NFA to DFA

"Shane O'Neill" <onesecond@oceanfree.net>
11 Apr 2000 14:31:48 -0400

          From comp.compilers

Related articles
NFA to DFA onesecond@oceanfree.net (Shane O'Neill) (2000-04-11)
Re: NFA to DFA johnston.p@worldnet.att.net (Paul Johnston) (2000-04-14)
Re: NFA to DFA bburshte@pyrps5.eng.pyramid.com (1991-10-09)
| List of all articles for this month |

From: "Shane O'Neill" <onesecond@oceanfree.net>
Newsgroups: comp.compilers
Date: 11 Apr 2000 14:31:48 -0400
Organization: ntl News Service
Keywords: lex, question

Hi,


I've started to reading about compiler construction pretty recently,
and have been trying to get my head around lexical analysis. Anyway
the book I'm reading has exercises in it, though it doesn't give any
answers. One of the questions is to convert the NFA below into DFA,
which I've done. Not sure if I'm on the right track or not, as I
don't know if it's correct.


If anyone could let me know if I'm doing things right or not, that
would be a great help.




Cheers,
      Shane.




0 = e-closure
* = Accepting state


NFA


              | a b 0
        ---|-------------------
          1 | {1} {3} {4}
          2 | {2} {1} {}
* 3 | {1} {4} {2}
          4 | {3} {2} {}






DFA


                      | a b 0
          ------|--------------------------
          [1,4] | [1,3,4] [2,3,4] [4]
* [1,3,4] | [1,2,3,4] [2,3,4] [2,4]
* [2,3,4] | [1,2,3] [1,2,4] [2]
              [4] | [3] [2] []
*[1,2,3,4] | [1,2,3,4] [1,2,3,4] [2,4]
          [2,4] | [2,3] [1,2] []
* [1,2,3] | [1,2,4] [1,2,3,4] [2,4]
      [1,2,4] | [1,2,3,4] [1,2,3,4] [4]
              [2] | [2] [1] []
* [2,3] | [1,2] [1,2,4] [2]
          [1,2] | [1,2,4] [1,3,4] [4]
              [1] | [1,4] [3,4] [4]
* [3,4] | [1,2,3] [2,4] [2]


Post a followup to this message

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