4.4 Theory of computation

Question 1

What is representational abstraction?

Answer 1

Removing uneccesary details from a problem

Question 2

What is abstraction by generalisation?

Answer 2

Grouping things in terms of common characteristics

Question 3

What is Data abstraction?

Answer 3

Seperating the way a compound data structure is used to how it is constructed

Question 4

What is problem reduction?

Answer 4

Reducing a problem into one that has already been solved

Question 5

What does the metacharcter ‘?’ denote in a regular expression

Answer 5

one or none

A?B = {AB, B}

Question 6

What does the metacharcter ‘*’ denote in a regular expression

Answer 6

Zero or more

A* = { ,A,AA,AAA,AAAA….}

Question 7

What does the metacharcter ‘+’ denote in a regular expression

Answer 7

One or more

A+ = {A,AA,AAA,AAAA…}

Question 8

What do parenthases ( ) denote in a regular expression

Answer 8

A group

(AB)?A = {A,AB}

Question 9

What does the metacharcter ‘|’ denote in a regular expression

Answer 9

OR
(Everything on the left, OR everything on the right)

A|B = {A,B}

Question 10

Exam style question

Describe the set of strings matched by the regular expression:
a?(a|b)*aba+a

Answer 10

zero or one instances of ‘a’
zero or more instances of either ‘a’ or ‘b’
‘a’ followed by ‘b’
one or more instances of ‘a’
a single character ‘a’