CmSc 365 Theory of Computation
Grammars, Chomsky Hierarchy
Grammars are language generators. They consist of an alphabet of terminal symbols, alphabet of non-terminal symbols, a starting symbol and rules. Each language, generated by some grammar, can be recognized by some automaton. Languages (and the corresponding grammars) can be classified according to the minimal automaton sufficient to recognize them. Such classification, known as Chomsky Hierarchy, has been defined by Noam Chomsky, a distinguished linguist with major contributions to linguistics.
The Chomsky Hierarchy comprises four types of languages and their associated grammars and machines.
The types of languages form a strict hierarchy:
The distinction between languages can be seen by examining the structure of the grammar rules of their grammar, or the nature of the automata which can be used to identify them.
As we have discussed, a regular language is one which can be represented by a regular grammar, described using a regular expression, or accepted using an FSA.There are two kinds of regular grammar:
Examples of regular languages are pattern matching languages (regular expressions).
A Context-Free Grammar (CFG) is one whose production rules are of the form:
Context-Sensitive grammars may have more than one symbol on the left-hand-side of their grammar rules, provided that at least one of them is a non-terminal and the number of symbols on the left-hand-side does not exceed the number of symbols on the right-hand-side.
Their rules have the form:
Since we allow more than one symbol on the left-hand-side, we refer to those symbols other than the one we are replacing as the context of the replacement.
The automaton which recognizes a context-sensitive language is called a linear-bounded automaton: an FSA with a memory to store symbols in a list.
Since the number of the symbols on the left-hand side is always smaller or equal to the number of the symbols on the right-hand side, the length of each derivation string is increased when applying a grammar rule. This length is bound by the length of the input string. Thus a linear-bound automaton always needs a finite list as its store
Examples of context-sensitive languages are most programming languages
Theorem: A language is generated by an unrestricted grammar if and only if it is recursively enumerable.
Are all languages recursively enumerable? The answer is no. We have shown that there are languages that are not recursively enumerable. Such languages cannot be described a formal grammar. Each formal grammar has a finite description and therefore can be considered as a string. Thus, the set of all formal grammars is infinitely countable. The set of all languages over an alphabet is the power set of all strings over that alphabet. We have shown that power sets of infinite sets are not countable. Therefore there is no one-to-one match between grammars and languages.
Recursive language - a language that can be decided by a Turing machine
Why do we use the word "recursive"?
Three basic numerical functions, so simple that their computability is obvious:
Using these three functions we can define more complex functions.
plus(m,n+1) = s(plus(m,n))
mult(m,n+1) = plus(m,mult(m,n))
It can be proved that all computable functions can be obtained from these primitive functions and vice versa - all functions that can be obtained are computable.
Back to Contents page
Created by Lydia Sinapova