Question
Download Solution PDFConsider the following expression grammar G:
E → E – T | T
T → T + F | F
F → (E) | id
Which of the following grammars is not left recursive, but is equivalent to G?Answer (Detailed Solution Below)
E → TX
X → -TX | ϵ
T → FY
Y → +FY | ϵ
F → (E) | id
Detailed Solution
Download Solution PDFConcept:
A production of grammar is said to have left recursion if its leftmost variable of its RHS is same as variable of LHS.
Consider grammar of type A → Aa | b
After removing left recursion, it becomes A → bA’, A’ → aA’| ϵ
Explanation:
Given grammar is:
E → E – T | T
T → T + F | F
F → (E) | id
After removing left recursion, it becomes:
E → TE’
E’ → -T E’ | ϵ
T → FT’
T’ → + FT’ | ϵ
F → (E) | id
Therefore option 3 is correct.
Last updated on Jan 8, 2025
-> GATE CS 2025 Admit Card has been released on 7th January 2025.
-> The exam will be conducted on 1st February 2025 in 2 shifts.
-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.
-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.
-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.