2
$\begingroup$

Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this stuff. If anyone can offer help that would be wonderful.

3 Answers 3

6

$(aa+\lambda)(aaaaa)^*$ should do.

  • 0
    It corresponds to `(aa)?(aaaaa)*` in the regex parlance.2012-03-20
2

Another answer, which is typically the first one in textbook order, is to build an automaton on 5 states, that keeps track the number of $a$'s mod 5. To do this, just number the states $0,1,2,3,4$ and transition from $i$ to $i+1\mod 5$ when reading an $a$.

Then $0$ is the start state and $\{0,2\}$ are accepting.

The point of this question is basically that regular languages are, in a certain sense, the ones that require finite memory. When you get to proving non-regularity, you'll learn how to make this precise.

1

What non-negative integers are congruent to $0$ or $2$ modulo $5$: all of the multiples of $5$, and everything that’s $2$ more than a multiple of $5$. In other words, you want words of the forms $a^{5n}$ and $a^{5n+2}$ for integers $n\ge 0$. To get words of the form $a^{5n}$, just start with $\lambda$, the empty word, and add $aaaaa$ as many times as you want, including none at all. That sounds like the star operation, right? These words are described by the regular expression $(aaaaa)^*$.

Now what about the other batch? They’re just like these, but with an extra $aa$ tacked on, so they’re described by either of the regular expressions $(aaaaa)^*aa$ and $aa(aaaaa)^*$. To get both collections, you need the disjunction (‘or’) operation. I don’t know exactly what symbolism you’re using, but it’s probably written either $+$ or $|$, though it might be written $\lor$; I’ll use $|$. Then your language is described by any of the following regular expressions:

$\begin{align*}&(aaaaa)^*\mid (aaaaa)^*aa\\ &(aaaaa)^*\mid aa(aaaaa)^*\\ &(aaaaa)^*aa\mid (aaaaa)^*\\ &aa(aaaaa)^*\mid (aaaaa)^*\\ &(aaaaa)^*(\lambda\mid aa)\\ &(aaaaa)^*(aa\mid\lambda)\\ &(\lambda\mid aa)(aaaaa)^*\\ &(aa\mid\lambda)(aaaaa)^* \end{align*}$

The last four are obtained from the first four by factoring out the $(aaaaa)^*$ that appears in both terms of each of the first four.

If you’ve already learnt the equivalence between regular languages and languages recognizable by finite state automata, another way to show that this language is regular is to design an FSA that recognizes it. That also is very easy, involving a ring of five states, two of which are acceptor states, but I’ll leave that in abeyance unless you ask.