Compilers NFA to DFA
Alex Aiken
NFA to DFA
NFA Regular expressions
DFA
Lexical Specification
Table-driven Implementation of DFA Alex Aiken
NFA to DFA
A
B
C D
1 0
E F
G
H
I
1
J
Alex Aiken
NFA to DFA
• An NFA may be in many states at any time • How many different states?
Alex Aiken
NFA to DFA
Alex Aiken
NFA to DFA
A
B
C 1
D 0
0 1
F
G
FGHIABCD
0 ABCDHI
E
1 EJGHIABCD
H
I
1
J
0 1 Alex Aiken
1
NFA to DFA
0
0
1 0
1
0
0
1 0 0
1 0
Choose the DFA that represents the same language as the given NFA
0 1 0 1