regex2dfa

DFA Generator for Simple Regular Expression (including '*' '|' '(' ')')

Features

• Regex -> NFA
• NFA -> DFA
• DFA Minimization (New)

Examples

Eg.1

regex:
1(1010*|1(010)*1)*0
tree:
('.', ('v', '1'), ('.', ('*', ('|', ('.', ('v', '1'), ('.', ('v', '0'), ('.', ('v', '1'), ('*', ('v', '0'))))), ('.', ('v', '1'), ('.', ('*', ('.', ('v', '0'), ('.', ('v', '1'), ('v', '0')))), ('v', '1'))))), ('v', '0')))
NFA Edges:
1 2 1
2 3 1
3 4 0
4 5 1
5 5 0
5 2 ε
2 6 1
6 7 0
7 8 1
8 6 0
6 2 1
2 9 0
DFA Edges:
[('1', '2', '1'), ('2', '4', '1'), ('2', '3', '0'), ('4', '2', '1'), ('4', '5', '0'), ('5', '6', '1'), ('6', '4', '1'), ('6', '7', '0'), ('7', '15', '1'), ('7', '8', '0'), ('8', '10', '1'), ('8', '9', '0'), ('9', '4', '1'), ('9', '9', '0'), ('10', '2', '1'), ('10', '11', '0'), ('11', '6', '1'), ('11', '12', '0'), ('12', '13', '1'), ('13', '14', '0'), ('14', '2', '1'), ('14', '12', '0'), ('15', '15', '1'), ('15', '16', '0'), ('16', '6', '1')]

NFA 1

DFA 1

Eg.2

regex:
1(0|1)*101
tree:
('.', ('v', '1'), ('.', ('*', ('|', ('v', '0'), ('v', '1'))), ('.', ('v', '1'), ('.', ('v', '0'), ('v', '1')))))
NFA Edges:
1 2 1
2 2 0,1
2 3 1
3 4 0
4 5 1
DFA Edges:
[('1', '2', '1'), ('2', '3', '1'), ('2', '2', '0'), ('3', '3', '1'), ('3', '4', '0'), ('4', '5', '1'), ('4', '2', '0'), ('5', '3', '1'), ('5', '4', '0')]

NFA 2

DFA 2

Eg.3

Unsigned Number

regex:
(dd*|dd*.dd*|.dd*)(ε|10(s|ε)dd*)|10(s|ε)dd*
tree:
('|', ('.', ('|', ('.', ('v', 'd'), ('*', ('v', 'd'))), ('|', ('.', ('v', 'd'), ('.', ('*', ('v', 'd')), ('.', ('v', '.'), ('.', ('v', 'd'), ('*', ('v', 'd')))))), ('.', ('v', '.'), ('.', ('v', 'd'), ('*', ('v', 'd')))))), ('|', ('v', 'ε'), ('.', ('v', '1'), ('.', ('v', '0'), ('.', ('|', ('v', 's'), ('v', 'ε')), ('.', ('v', 'd'), ('*', ('v', 'd')))))))), ('.', ('v', '1'), ('.', ('v', '0'), ('.', ('|', ('v', 's'), ('v', 'ε')), ('.', ('v', 'd'), ('*', ('v', 'd')))))))
NFA Edges:
[['1', '4', 'd'], ['4', '4', 'd'], ['4', '3', 'ε'], ['1', '5', 'd'], ['5', '5', 'd'], ['5', '6', '.'], ['6', '7', 'd'], ['7', '7', 'd'], ['7', '3', 'ε'], ['1', '8', '.'], ['8', '9', 'd'], ['9', '9', 'd'], ['9', '3', 'ε'], ['3', '2', 'ε'], ['3', '10', '1'], ['10', '11', '0'], ['11', '12', 's,ε'], ['12', '13', 'd'], ['13', '13', 'd'], ['13', '2', 'ε'], ['1', '14', '1'], ['14', '15', '0'], ['15', '16', 's,ε'], ['16', '17', 'd'], ['17', '17', 'd'], ['17', '2', 'ε']]
DFA Edges:
[('1', '13', '.'), ('1', '6', 'd'), ('1', '2', '1'), ('2', '3', '0'), ('3', '5', 's'), ('3', '4', 'd'), ('4', '4', 'd'), ('5', '4', 'd'), ('6', '11', '.'), ('6', '6', 'd'), ('6', '7', '1'), ('7', '8', '0'), ('8', '10', 's'), ('8', '9', 'd'), ('9', '9', 'd'), ('10', '9', 'd'), ('11', '12', 'd'), ('12', '12', 'd'), ('12', '7', '1'), ('13', '14', 'd'), ('14', '14', 'd'), ('14', '7', '1')]

NFA 3

DFA 3

Mini DFA 3