In the picture below can I use both NFA interchangeably? If not then why?
Asked
Active
Viewed 575 times
1 Answers
5
Yes, they are equivalent (they recognize the same language). More formally:
First, let's give names to your states:
Now, through powerset construction, let's remove the epsilon transitions:
Finally, we can use any DFA minimization algorithm such as Brzozowski's (reverse the arrows, apply powerset construction again, re-reverse the arrows) to obtain your resulting DFA.

rcpinto
- 4,166
- 2
- 24
- 25
-
which tool you use? – Grijesh Chauhan Jul 21 '16 at 09:40