Theory of Computation

Question 1

What is Abstraction?

Answer 1

Abstraction is the name given to the process of omitting unnecessary details from a problem.

Question 2

Representational abstraction

Answer 2

A representation of a problem arrived at by removing unnecessary details from the problem.

Question 3

Abstraction by generalisation /
categorisation

Answer 3

Grouping by common characteristics to form a hierarchical relationships

e.g. “is a kind of”

Question 4

What is information hiding

Answer 4

Hiding all non-essential details of an object that doesn’t affect its essential characteristics.

Question 5

What is procedure abstraction?

Answer 5

Breaking down a problem into reuseable procedures, abstraction specific values.

Question 6

What is functional abstraction?

Answer 6

Hiding the specific computation method and only focusing on the input/output of the function

Question 7

What is data abstraction?

Answer 7

Hiding details of data representation, allowing creation of new abstract data types.

Question 8

What is problem abstraction/reduction?

Answer 8

Simplifying a problem by removing details until it’s similar to a previously solved problem.

Question 9

What is decomposition?

Answer 9

Dividing a complex problem into smaller, more manageable sub-problems.

Question 10

What is composition?

Answer 10

Combining simple procedures or data types to build more complex ones (e.g. tree structure).

Question 11

What is automation in computer science?

Answer 11

Executing abstract models using algorithms, program code, and data structures.

Question 12

What are the main steps to achieve automation?

Answer 12

• Create models
• Design algorithms
• Implement in code
• Use data structures
• Execute the code

Question 13

What are the four constructs used in pseudocode?

Answer 13

Sequence, Assignment, Selection, Iteration

Question 14

What does sequence mean in pseudocode?

Answer 14

Instructions are carried out one after the other, in order.

Question 15

What is assignment in pseudocode?

Answer 15

Giving a value to a variable (e.g. x ← 5).

Question 16

What is selection in pseudocode?

Answer 16

Choosing between actions based on conditions (IF, ELSE, etc.).

Question 17

What is iteration in pseudocode?

Answer 17

Repeating actions using FOR or WHILE loops.

Question 18

What is hand-tracing an algorithm?

Answer 18

Manually running through an algorithm step-by-step with test data to verify correctness.

Question 19

How do you argue for the correctness of a program?

Answer 19

Use logical reasoning, test data, and user feedback.

Question 20

What is a Finite State Machine (FSM)?

Answer 20

A computational model with a finite number of states, transitions between states based on inputs, and optional outputs (Mealy machines).

Question 21

What is the difference between an FSM with and without output?

Answer 21

• Without output: Only tracks state transitions.
• With output (Mealy): Produces an output on each transition (e.g., 1 | “a”).

Question 22

How do you represent an FSM?

Answer 22

Using a state transition diagram (circles for states, arrows for transitions) or a state transition table.

Question 23

What happens if an FSM reaches a non-final state with no valid transitions?

Answer 23

The input is rejected.

Question 24

What is a set?

Answer 24

An unordered collection of unique elements (e.g., {1, 2, 3}).

Question 25

What is set comprehension?

Answer 25

A compact way to define a set using rules (e.g., {x | x ∈ ℕ ∧ x > 5}).

Question 26

What is the empty set?

Answer 26

A set with no elements, denoted {} or Ø.

Question 27

What is the Cartesian product of sets?

Answer 27

The set of all ordered pairs from two sets (e.g., {1, 2} × {a, b} = {(1,a), (1,b), (2,a), (2,b)}).

Question 28

What is the union (∪) of two sets?

Answer 28

All elements from both sets, excluding duplicates (e.g., {1, 2} ∪ {2, 3} = {1, 2, 3}).

Question 29

What is the intersection (∩) of two sets?

Answer 29

Elements common to both sets (e.g., {1, 2} ∩ {2, 3} = {2}).

Question 30

What is set difference (\ or -)?

Answer 30

Elements in the first set but not the second (e.g., {1, 2} \ {2} = {1}).

Question 31

What does ⊆ and ⊂ mean?

Answer 31

* ⊆=> Subset (all elements of A are in B). * ⊂=> proper subset (A ⊆ B but A ≠ B).

Question 32

What is a regular expression?

Answer 32

A shorthand to describe a set of strings (e.g., a(b|c)* matches "a", "ab", "ac", "abbc", etc.).

Question 33

What do these metacharacters mean?

Answer 33

* (*): 0 or more repetitions. * +: 1 or more repetitions. * ?: 0 or 1 (optional). * |: OR (alternation). * ( ): Grouping.

Question 34

What is the regex for "strings starting with 0, followed by any number of 1s"?

Answer 34

01*.

Question 35

How are FSMs and regular expressions related?

Answer 35

They are equivalent—any language defined by a regex can be recognized by an FSM, and vice versa.

Question 36

Convert the regex (ab)+c? to an FSM.

Answer 36

* Start → a → b → loop back for (ab)+. * Optional c → final state.

Question 37

What is a countably infinite set?

Answer 37

A set whose elements can be paired with natural numbers (e.g., integers).

Question 38

What is the cardinality of a set?

Answer 38

The number of elements in a finite set (e.g., |{1, 2}| = 2).

Question 39

What is a regular language?

Answer 39

A language that can be defined by a regex or recognized by an FSM.

Question 40

What set does {0^n 1^n | n ≥ 1} represent?

Answer 40

{01, 0011, 000111, ...} (equal 0s and 1s).

Question 41

What is the output of a Mealy machine for input 101 if transitions are: * S0 → S1 on 1 outputs "a", * S1 → S2 on 0 outputs "b", * S2 → S2 on 1 outputs "c"?

Answer 41

"a" → "b" → "c" = "abc".

Question 42

What is a context-free language?

Answer 42

A set of strings defined by a context-free grammar (CFG), where production rules determine valid strings.

Question 43

How do CFLs differ from regular languages?

Answer 43

CFLs can handle recursion and nested structures (e.g., balanced parentheses), which regular expressions cannot.

Question 44

What is BNF?

Answer 44

A notation for defining context-free grammars using production rules (e.g., ::= a )

Question 45

What are non-terminals in BNF?

Answer 45

Symbols in that can be expanded further (e.g., ).

Question 46

What are terminals in BNF?

Answer 46

Literal characters/strings that cannot be expanded (e.g., a, +, 123).

Question 47

What does the | symbol mean in BNF?

Answer 47

OR (alternation) ## Footnote e.g., ::= 0 | 1 | ... | 9.

Question 48

How does BNF support recursion?

Answer 48

A non-terminal can reference itself ## Footnote e.g., ::= | .

Question 49

Write BNF for a signed decimal number.

Answer 49

::= + | - ::= 0 | 1 | ... | 9 ::= | | . ::= |

Question 50

What is a syntax diagram?

Answer 50

A visual representation of BNF rules using: * Rectangles for non-terminals. * Ovals/Ellipses for terminals. * Arrows showing valid paths.

Question 51

How does a syntax diagram for look?

Answer 51

Start → (rectangle) → End. OR Start → → loop back to .

Question 52

Draw a syntax diagram for ::=