The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+31 votes

Which of the following statements are true?

- Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
- All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations
- 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
- The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

- I, II, III and IV
- II, III and IV only
- I, III and IV only
- I, II and IV only

+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.

+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)

+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

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

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**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,204 questions

43,662 answers

124,118 comments

42,949 users