Formal Language Theory A Primer

Abstract automata are machines with internal states, an input tape, and sometimes an auxiliary information storage stack. Automata read symbols from the tape, making transitions from one state to another, while performing other operations on the tape and stack. The simplest example of such an idealized machine is the finite automaton  

DEFINITION A finite automaton (FA) M is specified by three sets A, E and E and a state-transition function 0 E x — E, where 

Given an automaton A4 tliat starts in state ai, and any finite string s A, (j) a, s) will represent the final output state, that M. will enter after having processed s, one symbol at a time, from left to right. M. is said to accept the word s if 4 a, s) S the word s is rejected if and only if it is not accepted. Finally, we may define the language C M) accepted by A4 as the set of all words s e A that are accepted by M. 

Regular Languages allow only those productions that are of the form a — era or a — (T. Recognized by Finite Automata. 

Context-Free Languages allow only productions of the form a — d, where a is an arbitrary string of terminal and non-terminal symbols there is also a fixed bound on the length of a (= 5- ). Recognized by Push-Down Automata. 

---