# Does this constitute as an LL grammar?

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.

• 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.
– 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?

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$$