Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is the language $\lbrace (aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N} \rbrace$ regular? It looks like I need infinitely many states so it is not regular.

share|improve this question
    
This is solvable by basic techniques, so you should definitely include more of your own thoughts. In particular, try proving your claim. Either that works or you find out why not, which helps proving the converse. –  Raphael Feb 11 '13 at 12:05
add comment

2 Answers 2

The language consists of those strings that contain $5 n + 2 + 5 n = 10 n + 2$ symbols $a$ for some $n \in \mathbb{N}$, i.e., $$\lbrace(aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N}\rbrace = \lbrace (aaaaaaaaaa)^n aa \mid n \in \mathbb{N} \rbrace.$$ It is regular because it is accepted by the automaton which has twelve states $s_0, \ldots, s_{11}$ with a starting state $s_0$, accepting state $s_2$, and transitions $s_i \stackrel{a}{\longrightarrow} s_{i+1}$ for each $i = 0, \ldots, 10$, and one more transition $s_{11} \stackrel{a}{\longrightarrow} s_0$. In essence, this automaton counts the number of letters modulo 10 and accepts if the answer is 2.

share|improve this answer
    
I think that any language of the form $a^{e_1}a^{e_2}a^{e_3}a^{e_4}a^{e_5}\dots$, where the $e_i$'s are natural numbers, is regular. –  saadtaame Feb 11 '13 at 13:04
    
What do you mean? If you put in those $a^n$ for which the $n$-th Turing machine halts, you get an undecidable set, let alone regular. See Yuval's answer. –  Andrej Bauer Feb 13 '13 at 6:16
    
Just rearrange the expression like you did in the example and you get an automaton for the expression! –  saadtaame Feb 13 '13 at 9:26
    
But it is not clear what you mean by $a^{e_1} a^{e_2} a^{e_3} \cdots$. Can there be infinitely many $e_i$? What do $e_i$ depend on, are they functions of some $n$, or what? –  Andrej Bauer Feb 14 '13 at 5:54
    
The expression is finite in length, the $e_i$'s $\in\mathbb{N_0}$. –  saadtaame Feb 14 '13 at 12:28
show 7 more comments

We can prove a more general theorem. The language $\{ a^n : n \in A \}$ is regular if and only if the set $A$ is eventually periodic, i.e. there exist $m$ and $k$ such that for all $n \geq m$, $n \in A$ iff $n+k \in A$.

Indeed, a language of this form is clearly regular. For the other direction, consider a DFA accepting the language. It has outdegree $1$ and so must consist of a path leading into a cycle. Given that representation, we see that it can be represented using an eventually periodic $A$.

share|improve this answer
    
Or, simpler (to apply here): $\mathrm{CFG} \cap 2^{\{a\}^*} \subseteq \mathrm{REG}$ –  Raphael Feb 12 '13 at 6:31
    
@YuvalFilmus What sets are eventually periodic other than $\mathbb N$? –  saadtaame Feb 12 '13 at 16:36
3  
The set of even numbers. The set of odd numbers. The set of even numbers larger than 57. And so on. –  Yuval Filmus Feb 12 '13 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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