5
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ If you're not sure, try to construct one. Don't take the constant 3 too seriously. $\endgroup$ – Yuval Filmus Aug 26 '16 at 19:03
  • $\begingroup$ @YuvalFilmus - I added a clarification for the semantics. And yes, I tried constructing one, but failed. I understand that CDFA can gather some information with every run over the input, but can't find properties than could be remembered by single run and which, combined, would tell CDFA what is the $n-th$ symbol. $\endgroup$ – socumbersome Aug 26 '16 at 19:17
  • $\begingroup$ ...what does it mean "CDFA accepts iff during reading symbol $@$ it is in accepting state."? Since you said that it reads $@$ infinite times which time should be in an accepting state? Every time? At least once? An infinite number of times? A finite number of times? $\endgroup$ – Bakuriu Aug 27 '16 at 8:04
  • $\begingroup$ @Bakuriu - it accepts first time it sees $@$ while being in an accepting state. $\endgroup$ – socumbersome Aug 27 '16 at 8:22
  • $\begingroup$ @socumbersome Which means that it accepts the infinite word $w@w@w@...$ if at least once it reads $@$ while being in an accepting state. $\endgroup$ – Bakuriu Aug 27 '16 at 8:31
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Hint: Try

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

for some set $S$ that you choose to enable you to solve the problem. Can you think of any set $S$ that would make it easy to find a small CDFA for $L$?

$\endgroup$
  • $\begingroup$ This gives $2n + O(1)$ states. $\endgroup$ – Yuval Filmus Aug 26 '16 at 21:22
  • $\begingroup$ Maybe $S = \{kn : k \in \mathbb{N}\}$? Now, CDFA would remember index of character it is reading modulo $n$ and last seen symbol on index divisible by $n$. I can see it will accept words from $L$, but I also see a problem with accepting accidentally words outside $L$ when it runs a few times over a word which length is not divisible by $n$... how to overcome that? $\endgroup$ – socumbersome Aug 27 '16 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.