Re: Limits of regular languages

Max Hailperin <>
Sat, 13 Feb 2010 17:01:00 -0600

          From comp.compilers

Related articles
Limits of regular languages (e0726905) (2010-02-11)
Re: Limits of regular languages (Matthias-Christian Ott) (2010-02-13)
Re: Limits of regular languages (Kaz Kylheku) (2010-02-13)
Re: Limits of regular languages (Chris F Clark) (2010-02-13)
Re: Limits of regular languages (Max Hailperin) (2010-02-13)
Re: Limits of regular languages (e0726905) (2010-02-27)
| List of all articles for this month |

From: Max Hailperin <>
Newsgroups: comp.compilers
Date: Sat, 13 Feb 2010 17:01:00 -0600
Organization: Compilers Central
References: 10-02-052
Keywords: lex, DFA
Posted-Date: 13 Feb 2010 19:39:34 EST

e0726905 <> writes:
> ...Is every regular language LL(1)? ...

Yes, this can be shown by an algorithm for constructing an LL(1)
grammar from any DFA. The grammar should have one nonterminal symbol
for each state in the DFA and one terminal symbol for each symbol in
the DFA's alphabet. The nonterminal corresponding to the start state
is the start symbol of the grammar. For each transition edge in the
DFA, say from S1 to S2 labeled with x, include a corresponding

S1 -> x S2

Additionally, for every accepting state in the DFA, say A, include a
corresponding epsilon production:

A -> epsilon

To show this is an LL(1) grammar, you need to show the various
productions that share any particular left hand side have disjoint
FIRST sets for their right hand sides, and that if there is an epsilon
production, the FOLLOW set of the right hand side is also disjoint
from the various FIRST sets. In the constructed grammar, each
production of the form

S1 -> x S2

has just {x} for its FIRST set, and since the automaton was
deterministic, these must be disjoint. Also, given the form of the
productions, you can show that FOLLOW(A) = {$} for any (reachable)
nonterminal A, where $ is an end-of-input marker that must be
different from each of the alphabetic symbols labeling the

To show that the grammar generates the same language as the DFA
recognizes, you would show that the parse trees of the grammar are in
a straightforward one-to-one correspondence with accepting paths
through the DFA.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.