Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

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

share|improve this answer
    
Do you need the empty string for this regular expression? Wouldn't $(aa)(aaaaa)^*$ suffice? –  Hunter McMillen Mar 20 '12 at 5:22
    
No, it wouldn’t: it picks up only the words whose lengths are congruent to $2$ mod $5$. –  Brian M. Scott Mar 20 '12 at 5:31
    
I seem to be confused by the notation: is + denoting union here? –  Hunter McMillen Mar 20 '12 at 5:38
    
@Hunter: Technically no: it’s the disjunction operator for regular expressions. However, that corresponds to taking the union of the corresponding languages. –  Brian M. Scott Mar 20 '12 at 5:58
    
@BrianM.Scott I see, so it represents either $(aa | \lambda)$. $(\lambda)(aaaaa)^*$ allows it to represent all $k \equiv 0 mod 5$ and $(aa)(aaaaa)^*$ allows it to represent all $k \equiv 2 mod 5$ –  Hunter McMillen Mar 20 '12 at 6:10
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
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.