Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.

$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$

Is my hypothesis true or is this language parseable with an LL(1) parser?

One can use this simple grammar to describe $L$ (of course it is isn't LL(1) parseable):

S -> ε
S -> A
A -> aA
A -> aAb
A -> a
A -> ab

Kurki-Suonio has shown some helpful properties [1]:


Theorem 1

Each LL(k) grammar is unambiguous.

That means any inherently ambiguous language is not LL(1).


Theorem 9

For any $k>1$ the grammar $G$:


$\qquad \begin{align}
S &\to aSA \mid \varepsilon \\
A &\to a^{k - 1} b S \mid c
\end{align}$


generates an LL(k) language which is no LL(k-1) language.

There you have another concrete example by setting $k=2$.

As for your language $L$, assume $L$ is LL(1) and consider the language

$\qquad \displaystyle L' = \{ a^nb^m \mid n 0 \}$.

We make the following observations:

-
$L'$ is LL(1) by the grammar

$\qquad \begin{align}
S &\to AbB \\
A &\to aAb \mid \varepsilon \\
B &\to bB \mid \varepsilon
\end{align}$

• Neither $L$ nor $L'$ is regular (by Pumping Lemma).

• $L \cap L' = \emptyset$.

• $L \cup L' = \{a^nb^m \mid n,m \in \mathbb{N}\} \in \mathsf{REG}$.

In unison, these facts contradict this theorem [2]:


Theorem 9

If the finite union of disjoint LL(k) languages is regular, then all the languages are regular.

Thus, $L$ can not be LL(1) (and in fact not LL(k) for any k).

• Notes on top-down languages by R. Kurki-Suonio (1969)

• Properties of deterministic top-down grammars by D.J. Rosenkrantz and R.E. Stearns (1970)

StackExchange Computer Science Q#3350, answer score: 5