FOR FREE CONTENT

Different grammar of CFG:

We already discuss all forms of Context Free Grammar (CFG).

Here we just write all different type of grammar of CFG:

1. Production of Chomsky Normal Form (CNF):

G : V → VV | T

Example:

S →AB

A → a

B → b

2. Production of Greibach Normal Form (GNF):

G: V → TV* or V → T | TV*

Example:

S → aAB

A → aA | a

B → bA | b

3. Production rule of Simple grammar or S-grammar:

G: V → TV* (Same as GNF) where any pair of Variable and Terminal (V, T) occurs at most once in Production.

S → aAC | bCD | cD | d

A → aAC

C → c

D → d

4. Production of Linear grammar: 

G: V → T* | T*V | VT* | T*VT*

Example:

S → aSb | λ

Q. Which of the follow grammar is S-grammar?

a. S → aAC | bCD | cD | b

    A → aAC                               

    C → c                                      

    D → d 

b. S → aAC | bD | cD | d

    A → aAC

    C → cC | λ

    D → d 

c. S → aAB

   A → aA | a

   B → bA | b

d. S → aACD | cAD | dDC

    A → aAC

    C → c

    D → d             

Answer: Option d is correct.

Explanation:

Production rules of S-grammar is G: V → TV* (Same as GNF) where any pair of Variable and Terminal (V, T) occurs at most once in a Production.

Option a is not correct: It violates the S-grammar production rule because (S, b) occur twice in a production i.e. S → bCD and S → b 

Option b is not correct: As per S-grammar production rule it never contain only λ. But in this given production has a λ production i.e. C → cC | λ. 

Option c is not correct: It also violate production rule of S-grammar because (A, a) and (B, b) occur twice in a production i.e. A → aA | a and B → bB | b correspondingly. 

Option d is correct: It follows all the production rules of S-grammar. 

Q. Match the following grammar and its production rules:

Different Context Free Grammar:

(a) Chomsky NormalForm           (b) Linear Grammar

(c) Simple grammar                       (d) Greibach Normal Form

Production rules:

(1)  A → ax, A ∊ V, a ∊ T and x ∊ V*

(2) A → y | yA | Ay | yAy, y ∊ T*, A ∊ V

(3) A → AA | a, a ∊ T

(4) A → ax, A ∊ V, a ∊ T and x ∊ V*, any pair  (A, a) occur at most once in production.

Which of the following is correct? 

(A) (a) – (2),  (b) – (1), (c) – (4) , (d) – (3)     

(B)  (a) – (3) , (b) – (1) , (c) – (2) , (d) – (4)

(C) (a) – (1) , (b) – (2) , (c) – (3) , (d) – (4)

(D)  (a) – (3) , (b) – (2) ,  (c) – (4) ,  (d) – (1)

You should know:

Before see the solution please follow previous chapter to clear the concept Chapter Different grammar of CFG,  Chapter Different forms of CFG.

Solution:   

Option C is correct. 

Explanation:

See all productions rules above.