retagged by
528 views
2 votes
2 votes

 

I don’t get the explanation, How do you categorize grammer on the basis of production?

retagged by

1 Answer

Best answer
6 votes
6 votes

According to Chomsky, there are 4 types of grammar

Let $V = \text{set of non-terminals}$ and $T = \text{set of terminals}$

 

(a) $\text{Type-3}$ grammar

- These grammars generate regular language.

- In this grammar every production is of the form

        $A \rightarrow xB$ or $A \rightarrow x$,   where $A, B \in V$ and $x \in T$ (This is right linear grammar)

       $A \rightarrow Bx$ or $A \rightarrow x$,   where $A, B \in V$ and $x \in T$ (This is left linear grammar)

       Every production of $\text{Type-3}$ grammar must either be right linear or left linear.

 

(b) $\text{Type-2}$ grammar

- These grammars generate context-free language.

- Every production of $\text{Type-2}$ grammar must be of the form

          $A \rightarrow \alpha$,       where $\alpha \in (V \cup T)^*$ and $A \in V$

 

(c) $\text{Type-1}$ grammar

- These grammars generate context-sensitive language.

- The productions must be in the form

       $\alpha A\beta \rightarrow \alpha \gamma \beta$ 

        where $A \in V$ and $\alpha \beta \gamma \in (V \cup T)^*$, the strings $\alpha, \beta$ may be empty but $\gamma$ must not be empty

 

(d) $\text{Type-0}$ grammar

- These grammars generate Recursively enumerable language.

- The productions must be in the form

        $\alpha \rightarrow \beta$

         where $\alpha, \beta \in (V \cup T)^* $ and $\alpha$ cannot be null and must contain atleast one non-terminal.


edited by

Related questions

0 votes
0 votes
0 answers
1
goluabhinan asked Sep 16, 2018
201 views
What is the difference between phase structured grammar and phrase structured grammar?
0 votes
0 votes
0 answers
3