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.
-
$\begingroup$ 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. $\endgroup$– RaphaelFeb 11, 2013 at 12:05
2 Answers
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.
-
$\begingroup$ 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. $\endgroup$– mrkFeb 11, 2013 at 13:04
-
$\begingroup$ 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. $\endgroup$ Feb 13, 2013 at 6:16
-
$\begingroup$ Just rearrange the expression like you did in the example and you get an automaton for the expression! $\endgroup$– mrkFeb 13, 2013 at 9:26
-
$\begingroup$ 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? $\endgroup$ Feb 14, 2013 at 5:54
-
$\begingroup$ The expression is finite in length, the $e_i$'s $\in\mathbb{N_0}$. $\endgroup$– mrkFeb 14, 2013 at 12:28
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$.
-
$\begingroup$ Or, simpler (to apply here): $\mathrm{CFG} \cap 2^{\{a\}^*} \subseteq \mathrm{REG}$ $\endgroup$– RaphaelFeb 12, 2013 at 6:31
-
$\begingroup$ @YuvalFilmus What sets are eventually periodic other than $\mathbb N$? $\endgroup$– mrkFeb 12, 2013 at 16:36
-
3$\begingroup$ The set of even numbers. The set of odd numbers. The set of even numbers larger than 57. And so on. $\endgroup$ Feb 12, 2013 at 16:37