Automata Chomsky Hierarchy
Chomsky Hierarchy
Formal languages: A language with precise syntax and semantics are called formal languages.
Noam Chomsky has defined the Chomsky hierarchy in 1956. He is an American scientist and philosopher, and gave the mathematical model of grammar which is effective & efficient for writing computer languages.
The Chomsky hierarchy is a collection of various formal grammars. With the use of this formal grammar we can generate some formal languages.
The Chomsky hierarchy contains 4 types of grammar, which are listed below:
- Unrestricted grammar
- Context sensitive grammar
- Context free grammar
- Regular grammar
The power of all machines are in the form FA<PDA<LBA<TM
The above diagram shows the relationship between languages and their corresponding relation.
Unrestricted Grammar:
It is more powerful than other types of grammar in Chomsky hierarchy. It is also called unrestricted grammar or phrase grammar or semi-Thue grammar. The language generated by unrestricted grammar is recognized by Turing machine. The relationship of unrestricted grammar and Turing machine is shown below:
A grammar with no restrictions on the production rules is called unrestricted grammar.
An unrestricted grammar or type 0 grammar G consists of 4 tuples (V, T, P, S):
V: - It is a finite set of variables also called non-terminals.
T: - It is a collection of finite set of symbols called terminals in every production rule.
S: - It is called the start symbol of every production rule.
P: - It is a finite set of rules called production rules. Production rules are in the form:
P: ? -> ?
Context Sensitive Grammar:
Context sensitive grammar is also called Type -1 grammar. Type -1 grammar defines the language called context sensitive language, which are accepted by Linear Bounded Automata. The relationship of context sensitive grammar and linear bounded automata is shown below:
Context sensitive grammar or type 1 grammar consists of 4 tuples or elements (V, T, P, S):
V: - It is a finite set of variables also called non-terminals.
T: - It is a collection of finite set of symbols called terminals in every production rule.
S: - It is called the start symbol of every production rule.
P: - It is a finite set of rules called production rules .Production rules are in the form:
P: ?A? -> ???
Example of context sensitive language are:
L = { anbncn : n>=1 }
Context free Grammar:
In Context Free Grammar, production rules have condition that on the left-hand side of each rule there must be a single variable and on the right-hand side of production rules there may be combination of variables and terminals, and can also include empty string i.e. ?.
Context Free grammar also called type -2 grammar. It defines the language that is accepted by Push down Automata.
The relationship of context free grammar and push down automata is shown below:
A Context Free Grammar or type 2 grammar G consists of 4 tuples (V, T, P, S):
V: - It is a finite set of variables also called non-terminals.
T: - It is a collection of finite set of symbols called terminals in every production rule.
S: - It is called the start symbol of each production rule.
P: - It is a finite set of rules called production. Production rules Production rules are in the form:
P: ? -> ?
Consider the example of Context free Grammar:
S -> 0S1
S -> 1S1
S-> ?
This grammar can also be written as:
S -> 0S1|1S1| ?
Regular Grammar
Regular grammar is also called Type -3 grammar.
A regular grammar defines the language called regular language that are accepted by finite Automata.
The relationship of regular grammar and finite automata is shown below:
A Regular Grammar or type 3 grammar G consists of 4 tuples (V, T, P, S):
V: - It is a finite set of variables also called non-terminals.
T: - It is a collection of finite set of symbols called terminals in every production rule.
S: - It is called the start symbol of each production rule.
P: It isa finite set of rules called production rules. Production rules are in the form:
P: A -> a or
A -> aB
Example:
L = { an b2m | n>=0,m>=0 } is a regular language