The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
2.2k views

Which of the following statements are true?

  1. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
  2. All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations
  3. The language generated by a context-free grammar all of whose productions are of the form $X \rightarrow w$ or $X \rightarrow wY$ (where, $w$ is a string of terminals and $Y$ is a non-terminal), is always regular
  4. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
  1. I, II, III and IV
  2. II, III and IV only
  3. I, III and IV only
  4. I, II and IV only
asked in Compiler Design by Veteran (59.4k points) | 2.2k views

4 Answers

+39 votes
Best answer

Answer is C: 

Statement 1 is true: Using GNF we can convert Left recursive grammar to right recursive and by using reversal of CFG and GNF we can convert right recursive to left recursive.

Statement 2 is false: because if $\epsilon$ is in the language then we can't remove  $\epsilon$ production from Start symbol. (For example $L = a^*$)

Statement 3 is true because right linear grammar generates regular set

Statement 4 is true, only two non-terminals are there in each production in CNF. So it always form a binary tree.

answered by Boss (13.5k points)
edited by
+9 votes

1.Every left recursive grammar can be converted to a right recursive grammar and vice versa

    yes their is algo.

2. All ∈ production can be removed from any CFG by suitable transformation

   NO when language itself contain null then u can't remove null.

3. The language generated by a CFG all whose production are to the form X→ w or X→ wY 

    yup their is formula for it X-> aT* then regular since right linear form

4.The derivation trees of strings generated by a CFG in CNF are alays binary trees.

    yes b/c cfn in form of S->AB or S->a so max two child at a time.

Answer is (C)

answered by Veteran (59.8k points)
+5 votes
2nd is false

S->∈ if we have this production in our cfg we can remove it if we do so it changes language

All other options are true so ans is c
answered by Boss (31.3k points)
0
but,we have a procedure to remove null production in cfg isnt it???and the qs asked that all epsilon production can be removed or not...
+18

Yes, we can remove any Null production except in one case if we can derive $\epsilon$ from grammar, we cannot remove that. 

eg. $S\rightarrow aS|\epsilon$ generating language $L = a^*$, and if we remove $\epsilon$ from it,
we will get $S\rightarrow aS|a$ generating a different language ,$L = a^+$ 

–1 vote

Answer is A

Statement 1 is true: Using GNF we can convert Left recursive grammar to right recursive and by using reversal of CFG and GNF we can convert right recursive to left recursive.

Statement 3 is true because right linear grammar generates regular set

Statement 4 is true, only two non-terminals are there in each production in CNF. So it always form a binary tree.

Statement 2 is true, we can remove null productions from any context free grammar G producing language L(G) using suitable transformations such that the new grammar G1 will produce language L1(G1).

The new language L1 will produce every string produced by L except for Null string. 

But the statement given in question does not mention the new grammar to be equivalent of the original grammar. Therefore statement 2 is also TRUE and the answer is A

answered by (49 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,204 questions
43,662 answers
124,118 comments
42,949 users