[Solved]: Cyclic deterministic finite automata, exponential advantage over DFA

Problem Detail: 

Let's define Cyclic deterministic finite automata (CDFA) as a DFA that treats its input a bit differently -- namely, CDFA when given input $w$, firstly transforms its input into $w@$, where $@$ is a special character outside the alphabet that acts as a loop, gluing end of $w$ to the beginning of $w$. So, when CDFA reads $@$ and is currently in state $q$, it then reads whole input (i.e. $w@$) again (so CDFA acts as if it was reading infinite word $w@w@w@w@\ldots$), starting this time from the state $q$. CDFA accepts iff during reading symbol $@$ it is in accepting state.

How to show the following:

For every $n$ natural, there is language $L_n$ and CDFA $C_n$ such that $C_n$ has less than $3n$ states, but every DFA recognizing $L_n$ has at least $2^n$ states.

?

I tried firstly to find some regular language that I know requires approximately $2^n$ states, but the only candidate that springs to my mind is

$L = \{w \in \{0,1\}^{\star} : \text{n-th symbol counting from the end is 0}\}$

However, I'm not sure whether there exists CDFA having less than $3n$ states. To be honest, I have no idea why it is $3n$ and not other $kn$.

Asked By : socumbersome

Answered By : Yuval Filmus

Let $\Sigma$ be an alphabet of size $n$, and consider the language $L_n$ of all words over $\Sigma$ which contain all letters of the alphabet. It is well-known that the minimal DFA for $L_n$ contains $2^n$ states. On the other hand, $L_n$ is accepted by a CDFA with $n+1$ states.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents