1
$\begingroup$

I came across following:

Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.

I tried to get that.

Definition: Right linear grammar (RLG)
In right linear grammar, all productions are of one of the following forms: $A\rightarrow t^*V$ or $A\rightarrow t^*$, where $A$ and $V$ are non terminals and $t$ is terminal.

Definition: LL(1) grammar

A grammar $G$ is $LL(1)$ grammar if and only if whenever $A→α|β$ are two distinct productions of $G$, the following conditions hold:

  1. For no terminal $a$ do both $α$ and $β$ derive strings beginning with $a$.
  2. At most one of $α$ and $β$ can derive the empty string.
  3. If $β⇒^*ϵ$, then $α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $α⇒^*ϵ$, then $β$ does not derive any string beginning with a terminal in FOLLOW(A). ($β⇒^*ϵ$ means $B$ derives $\epsilon$)

(Q1.) How definition of RLG ensures condition 1 in the definition of LL(1) grammar.

This answer says:

All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.

(Q2.) I read somewhere "eliminating left recursion from given grammar does not necessarily make it LL(1)". Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?

(Q3). I didnt get the significance of "one produces ε and has $ as a lookahead token" in above quoted answer.

(Q4.) First quote in this question says right linear grammar is LL(1). How is it so?

(Q5.) This answer says "all regular languages have a LR(0) grammar", I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?

$\endgroup$
4
  • $\begingroup$ Your Q5 is not really related to the rest of the question. The answer to Q5 is that the quoted sentence in the answer is incorrect. That happens. SO does not guarantee the answers it hosts. (Don't take that the wrong way. It's normal; you always need to apply judgement. History --up to today-- is full of large organizations, commercial and otherwise, publishing statements which are untrue. Sometimes the untruth of the statement was known at the time; sometimes it was discovered afterwards, and sometimes it was just the result of an uncorrected typo.) $\endgroup$
    – rici
    Dec 25, 2019 at 20:06
  • $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Dec 26, 2019 at 3:55
  • $\begingroup$ @rici yes Q5 was somewhat not related, but I got confused. I understand answers may go wrong. $\endgroup$
    – Maha
    Dec 26, 2019 at 10:46
  • $\begingroup$ @D.W. sorry for that, I asked those questions to tackle original question from different directions to help me have clear understanding $\endgroup$
    – Maha
    Dec 26, 2019 at 10:47

2 Answers 2

5
$\begingroup$

The quoted answer does not claim that every right regular grammar is LL(1). That statement would not be true.

What the answer claims is that the grammars produced by the indicated algorithm are LL(1). That statement is correct.

So, no-one is saying "every right-linear grammar" satisfies condition 1 (of the LL(1) definition) (your Q1). They don't all do so.

Alos, no-one is saying that just removing left-recursion is sufficient to guarantee LL(1) (your Q2). It isn't.

Finally, no-one is saying that every RLG is LL(1) (your Q4), not even the unattributed quote which starts your question. That quote says that every regular language has at least one RLG which is LL(1). Regular languages have many RLGs, and often not all of them are LL(1). These other RLGs are not relevant to the claim that all regular languages are LL(1).

That leaves your Q3, which is really about how to demonstrate the RLG produced by the algorithm satisfies conditions 2 and 3.

It's clear why that particular RLG passes condition 1. The algorithm starts with a DFA, and the DFA has only one out-transition on each symbol, by definition. One production is generated for each out-transition, whose first symbol is the out-transition's symbol. So it's not possible for two productions starting with the same symbol to be generated for the same state (= non-terminal).

Now, under what circumstances does the algorithm produce productions which derive $\epsilon$? Answer: these productions are generated for final states. @templatetypedef wrote the quoted answer thinking about the augmented grammar/language, in which every sentence ends with an end-marker $ which does not appear elsewhere. [Note 1]

Instead of augmenting the grammar or writing the LRG as implied by the cited answer, we could invent a new state F with no out-transitions on any symbol. We then add the production $A\to F$ to every final state $A$. And we add the production $F\to\epsilon$.

