For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar

\begin{align*}S&\to aAba \mid abbB\\ A &\to Aa \mid \lambda\\ B &\to Bb \mid \lambda \end{align*}

Would the grammar above constitute as LL? I'm having trouble recognizing what exactly constitutes an LL grammar.

  • $\begingroup$ Have you tried applying the definition? Where did you get stuck? Have you studied the definition? What resources/textbooks have you consulted? What prevents you from figuring out the answer on your own? We're happy to help you understand concepts but just solving this particular exercise for you is unlikely to achieve that. $\endgroup$
    – D.W.
    Apr 11 '18 at 20:27

An LL grammar is a grammar that can be parsed by an LL parser. An LL parser is a parser which parses input from Left-to-right and constructs a Leftmost derivation of the sentence. (https://en.wikipedia.org/wiki/LL_grammar).

The explanation is still a bit confusing, so it's easier to think of it that by looking at only a portion of the input string, we can predict exactly which production rule to apply.

In the grammar you've given: $L(aa^*ba) \cup L(abbb^*)$

which has the production rules:

$$S \rightarrow aAba | abbB$$ $$A \rightarrow aA | \lambda$$ $$B \rightarrow Bb | \lambda$$

this grammar is the union of all strings which start with either an arbitrary amount of $a$'s or an $ab$.

Remember what I mentioned earlier about LL grammars parsing strings from left to right, and that we'd be able to predict which production rule to use by looking at a portion of the input string? This specific grammar satisfies these properties, and is therefore LL.

Let's look at an example:

Say we're given the strings $aaaaaba$ and $abbbbb$. Starting from the left, how many input characters must we read to see which production rule to use?

The answer is two.

All strings in the grammar $L(aa^*ba) \cup L(abbb^*)$ start with an $a$, and if the second character of the input string is also an $a$, then we must use the production

$$S \rightarrow aAba$$

and if the second character is a $b$ then we must use the production

$$S \rightarrow abbB$$

The only basic concept to keep in mind when dealing with LL grammars is whether or not you can accurately predict which production rule to use when only looking at a portion of the string.

I hope this helped, and if I either missed something or didn't explain sufficiently please feel free to correct me.


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.