# Prove a language is regular [duplicate]

Prove that the following languages are regular languages:

(a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$

(b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$

(c) $\{a^nb \mid n\geq2\}\cup\{ab^m \mid m≥3\}$

I have a vague understanding of pumping lemma, and how to prove a language is not regular, but was hoping that someone could walk through (a) with me to give me a better understanding and allow me to do the rest on my own. I think I must make an automaton but I am not sure how, as this does not seem finite to me?

## marked as duplicate by Raphael♦Nov 19 '14 at 11:50

• The pumping lemma is used to show that languages are not regular, so you don't need it for this question. – David Richerby Nov 18 '14 at 18:23
• In what sense does (a) not look finite to you? Is it the fact that the language contains an infinite number of strings? If so, note that the finiteness of a finite automaton does not refer to the number of distinct strings it recognises, but to the number of states it contains for recognising those strings. For recognising (a) a finite number of states suffices, so I would suggest trying to define a finite automaton that accepts the language. – Roy O. Nov 18 '14 at 19:33
• So what makes this finite as opposed to say a^nb^n? – tyuip Nov 18 '14 at 19:40
• And to make a finite machine can I choose any value for n, m and k as long as they are in the bounds set? also a^n simply means n amount of a's in the string, correct? – tyuip Nov 18 '14 at 19:44
• Have you studied (deterministic) finite state automatons? They count roughly by moving to states that keep track of the count so far. For $a^nb^n$, $n$ can be arbitrarily large, so any finite number of states will fall short at some point - the pumping lemma can be used to prove this. For (a) the count is bounded by constants (e.g. we only need to count up to 3 for the $a$'s), so this problem does not occur. (It's difficult to explain well in a comment - I would suggest looking for an elementary textbook.) – Roy O. Nov 18 '14 at 19:52

Note that the language in (a) consists of strings that start with $\mathtt{aaaa}^r\dotsc$ where $r\ge 0$. Make use of the idea that a state in a FA can "record" the answer to a yes/no question. To process the first part, use a FA with four states, \begin{align} q_0:&\text{ we've seen 0\ \mathtt{a}'s so far}\\ q_1:&\text{ we've seen 1\ \mathtt{a} so far}\\ q_2:&\text{ we've seen 2\ \mathtt{a}'s so far}\\ q_3:&\text{ we've seen 3 or more \mathtt{a}'s so far}\\ \end{align} Obviously, in state $q_0$ on input $\mathtt{a}$, we'll go to state $q_1$, in state $q_1$ on an $\mathtt{a}$ we'll go to state $q_2$, in state $q_2$ on an $\mathtt{a}$ we'll go to state $q_3$ and in state $q_3$ on an $\mathtt{a}$ we'll stay in state $q_3$. That takes care of the first part, $\mathtt{a}^n$ where $n\ge 3$. Do the same thing for the other two parts and you'll have a FA for the language.
• @tyuip. $n\equiv 2\pmod{7}$ means that $(n-2)$ is divisible by 7. Equivalently, it means that $n$ when divided by 7 gives a remainder of 2, so in this case we'd have $n\in\{ 2, 9, 16, 23,\dotsc\}$. – Rick Decker Nov 18 '14 at 20:13