4

In the picture below can I use both NFA interchangeably? If not then why?

enter image description here

Dennis Grinch
  • 353
  • 3
  • 13

1 Answers1

5

Yes, they are equivalent (they recognize the same language). More formally:

First, let's give names to your states:

Original DFA from Thompson's algorithm

Now, through powerset construction, let's remove the epsilon transitions:

enter image description here

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.

enter image description here enter image description here enter image description here

rcpinto
  • 4,166
  • 2
  • 24
  • 25