|[2 earlier articles]|
|Re: Theory about DFA's and f?lex start states firstname.lastname@example.org (2000-11-09)|
|Re: Theory about DFA's and f?lex start states email@example.com (2000-11-11)|
|Re: Theory about DFA's and f?lex start states firstname.lastname@example.org (Chris F Clark) (2000-11-14)|
|Re: Theory about DFA's and f?lex start states email@example.com (Joachim Durchholz) (2000-11-14)|
|Re: Theory about DFA's and f?lex start states firstname.lastname@example.org (Jonathan Barker) (2000-11-14)|
|Re: Theory about DFA's and f?lex start states email@example.com (2000-11-14)|
|Re: Theory about DFA's and f?lex start states firstname.lastname@example.org (2000-11-19)|
|Re: Theory about DFA's and f?lex start states email@example.com (Chris F Clark) (2000-11-21)|
|Re: Theory about DFA's and f?lex start states firstname.lastname@example.org (Joachim Durchholz) (2000-11-21)|
|Re: Theory about DFA's and f?lex start states email@example.com (2000-11-22)|
|Date:||19 Nov 2000 20:28:28 -0500|
|Organization:||Deja.com - Before you buy.|
|References:||00-11-073 00-11-080 00-11-083 00-11-100|
|Posted-Date:||19 Nov 2000 20:28:28 EST|
"Jonathan Barker" <firstname.lastname@example.org> wrote:
[snip of good analysis]
> The key point here is that a set of DFAs is the same as one big
> DFA. If I'm wrong, I expect that you'll find that a DPDFA is
> equivalent to one of the other well-known models of computation.
> It's just a matter of finding out which.
You have hit on some key points. One /can/ theoretically combine the
set of DFA's over M to generate D.
But stepping back from a practical standpoint for a second: Assume I'm
a developer writer trying to write a grammar for my new language. I'm
struggling to write the lexer because I've overloaded the syntax to
the point that I can't seem to achieve what I want because many of the
tokens have overlapping definitions (they cause conflicts in the
DFA). So the (natural?) thing is to try to partition those token
definitions into several distinct layers and switch between them when
The point I'm trying to make is that notion of "mode" arises from the
difficulty of trying to generate D from the set M.
This is not to say that one cannot find an alternative grammar that
/would/ be conflict-free. In many cases, people use this approach
because it is mentally less challenging to make several modes (states,
layers, contexts, whatever...) and switch between them rather than to
try to find a conflict-free grammar. But in other cases, I think that
no amount of wrangling can generate a deterministic automaton capable
of recognizing the prescribed tokens. They just conflict, and there's
no getting around it (I conjecture).
So what model of computation is this? I'm not too sure (the reason
for my original post). Given the additional thought, I think the
point of using stack instructions for switching between the elements
in M (DPDFA) versus explicit goto instructions (like flex) is not too
relevant. The important thing is that you have multiple "exclusive"
DFA's (using the word "exclusive" to mean that merging them would
cause conflicts) and that you are switching between them.
Taken to an extreme, it seems to "degenerate" into Turing behavior
(according to my gut). Each DFA looks like a procedure which contains
statements that call other procedures. In this case however there is no
concept of a return statement since a DFA never really ever "completes"
(it just keeps running until another procedure call is found).
Any thoughts? Mine are increasingly less productive as it is nearly
Return to the
Search the comp.compilers archives again.