Is there a DFA with $k+2$ states which its reverse has $2^k$ states

195 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

Hint:

No DFA with fewer than $2^k$ states can recognize the language $C_k$ consisting of all strings of $a$ and $b$ that have an $a$ in the $k$th position from the end.