Chomsky Hierarchy - Formal Grammars

Formal Grammars

A formal grammar of this type consists of:

• a finite set of production rules (left-hand side right-hand side) where each side consists of a sequence of these symbols
• a finite set of nonterminal symbols (indicating that some production rule can yet be applied)
• a finite set of terminal symbols (indicating that no production rule can be applied)
• a start symbol (a distinguished nonterminal symbol)

A formal grammar defines (or generates) a formal language, which is a (usually infinite) set of finite-length sequences of symbols (i.e. strings) that may be constructed by applying production rules to another sequence of symbols which initially contains just the start symbol. A rule may be applied to a sequence of symbols by replacing an occurrence of the symbols on the left-hand side of the rule with those that appear on the right-hand side. A sequence of rule applications is called a derivation. Such a grammar defines the formal language: all words consisting solely of terminal symbols which can be reached by a derivation from the start symbol.

Nonterminals are usually represented by uppercase letters, terminals by lowercase letters, and the start symbol by . For example, the grammar with terminals, nonterminals, production rules

ε (where ε is the empty string)

and start symbol, defines the language of all words of the form (i.e. copies of followed by copies of ). The following is a simpler grammar that defines the same language: Terminals, Nonterminals, Start symbol, Production rules

ε