Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? - EduRev Computer Science Engineering (CSE) Question

Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity

Open App

Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Consider these three grammars.Which of the fo...

Join the Discussion on the App

Consider these three grammars.

Which of the following statements is not true?

a)
If w can be generated by G1, then it can be generated by G2.
b)
If w can be generated by G2, then it can be generated by G3.
c)
If w can be generated by G3, then it can be generated by G1.
d)
If w can be generated by G2, then it can be generated by G1.

Correct answer is option 'C'. Can you explain this answer?

FREE This question is part of

Test: Syntax Directed Translation- 2

Attempt Test

Attempt this Test

Verified Answer

Consider these three grammars.Which of the following statements is not...

In G1, T can take the form of v * v * v * v * v ....
In G2, R can take the form * v * v * v ..., so T can take the form of v * v * v * v ....

Thus, in both G1 and G2, E can take the form v * v * v + v * v * v * v + v * v ....

These are the algebraic expressions involving only addition and multiplication.

In G3, T can take the form v * v * v * v, so R can take the form + v * v + v * v. Thus, through the production E ! T R, E can take the form of any arithmetic expression.

However, E can also take the form of non-arithmetic expressions,

as with E --> R --> + T R --> + v R --> + v + T R ---> + v + v R --> + v + v.

In addition, G3 can generate ε , which G1 and G2 cannot.

Thus, while G1 and G2 generate the same language,

G3 generates a somewhat larger language. Incidentally, G1 demonstrates left-recursion because it contains productions of the form X --> X α ( in addition to non-problematic productions of the form X --> β ).

Left recursion can be eliminated by introducing a helper non-terminal R and changing the grammar to read

View all questions of this test

View all answers Start learning for free

< Previous Question Next Question >

Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Consider the following problems L(G) denotes the language generated by a grammar G.L(M) denotes the language accepted by a machine M.(I) For an unrestricted grammar G and a string w, where w = L(G).(II) Given a Turing Machine M, whether L(M) is regular.(III) Given two grammars G1 and G2 whether L(G1) = L(G2).(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.Which one of the following statements is correct?

View answer

Which one of the following statements is FALSE?

View answer

Which of the following statements are true?I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versaII. All∈ -productions can be removed from any context-free grammar by suitable transformationsIII. The language generated by a context-free grammar all of whose productions are of the form (where ω , is a string of terminals and is a non-terminal), is always regularIV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

View answer

Assume the statements S1 and S2 given as:S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite.S2: There exists an algorithm to determine whether two context free grammars generate the same language.Which of the following is true?

View answer

Direction: Two Statements I and II are given. These statements may be either independent causes or may be effects of independent causes or a common cause. One of these statements may be the effect of the other statements. Read both statements and decide which of the following answer choice correctly depicts the relationship between these two statements:Statement I. A large number of Primary Schools in the rural areas are run by only one teacher.Statement II. There has been a huge dropout from the primary schools in rural areas.

View answer

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

View all

Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer?

Share with a Friend

Answer this doubt

Question Description
Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer?.

Solutions for Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.

Here you can find the meaning of Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer?, a detailed solution for Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? has been provided alongside types of Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Consider these three grammars.Which of the following statements is not true?a)If w can be generated by G1, then it can be generated by G2.b)If w can be generated by G2, then it can be generated by G3.c)If w can be generated by G3, then it can be generated by G1.d)If w can be generated by G2, then it can be generated by G1.Correct answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.

Explore Courses for Computer Science Engineering (CSE) exam