The Chomsky Hierarchy
Chomsky classified languages according to the complexity of their grammars and the power of the algorithms needed to recognize them:
Terminology of a grammar includes:
- The vocabulary of a grammar includes its terminal and nonterminal symbols.
- An arbitrary production has the form
α ::= β where α and β are strings of symbols from the vocabulary, and α has at least one nonterminal in it.
- The symbol ‘|’ in a production is a separator.
- The special terminal symbol ‘
ε’ is an empty string.
Type-3 Grammars: Regular Grammars
They are the most restrictive grammars allow only a terminal or a terminal followed by one nonterminal on the right side—that is, rules of the form
“<A> ::= a” or “<A> ::= a <B>”
A grammar describing binary numerals such as 0011 and 101 can be designed using the format of a regular grammar:
<binary> ::= 0 | 1 | 0 <binary> | 1 <binary>