Now condition 2 is met becaus the only unit productions in the grammar are $A\to F$, so no non-terminal derives $\epsilon$ in any way other than directly through $F$. And condition 3 is met rather trivially because $FOLLOW$ of every non-terminal is empty, so no terminal is in any $FOLLOW$ set.

Since conditions 1, 2 and 3 are verified, we know that the grammar produced by converting a DFA is necessarily LL(1).


Notes

  1. This augmented language is prefix-free, since all sentences end with the endmarker. Also, as we'll see, the augmented grammar produced by the algorithm is LL(1) and therefore deterministic. A deterministic prefix-free language is LR(0), which might explain the error you refer to in your Q5. The original unaugmented grammar is not necessarily prefix-free, and therefore might not be LR(0) although it is still LL(1). This is an illustration of why augmented grammars are useful.
$\endgroup$
8
  • $\begingroup$ So, @rici, (as you might have guessed that I at times face difficulty in understanding the meaning of (probably obvious) statements), as you say that the quotation at the beginning of the statement is not right. So can we say $\text{There exists at least one regular language for which we cannot write a LL(1) grammar}$. Because I tried to come up with an $LL(1)$ grammar for the language $L=a^*$ but could not possibly succeed.... $\endgroup$ Jan 11 at 21:15
  • 1
    $\begingroup$ @abhishek: I didn't say that the quotation at the beginning of the question is wrong, exactly. At best, it is badly phrased. What is correct is that every regular language has an LL(1) grammar. It is also true (by definition) that every regular language has a right regular grammar. What is not correct is that every right regular grammar is LL(1), which is clearly a different statement. Because every regular language has an LL(1) grammar, the set of LL(1) languages includes all regular languages. $\endgroup$
    – rici
    Jan 11 at 22:05
  • 1
    $\begingroup$ As for $\{a^*\}$, what's not LL(1) about $S\to A; A\to a A; A\to\epsilon$? $\endgroup$
    – rici
    Jan 11 at 22:07
  • 1
    $\begingroup$ The statement I said was incorrect is that all regular languages have an LR(0) grammar, although one could say that it is "only technically incorrect". If you add an explicit endmarker to every sentence in a language, then the resulting modified language has the "prefix property", and a regular language with the prefix property is LR(0). (The prefix property is that no sentence in the language is a proper prefix of a different sentence in the language.) In practice, it's common to augment input with an explicit endmarker; in that context, every regular language is LR(0). But not in general. $\endgroup$
    – rici
    Jan 11 at 22:14
  • 1
    $\begingroup$ @AbhishekGhosh: I'm afraid that I don't have a library of textbooks to consult :-) Over the years, I've been increasingly annoyed by the proliferation of academic paywalls which demand truly exorbitant ransoms for releasing little tidbits of ancient knowledge. For me, it's just an annoyance; I was fortunate to be learning at a time when access to knowledge, at least in Canada, was relatively ungated. So I'm deeply sympathetic, but not really in a position to help. If you have access to an academic library, use it. (I don't, unfortunately.) $\endgroup$
    – rici
    Jan 13 at 2:43
0
$\begingroup$

Let's consider a restricted type of right-regular grammar: all rules must be of the form

  • $X \rightarrow yZ$
  • $X \rightarrow \epsilon$

Such a grammar directly corresponds to a nondeterministic automaton:

  • the nonterminals correspond to states
  • the start symbol corresponds to the initial state
  • the $\epsilon$-rules corresponds to the state being accepting
  • the other rules corresponds to transitions
  • the grammar generating a word corresponds to the automaton accepting that word

It is a special kind of nondeterministic automaton: one in which all transitions are on single symbols; no $\epsilon$ transitions.

It is a 1 to 1 mapping: every such automaton corresponds to such a grammar.

Such a grammar is LL(1) if and only if its corresponding automaton is deterministic. Once again, the correspondence is 1 to 1: every deterministic automaton corresponds to such a grammar.

We know deterministic automata can accept all regular languages. Hence, LL(1) right-linear grammars (of this restricted type) can generate all regular languages.

$\endgroup$

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.