Finding an LL(1) grammar? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

How would I find an LL(1) grammar for the language:

L=a^m bⁿ c^m+n

Where m and n are elements of the naturals? My context-free grammar is:

S → AB

A → acA | ac

B → bcB | bc

Could anyone tell me if I’m on the right track?

edit: my new CFG is

S → aSc | B

B → bBc | bc

However I think I may have an error regarding LL(1) in that the two derivations of B both start with b..is that correct?

EDIT Thank you I think I got it:

S → aSc | B

B → bBc | lambda

Answer 1

There are two main problems with your grammar:

1. You currently can generate some strings not in the language. As an example, your grammar can generate acacbcbc, which isn't in the language.

2. Your grammar is not LL(1) because you have numerous FIRST/FIRST conflicts. For example, the pair of productions A → acA and A → ac both start with a, so given the nonterminal A and the character a, you can't determine which production to apply.

As a hint, the strings in your language are precisely the strings of the form a^mbⁿcⁿc^m. In other words, try seeing if you can generate m a's at the front and m c's at the back, then switch and generate n b's matched with n c's. You might want to try finding a grammar for a^mc^m first and see if you can adapt it.

EDIT for the new grammar: This looks a lot better! However, you still have a FIRST/FIRST conflict in the productions

B → bBc

and

B → bc

Additionally, your grammar cannot generate the strings ac or ε. You should be able to resolve both of these issues by fixing up the FIRST/FIRST conflict. As a hint: how could you replace the second production with one that lets you generate no characters?

Hope this helps!