Slide 2.2: The Chomsky hierarchy

Slide 2.1: Programming language syntax
Slide 2.3: The Chomsky hierarchy (cont.)
Home

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>