# Prove a language is regular [duplicate]

I am asked to find

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?

• 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 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 Nov 18 '14 at 19:52

## 1 Answer

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.

• if I was to do a regular expression would that also work? Say "aaaa*bb*aa*" ? – tyuip Nov 18 '14 at 19:58
• @tyuip. That's a perfectly good way to do it. This idea will also work for your other two questions. – Rick Decker Nov 18 '14 at 20:01
• So what does 2mod7 mean for (b)? Like is that his way of just saying 2 or...? – tyuip Nov 18 '14 at 20:10
• @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
• So say for a DFA 0a1 1a2 2a3 3a4 4a5 5a6 6a7 7a8 8a3 with all final but state 2 and 3? – tyuip Nov 18 '14 at 20:22