Return to Answer

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.

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.

There 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.

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.

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 ate 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.

There 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.