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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you're not sure, try to construct one. Don't take the constant 3 too seriously. $\endgroup$
    – Yuval Filmus
    Commented Aug 26, 2016 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
    Commented Aug 26, 2016 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
    Commented Aug 27, 2016 at 8:04
  • $\begingroup$ @Bakuriu - it accepts first time it sees $@$ while being in an accepting state. $\endgroup$
    – socumbersome
    Commented Aug 27, 2016 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
    Commented Aug 27, 2016 at 8:31

2 Answers 2

Reset to default
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.

Improve this answer
$\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$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ This gives $2n + O(1)$ states. $\endgroup$
    – Yuval Filmus
    Commented Aug 26, 2016 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
    Commented Aug 27, 2016 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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