Search code examples
regexdiscrete-mathematicsdfanfaautomaton

Can you skip epsilon transitions in union expression (Thompson's construction algorithm)


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

enter image description here


Solution

  • 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