1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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. ♦
    Commented Mar 25, 2017 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
    Commented Mar 25, 2017 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. ♦
    Commented Mar 25, 2017 at 18:48
  • $\begingroup$ Perhaps designing a deterinistic PDA helps to get some insight? $\endgroup$
    – Hendrik Jan
    Commented Mar 25, 2017 at 19:37

1 Answer 1

Reset to default
-2
$\begingroup$

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$

Improve this answer
$\endgroup$
1
  • 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$
    – templatetypedef
    Commented Mar 26, 2017 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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