0
$\begingroup$

I am wondering what generic example there is so that an NFA with n states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft et al. where the resulting DFA has $2^{n-1}$ states but I am looking for a result with exactly 2^n states.

Thanks in advance.

PS: This is not the same question as An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof since there $2^{n-1}$ states suffices but I am looking for $2^n$ states.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The question is answered here by J.-E. Pin. $\endgroup$
    – user6530
    Commented Apr 21, 2021 at 17:26
  • $\begingroup$ Thank you very much $\endgroup$
    – sorry
    Commented Apr 21, 2021 at 19:26
  • $\begingroup$ Please don't re-post your question multiple times: cs.stackexchange.com/q/139174/755 $\endgroup$
    – D.W. ♦
    Commented Apr 23, 2021 at 0:01

0

Reset to default

Browse other questions tagged or ask your own question.