3
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – Raphael
    Feb 11, 2013 at 12:05

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
12
  • $\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$
    – mrk
    Feb 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$
    – mrk
    Feb 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$
    – mrk
    Feb 14, 2013 at 12:28
6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Or, simpler (to apply here): $\mathrm{CFG} \cap 2^{\{a\}^*} \subseteq \mathrm{REG}$ $\endgroup$
    – Raphael
    Feb 12, 2013 at 6:31
  • $\begingroup$ @YuvalFilmus What sets are eventually periodic other than $\mathbb N$? $\endgroup$
    – mrk
    Feb 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

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.