Unrestricted Grammar

In automaton, Unrestricted Grammar or Phrase Structure Grammar is the most general in the Chomsky Hierarchy of classification. This is type0 grammar, generally used to generate Recursively Enumerable languages. It is called unrestricted because no other restriction is made on this except each of their left hand sides being non-empty. The left hand sides of the rules can contain terminal and non-terminal, but the condition is at least one of them must be non-terminal.

A Turning Machine can simulate Unrestricted Grammar and Unrestricted Grammar can simulate Turning Machine configurations. It can always be found for the language recognized or generated by any Turning Machine.





Formal Definition

The unrestricted grammar is 4 tuple -

G = (N,Σ,P,S)


N - A finite set of non-terminal symbols or variables,
Σ - It is a set of terminal symbols or the alphabet of the language being described, where N ∩ Σ = φ,
P - It is a finite set of "productions" or "rules",
S - It is a start variable or non-terminal symbol.

If, α and β are two strings over the alphabet N ∪ Σ. Then, the rules or productions are of the form α → β. The start variable S appears on the left side of the rule.





Example of Unrestricted Grammar

Language

L={anbncn | n≥0}

Grammar

S→aBSc {Equal Number of a's, B's, c's} S→ ε {Eliminate S} Ba→aB {Move a's to Right of B's} Bc→bc {Reduce B before first c to b} Bb→bb {Reduce all remaining B's to b}