Chomsky's hierarchy of grammars

Grammars are usually classified according to a hierarchy established by Chomsky (1965) (see also (Hopcroft and Ullman, 1979) or Salomaa (1973, 15)), according to the form of their productions. Each of the levels in the hierarchy has a corresponding automaton class:

• Type 0 or unrestricted (all possible grammars). Languages generated are recognized by Turing machines (automata that read from and write on an endless tape, which will be defined in section 4.3.1). Recognizing a string is outputting ``yes'' if the string belongs to the language.

• Type 1 or context-sensitive: $\beta$ never shorter than $\alpha$, $\vert\alpha\vert\le\vert\beta\vert$ (except for $S\rightarrow\epsilon$). Languages generated are recognized by linearly-bounded automata (a subclass of Turing machines, see section 4.3.1).

• Type 2 or context-free: $\alpha$ is a single variable ($\alpha\in V$). The class of languages generated by type 2 grammars is exactly the class of languages recognized by pushdown automata (PDA, Hopcroft and Ullman (1979, 110), Salomaa (1973, 34)), which may be seen as finite-state machine which can push symbols into and pop symbols from an infinite stack. A (nondeterministic) pushdown automaton is a 7-tuple $M=(Q,\Sigma,\Phi,\delta,q_I,\phi_0,F)$ where:
  • $Q$ is the finite set of states, with $q_I\in Q$ the initial state;
  • $\Sigma$ is the finite input alphabet;
  • $\Phi$ is a finite set of symbols which may be stored in the stack, which is not initially empty, but instead contains a special symbol $\phi_I$;
  • $F\subseteq Q$ is the subset of accepting states.
  • $\delta$ is the next-state or transition function of the automaton, which maps $Q\times\Sigma^*\times\Phi$ into finite subsets of $Q\times \Phi^*$; that is, when the PDA is in a state, reads in a string, pops a symbol from the stack, changes state, and pushes zero or more symbols into the stack, nondeterministically choosing the next state and the symbols pushed from a finite set of choices.
  The PDA is said to accept an input string from $\Sigma^*$ when it is led to at least one accepting state in $F$. An alternate acceptance criterion prescribes an empty stack at the end of the processing.

• Type 3 or regular: $\alpha\in V$, $\beta$ contains at most one variable at the right end. Languages generated are recognized by deterministic finite-state automata (see section 2.3.3).