13,578 views
58 votes
58 votes

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

4 Answers

Best answer
76 votes
76 votes

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.

edited by
20 votes
20 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)

8 votes
8 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
2 votes
2 votes

Explanation for I.

Source: https://cs.stackexchange.com/questions/68078/can-any-left-recursive-grammar-be-converted-into-equivalent-right-recursive-gram

  • Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB
  • Convert "RLG for LR" directly to "FA for LR"
  • Reverse "FA for LR" to get "FA for L" by
    • Change starting state to final state
    • Reverse direction of each transition
    • Create a new start state with ϵ transitions to all accepting states
    • Convert "FA for L" directly to "RLG for L"

Similar approach can be derived for converting "RLG for L" to "LLG of L".

Answer:

Related questions

37 votes
37 votes
3 answers
2
Kathleen asked Sep 12, 2014
15,660 views
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only ifThe SLR(1) parser for G has S-R conflictsThe LR(1) parser for G has S-R conflictsThe...