I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character b is exactly triple compared to the amount of character a" for $\Sigma = \{a,b\}$.

I've tried to figure it out so that if we consider a string $w$ to have one a, then the acceptable presentations for $w$ considering language $A$ would be abbb, babb, bbab and bbba.

But how do I build the CFG rules for that? I have tried something like $$S \rightarrow A$$ $$A \rightarrow \epsilon | aAbbb |baAbb | bbaAb | bbbaA$$ but I think it's not very good because at least I cannot build an LL(1)-parser out of it (which would be good) because of ambiguity. And it doesn't quite work out for a string like bbbbbbaa $\in A$.

Is it possible to build a CFG for this language that can be parsed using a LL(1) parser? If not, why not?

  • $\begingroup$ Do you want to build a CFG for the language? Or do you want to build a LL(1) CFG? Your first sentence suggests the former, your later comments suggest the latter. Those are different goals -- it would help to be precise and consistent about what your goal is. $\endgroup$
    – D.W.
    Mar 25 '17 at 18:17
  • $\begingroup$ @D.W. actually that is part of my problem. I want to figure out is it possible at all to build a LL(1) CFG for this language. And if not, why? Sorry for the unclear presentation. $\endgroup$
    – tuska10
    Mar 25 '17 at 18:26
  • $\begingroup$ Cool, sounds good. Then it would help to state that explicitly. I've edited the question for you, but in the future it'd be better to make sure the post is consistent about what your question is. $\endgroup$
    – D.W.
    Mar 25 '17 at 18:48
  • $\begingroup$ Perhaps designing a deterinistic PDA helps to get some insight? $\endgroup$ Mar 25 '17 at 19:37

I believe that any string able to be represented by a CFG can also be parsed in LL or LR. That is just one of the features of CFG's. The grammar you have originally written can be parsed using LL as the upper-case $A$ will act always as your left-most variable to be expanded and simplified.

I think your problem with constructing the grammar can be solved by also including rules in which the lower-case and upper-case $a$'s are switched, though, that is a rather clunky solution.

$S \rightarrow A$

$A \rightarrow \epsilon | baAbb | bAabb | bbbaA | bbbAa | bbaAb | bbAab | aAbbb| Aabbb$

  • 2
    $\begingroup$ Not all context-free languages have LL or LR grammars. Also, I don't think that grammar works: can you derive bbbbbbaaaabbbbbb with it? $\endgroup$ Mar 26 '17 at 4:08

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.