0
$\begingroup$

Let G b the following CFG (Where S is the start symbol):

S→aB|aDc
B→bBc|c
D→bc|c

(a) Show that G is ambiguous.
(b) Show that G is not an LR(1) grammar.
(c) Modify G into an equivalent grammar G′ that is LR(1). Explain why G′ is an LR(1) grammar and why G and G′ are equivalent.

My current answers:

(a) I showed that there exists two left derivation trees for string abcc - therefore it is ambiguous.

(b) I simply stated that an LR(1) grammar is not ambiguous by definition, and since (a) shows it is ambigious it follows that G is not an LR(1) grammar.

(c)
G':

S→aB 
B→bBc|c

I removed the nonterminal D, which makes it unambiguous.

Questions:

Is there a more suiting answer for (b)?

How do I explain why G' is an LR(1) grammar in (c)?

Thank you!

$\endgroup$
  • $\begingroup$ Your G' does not generate acc $\endgroup$ – rici May 10 '19 at 19:49
1
$\begingroup$

Your answer to B is perfectly fine.

To show that something is LR(1) you should generate the automaton and show it has no conflicts.

Don't forget you have to show that G and G' generate the same language. Luckily this is simple because your removal of rules only involved a finite sub language thus you can exhaustively show equivalence.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Is it through the parse table for the automaton I show that there is no conflicts? $\endgroup$ – Danjero May 10 '19 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.