4.4 Theory Of Computation Flashcards
1
Q
?
A
0 or 1 occurrence of previous character
2
Q
*
A
Min 0 occurrences of previous character
3
Q
+
A
Min 1 occurrences of previous character
4
Q
|
A
Or
5
Q
“Backus Naur form …
A
Does not support iteration. It uses recursion instead”
6
Q
Backus Naur diagrams
A
Syntax / railroad diagrams
7
Q
Intractable
A
Takes a long time to complete
Not the same as unsolvable
E.g. Travelling Salesman
8
Q
Turing Machines
A
- a model of computation
- a task is computable if and only if it can be computed by a Turing machine
9
Q
The Universal Turing Machine
A
“A Turing Machine performs a specific algorithm. The UTM can simulate any other Turing Machine”
10
Q
a
A
a
