Topic 4 | Theory of Computation

What is the definition of a "State Machine"?

What is the different between a State Machine and a Mealy Machine?

Give an example of a Mealy Machine.

What is a FSM (Finite State Machine) that does not have an output called?

What does the regular expression a* represent?

What does the regular expression a+ represent?

What does the regular expression b? represent?

What does the regular expression a|b represent?

What is the importance of the "Turing Machine"?

What does the following Big O notations represent?
O(1)
O(nLogN)
O(n)
O(n^2)
O(2^n)

What is the "Halting Problem"?

What does the term "tractable" and "intractable" mean?

What are "Heuristic Methods" and when are they used in comp. sci.?

Give an application of Breadth-First and Depth-First search algorithms.

What are the uses of:
-> Pre-Order graph traversal
-> In-Order graph traversal
-> Post-Order graph traversal

Give a use of dijkstra's algorithm?

Why is Reverse Polish Notation used?

What time complexity is a Bubble Sort?

What is the time complexity of a Merge Sort?

What is "Diijstra's Algorithm"?

What does the term "Algorithm" mean?

• What is "Composition"?

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

What does the set A = {x | x ∈ ℕ ∧ x ≥ 1 } represent?

What does the term "Cardinality of a Finite State" mean?

Give an example of an infinite set.

Give an example of a finite set.

Find the Cartesian Product of the following two sets:
a = {A, B}
b = {C, D, E}
What does the x represent in b x a

What does ⊂ mean in set notation?

What does ∈ and ∉ mean in set notation

What is a "Meta Language"?

What is BNF and what does it stand for?

What does the BNF notation of the following mean?
::=
<>
|
{} (rarely used)
',' (rarely used)

What is the process of working out a given statement is valid according to a given BNF production called?

In BNF, what are the terminals and non-terminals in the following expression:
<DIGIT>::=0|1|2|3|4|5|6|7|8|9