0
$\begingroup$

For the language L = $\{\Sigma^*. 0 .\Sigma^5 . 1. \Sigma^*\}$

The NFA must have 8 states. Also, what would be the upper bound on the number of states of a DFA recognizing L.

enter image description here

  • 1
    The NFA looks good, though you should have said that $\Sigma=\{0,1\}$. There is no **upper** bound on the number of states of a DFA recognizing $L$; did you mean **lower** bound?2012-11-08
  • 1
    The minimal automaton of your language has 65 states. Thus any DFA accepting your language will have at least 65 states.2016-02-03

1 Answers 1