Select all the statements below which are TRUE: Let G be a context-free grammar

Question

Select all the statements below which are TRUE: Let G be a context-free grammar If a string w in L(G) is the yield of two different derivation trees of G. then G is ambiguous. Consider the grammar below: S -rightarrow AaAa | BbBa A rightarrow Aaa | lambda B rightarrow b If we apply the substitution rule for B. then we get the following equivalent grammar. S rightarrow AaAa | bbBa A rightarrow Aaa | lambda The grammar below is an s-grammar: S rightarrow aS | bA A rightarrow aA | bBB B rightarrow b If G is a context-free grammar, then the right-most derivation is obtained if the right-most variable is replaced at each step of the derivation. If L is a context-free language, then L is regular. Let G = (V, T, S, P) be a context-free grammar. Then any derivation tree of G must have the root labeled S.

Explanation / Answer

1)True

If a context free grammar G has more than one derivation tree for some string w L(G), it is called an ambiguous grammar. There exist multiple right-most or left-most derivations for some string generated from that grammar

2)False

3)True

4)True

5)False

Every regular grammar is context-free, but not all context-free grammars are regular

6)True

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.