Theory of computation (A Level) flashcards

Topic 13: Theory of computation

What is a finite state machine?

A machine with a fixed number of states that changes state as it reads each input symbol. Without output, the input is accepted if it ends in an accepting state.

What is a Mealy machine?

An FSM with output, in which each output is produced on a transition; arcs are labelled input / output.

What do *, +, ? and | mean in a regular expression?

* means 0 or more repetitions; + means 1 or more; ? means 0 or 1 (optional); | means alternation (or). Brackets group a regular expression.

Does k(o|i)+t match kt, kot and koit?

It matches kot and koit, but not kt, because + needs at least one o or i.

What is a regular language?

A language that can be represented by a regular expression (equivalently, accepted by an FSM).

What are the parts of a Turing machine?

A finite set of states (one start state; halting states have no outgoing transitions), a finite alphabet, a tape infinite in one direction divided into squares, and a read-write head that moves one square at a time.

What is a universal Turing machine, and why is it important?

A Turing machine that can simulate any other, with the other machine's description and input stored on its tape. It shows one machine can run any program held as data, and Turing machines define what is computable.

Tractable vs intractable problems

A tractable problem has a polynomial (or less) time solution. An intractable problem has no polynomial time solution, so heuristics may be used to find an acceptable answer.

What is the halting problem?

The unsolvable problem of determining, without running it, whether a program will eventually stop for a given input. It shows some problems cannot be solved by any algorithm.

What is BNF used for?

Backus-Naur form is a notation of production rules for defining the syntax of a language.