patternModerate
Is $(aaaaa)^n aa (aaaaa)^n$ a regular language?
Viewed 0 times
aaaaaregularlanguage
Problem
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.
Solution
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.
$$\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.
Context
StackExchange Computer Science Q#9670, answer score: 10
Revisions (0)
No revisions yet.