World's most popular travel blog for travel bloggers.

[Solved]: Is there a DFA with $k+2$ states which its reverse has $2^k$ states

, , No Comments
Problem Detail: 

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.
I am trying to find an example of such a DFA, any help?

Asked By : DaniaG.

Answered By : Hendrik Jan

This is related to the usual NFA to DFA complexity problem. Strings over $\{a,b\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|>1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18648

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback