GATE Exam > GATE Questions > Consider the following expression grammar G.E...
Start Learning for Free
Consider the following expression grammar G.
E -> E - T | T
T -> T + F | F
F -> (E) | id
T -> T + F | F
F -> (E) | id
Q. Which of the following grammars are not left recursive, but equivalent to G.
- a)E -> E - T | T
T -> T + F | F
F -> (E) | id - b)E -> TE'
E' -> -TE' | ε
T -> T + F | F
F -> (E) | id - c)E -> TX
X -> -TX | ε
T -> FY
Y -> +FY | ε
F -> (E) | id - d)E -> TX | (TX)
X -> -TX | +TX | ε
T -> id
Correct answer is option 'C'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Consider the following expression grammar G.E -> E - T | TT ->...
We know for left recursion : A -> Aα/β
After removing left recursion it can be written as A->βA’
A’->αA’/ε
Thus for : E->E- T/T
α= -T , β= T . thus new production after removing left recursion
is E->TE’ and E’->- TE’/ ε
T->FT’ and T’->+FT’/ ε
F->(E)/id.
After removing left recursion it can be written as A->βA’
A’->αA’/ε
Thus for : E->E- T/T
α= -T , β= T . thus new production after removing left recursion
is E->TE’ and E’->- TE’/ ε
T->FT’ and T’->+FT’/ ε
F->(E)/id.
Most Upvoted Answer
Consider the following expression grammar G.E -> E - T | TT ->...
Explanation:
The given grammar is as follows:
E -> E - T | T
T -> F | FF
F -> (E) | id
The objective is to find an equivalent grammar that is not left recursive.
Left Recursion:
A grammar is said to be left recursive if there exists a non-terminal A that can directly or indirectly derive a string that starts with A itself. In other words, a grammar is left recursive if there is a production of the form A -> Aα, where α is a sequence of terminals and/or non-terminals.
Equivalent Grammar:
Two grammars are said to be equivalent if they generate the same language, i.e., they generate the same set of strings.
Analysis of Options:
a) E - E - T | TT - T F | FF - (E) | id
b) E - TEE - -TE | T - T F | FF - (E) | id
c) E - TXX - -TX | T - FYY - FY | F - (E) | id
d) E - TX | (TX)X - -TX | TX | T - id
Option a:
This option is equivalent to the given grammar as it has the same productions and the same structure. However, it is still left recursive.
Option b:
This option is not equivalent to the given grammar as it introduces additional productions and changes the structure of the grammar.
Option c:
This option is equivalent to the given grammar and it is not left recursive. It achieves this by introducing two new non-terminals X and Y to eliminate the left recursion.
Option d:
This option is not equivalent to the given grammar as it introduces additional productions and changes the structure of the grammar.
Conclusion:
Among the given options, only option c is both equivalent to the given grammar and not left recursive. Therefore, the correct answer is option 'C'.
The given grammar is as follows:
E -> E - T | T
T -> F | FF
F -> (E) | id
The objective is to find an equivalent grammar that is not left recursive.
Left Recursion:
A grammar is said to be left recursive if there exists a non-terminal A that can directly or indirectly derive a string that starts with A itself. In other words, a grammar is left recursive if there is a production of the form A -> Aα, where α is a sequence of terminals and/or non-terminals.
Equivalent Grammar:
Two grammars are said to be equivalent if they generate the same language, i.e., they generate the same set of strings.
Analysis of Options:
a) E - E - T | TT - T F | FF - (E) | id
b) E - TEE - -TE | T - T F | FF - (E) | id
c) E - TXX - -TX | T - FYY - FY | F - (E) | id
d) E - TX | (TX)X - -TX | TX | T - id
Option a:
This option is equivalent to the given grammar as it has the same productions and the same structure. However, it is still left recursive.
Option b:
This option is not equivalent to the given grammar as it introduces additional productions and changes the structure of the grammar.
Option c:
This option is equivalent to the given grammar and it is not left recursive. It achieves this by introducing two new non-terminals X and Y to eliminate the left recursion.
Option d:
This option is not equivalent to the given grammar as it introduces additional productions and changes the structure of the grammar.
Conclusion:
Among the given options, only option c is both equivalent to the given grammar and not left recursive. Therefore, the correct answer is option 'C'.
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer?
Question Description
Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer?.
Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer?.
Solutions for Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Consider the following expression grammar G.E -> E - T | TT -> T + F | FF -> (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.a)E -> E - T | TT -> T + F | FF -> (E) | idb)E -> TE'E' -> -TE' | εT -> T + F | FF -> (E) | idc)E -> TXX -> -TX | εT -> FYY -> +FY | εF -> (E) | idd)E -> TX | (TX)X -> -TX | +TX | εT -> idCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup