<p>By saturated I mean that the grammar accepts every possible string
that can be constructed from the terminal set. So the parse table would
be full of valid entries, no error entries at all. Can such a grammar
be known to also be included in a more restrictive class, such as
regular for example?</p>

<p>The following grammar is what motivates this question.</p>

<pre><code>A1 --&gt; A2 a
A1 --&gt; A2 b
A2 --&gt; A3 a
A2 --&gt; A3 b
A3 --&gt; A4 a
A3 --&gt; A4 b
    . 
    . 
    . 
Ak --&gt; a
Ak --&gt; b
</code></pre>

<p>Clearly since the grammar is left-linear we know that it is LL(k) as
well. Can anything be deduced from the other direction. That is, by
knowing that the grammar is saturated LL(k), can we say that it is
also regular? Does the saturated property imply anything useful about
the grammar?</p>

CC BY-SA 3.0
2011-11-20T22:57:17.850Z
If $\Sigma$ is the terminal alphabet, then $\Sigma^\ast$ is a regular set.  Your example grammar looks like it recognizes $\Sigma^k$, which is finite and thus regular, instead. Being left-linear is not sufficient to be LL$(k)$: for instance the grammar could be left-recursive.
Sylvain
CC BY-SA 3.0
2011-11-20T23:01:30.563Z
@Sylvain: [Regular grammars](http://en.wikipedia.org/wiki/Regular_grammar) are different from regular sets.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-20T23:10:25.910Z
@Tsuyoshi Ito: You are right to point out that any left-linear grammar derives a regular set, which should be helpful to the poster.  It is actually unclear to me what was initially meant by "regular" in the question, i.e. regular language or regular grammar.
Sylvain
CC BY-SA 3.0
2011-11-20T23:19:32.303Z
@Sylvain: I think that the wording of the question is clear in that it asks about a classification of grammars, not languages.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-20T23:39:36.693Z
@Tsuyoshi Ito: in that case I can think of a LL$(1)$ grammar for $\Sigma^\ast$ which is not a linear grammar: $S\to AS\mid\varepsilon$ with $A\to a$ for each $a$ in $\Sigma$. Not a very interesting answer though.
Sylvain
CC BY-SA 3.0
2011-11-20T23:49:20.760Z
@Sylvain: What is the point of arguing that toward me?  I stand behind my words: I think that the wording of the question is clear in that it asks about a classification of grammars, not languages.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-20T23:53:28.823Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1823/discussion-between-sylvain-and-tsuyoshi-ito)
Sylvain
<fl.formal-languages><grammars>
Classification of Saturated LL(1) Grammars
slkpg
# Classification of Saturated LL(1) Grammars

(Asked by: username_0 on 2011-11-20)

By saturated I mean that the grammar accepts every possible string
that can be constructed from the terminal set. So the parse table would
be full of valid entries, no error entries at all. Can such a grammar
be known to also be included in a more restrictive class, such as
regular for example?
The following grammar is what motivates this question.
A1 --> A2 a
A1 --> A2 b
A2 --> A3 a
A2 --> A3 b
A3 --> A4 a
A3 --> A4 b
    . 
    . 
    . 
Ak --> a
Ak --> b

Clearly since the grammar is left-linear we know that it is LL(k) as
well. Can anything be deduced from the other direction. That is, by
knowing that the grammar is saturated LL(k), can we say that it is
also regular? Does the saturated property imply anything useful about
the grammar?

**Tags:** fl.formal-languages, grammars

> **Comments:**
> **username_1**: If $\Sigma$ is the terminal alphabet, then $\Sigma^\ast$ is a regular set.  Your example grammar looks like it recognizes $\Sigma^k$, which is finite and thus regular, instead. Being left-linear is not sufficient to be LL$(k)$: for instance the grammar could be left-recursive.  
> **username_2**: @username_1: [Regular grammars](http://en.wikipedia.org/wiki/Regular_grammar) are different from regular sets.  
> **username_1**: @username_2: You are right to point out that any left-linear grammar derives a regular set, which should be helpful to the poster.  It is actually unclear to me what was initially meant by "regular" in the question, i.e. regular language or regular grammar.  
> **username_2**: @username_1: I think that the wording of the question is clear in that it asks about a classification of grammars, not languages.  
> **username_1**: @username_2: in that case I can think of a LL$(1)$ grammar for $\Sigma^\ast$ which is not a linear grammar: $S\to AS\mid\varepsilon$ with $A\to a$ for each $a$ in $\Sigma$. Not a very interesting answer though.  
> **username_2**: @username_1: What is the point of arguing that toward me?  I stand behind my words: I think that the wording of the question is clear in that it asks about a classification of grammars, not languages.  
> **username_1**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1823/discussion-between-sylvain-and-tsuyoshi-ito)  

---

## 0 answers

