0
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sylvain
    Nov 20, 2011 at 22:57
  • $\begingroup$ @Sylvain: Regular grammars are different from regular sets. $\endgroup$
    – Tsuyoshi Ito
    Nov 20, 2011 at 23:01
  • $\begingroup$ @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. $\endgroup$
    – Sylvain
    Nov 20, 2011 at 23:10
  • $\begingroup$ @Sylvain: I think that the wording of the question is clear in that it asks about a classification of grammars, not languages. $\endgroup$
    – Tsuyoshi Ito
    Nov 20, 2011 at 23:19
  • $\begingroup$ @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. $\endgroup$
    – Sylvain
    Nov 20, 2011 at 23:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.