CODEWITHSUNDEEP
compiler-constructioncontext-free-grammar
user5005768Himadree
user5005768Himadree

Reputation: 1427

derive the given solution using given context free grammar rules

There is a language defined by a context-free grammar with the production rules below:

E -> T + E | T
T -> F * T | F
F -> (E) | C
C -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

In this grammar, non-terminals are E , T , F , and C ; terminals are parentheses, plus sign,asterisk, and numbers; E is the start symbol. Which of the following shows that the expression 7 + 3 * (6 + 4) is a sentence of this language?

 (a) E -> 7 + 3 * (F + T)    (c) E -> 7 + 3 * (T)
 (b) E -> 7 + 3 * E          (d) E -> 7 + T * (E)

i derived option (d) But the correct answer is option (a).why? please explain.thanks

Upvotes: 0

Views: 154

Answers (1)

Michael Dyck
Michael Dyck

Reputation: 2413

The problem as posed is not very well-defined, because it's unclear what it means for an option (such as one of those four) to "show" that an expression is in the language.

My best guess at the problem's intent is to ignore the "E ->" in each option, and ask which of the four is a sentential form that could appear in a derivation of the given sentence.

You can divide this into two questions: (1) which of these are sentential forms (i.e., forms that can be derived from E), and (2) of those, which derive the given sentence?

In step (1), you can eliminate (b) and (d):

re (b), if you try to derive 7 + 3 * E, you can get to 7 + 3 * T, but T doesn't derive E

re (d), if you try to derive 7 + T * (E), you can get to 7 + F * (E), but F doesn't derive T.

In step (2), you eliminate (c), because although 7 + 3 * (T) can be derived from E, T doesn't derive 6+4.

So the answer is (a), because 7 + 3 * (F + T) can be derived from E, and F can derive 6, and T can derive 4.

Upvotes: 2

Related Questions