Question

What are finite automata? What are pushdown automata? What are the Turing machines?

Answer 1

A finite automaton (FA) is a machine used to recognize patterns within input taken from some character set (or alphabet) C. The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

A finite automata consists of:

• a finite set S of N states
• a special start state
• a set of final (or accepting) states
• a set of transitions T from one state to another, labeled with chars in C

A PDA is formally defined as a 7-tuple:

where

• is a finite set of states
• is a finite set which is called the input alphabet
• is a finite set which is called the stack alphabet
• is a finite subset of , the transition relation.
• is the start state
• is the initial stack symbol
• is the set of accepting states

Turing machine can be formally defined as a 7-tuple where

• is a finite, non-empty set of states
• is a finite, non-empty set of tape alphabet symbols
• is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
• is the set of input symbols
• is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) If is not defined on the current state and the current tape symbol, then the machine halts.^[21]
• is the initial state
• is the set of final or accepting states. The initial tape contents is said to be accepted by if it eventually halts in a state from .

Anything that operates according to these specifications is a Turing machine.