# 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" Newsgroups: comp.compilers Date: 11 Apr 2000 14:31:48 -0400 Organization: ntl News Service Keywords: lex, question

Hi,

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