Explain chomsky classification of languages with suitable examples
Ans: Any language is appropriate for communication provided the syntax & semantic of the language is termed to the participating sides. It is made feasible by forcing a standard on the way to create sentences from words of that language. This standard is forced by a set of rules. This set of rules is known as grammar of the language. As per to the Chomsky classification, a grammar G = (N, ∑, P, S) is known as Type 0: if there is no restriction on the production rules that is in α→β, in which α, β∈ (N ∪ ∑)*. This type of grammar is as well called an unrestricted grammar and language is known as free language.
Type 1: if in eash production α→β of P, α, β ∈ (N ∪ ∑)* and |α| ≤ |β|. Here |α| and |β| denote number of symbols in string α and β correspondingly. This type of grammar is as well called a context sensitive grammar (or CSG) and language is known as context sensitive.
Type 2: if in each production α→β of P, α ∈ N and β ∈ (N ∪ ∑)*. Here α is a single non-terminal symbol. This kind of grammar is as well known as a context free grammar (or CFG) and language is called context free.
Type 3: if in each production α→β of P, α ∈ N and β ∈ (N ∪ ∑)*. Here α is a single non-terminal symbol and β may contain at the most one non-terminal symbol and one or more terminal symbols. The non-terminal symbol appearing in β should be the extreme right symbol.
This kind of grammar is as well called a right linear grammar or regular grammar (or RG) and the corresponding language is known as regular language.