NFA http://i48.tinypic.com/2lwof1z.png
I'm having trouble understanding how to convert.
If 2 gets an input of 'a' would it become (1,4) or (1,2,4) because of the empty string?
Thanks!
NFA http://i48.tinypic.com/2lwof1z.png
I'm having trouble understanding how to convert.
If 2 gets an input of 'a' would it become (1,4) or (1,2,4) because of the empty string?
Thanks!
If state
Q2
gets an input of 'a' next states may be eitherQ1
,Q2
, 0rQ4
.In your NFA your get final state
Q4
Its equivalent DFA is as below:
Where
Q1
andQ2
are final state.And its Regular Expression is:
a
(a + ba)*
(b + ε )
Where
ε
is null symbol (epsilon)We begin to convert NFA to DFA with identifying empty-input-closure sets (starting from here i will denote empty-input-closure by L-closure).
L(1)=(1,2) We can visit 2 from 1 on empty input.
L(2)=(2) There is no empty input edge out from 2.
L(3)=(3) There is no empty input edge out from 3.
L(4)=(1,2,4) We can visit 1 from 4 and 2 from 1.
If 2 gets an input of 'a', it would become L(1)UL(4)=(1,2,4).
Since our start node is 1 in NFA, in DFA it will be L(1) which is (1,2).
Since 4 is an accept node in NFA, in DFA nodes including 4 will be accept nodes, which are (1,2,3,4) and (1,2,4).