Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma:

$L = \{a^n\mathord{*} a^m \mid m \equiv n \pmod 3\}$
$L = \{w \in \{0,1\}^*\mid \text{number of "10" equals to the number of occurances of "01" in $w$}\}$
$L = \{a^i\mathord*b^j\mathord*c^k \mid i>j>15, k>0\}$

Thanks in advance

share|cite|improve this question
You should certainly show some effort. – Karolis Juodelė Dec 6 '12 at 22:03
I'm confused, the $\mathord{*}$ is concatenation (should be a circle, I think) or repetition (should be higher) or just a symbol? – Karolis Juodelė Dec 6 '12 at 22:11
It means concatenation, in this case – DanielY Dec 7 '12 at 4:38
up vote 1 down vote accepted

In the first and third languages I’m assuming that $*$ is a symbol in the alphabet.

(i) $L=\{a^n*a^m:n\equiv m\pmod 3\}$. This is regular, basically because there are only finitely many congruence classes mod $3$. You can show this either by building a finite state automaton that recognizes it or by finding a regular grammar that produces it.

For a grammar, let $S$ be the initial symbol, and start with the three productions $$S\to A_0\mid aA_1\mid aaA_2\;;$$ the first of these will be used to generate strings $a^n$ such that $n\equiv0\pmod3$, the second to generate strings $a^n$ such that $n\equiv1\pmod3$, and the third to generate strings $a^n$ such that $n\equiv2\pmod3$. Each of the non-terminals $A_k$ must therefore produce strings of the form $(aaa)^**$:

$$\begin{align*} &A_0\to aaaA_0\mid *B_0\\ &A_1\to aaaA_1\mid *B_1\\ &A_2\to aaaA_2\mid *B_2\;. \end{align*}$$

Now each $B_k$ has to generate a string of the form $a^m$, where $m\equiv k\pmod3$:

$$\begin{align*} &B_0\to \epsilon\mid aaaB_0\\ &B_1\to aB_0\\ &B_2\to aaB_0\;. \end{align*}$$

For FSA use six states, $s_0,s_1,s_2,s_0',s_1'$, and $s_2'$. Make $s_0$ the initial state, and give state $s_k$ an $a$-transition to $s_{(k+1)~\bmod~3}$. Each state $s_k$ should have a $*$-transition to $s_k'$, and each state $s_k'$ should have an $a$-transition to $s_{(k-1)~\bmod~3}$. There is one acceptor state; can you see what it is?

(ii) $L=\big\{w\in\{0,1\}^*:|w|_{10}=|w|_{01}\big\}$, where $|w|_x$ is the number of occurrences in $w$ of the substring $x$. Let $w\in\{0,1\}^*$, let $\alpha$ be the first symbol of $w$, and let $\beta=1-\alpha$, the other possible symbol. Set a counter $c$ to $0$, and then scan $w$ from left to right. Each time you move from an $alpha$ to a $\beta$, increase $c$ by $1$, and each time you move from a $\beta$ to an $\alpha$, decrease $c$ by $1$. When you’re done scanning $w$, what final value of $c$ tells you that $w\in L$? Can you design a finite state automaton to mimic this scanning process?

(iii) $L=\{a^i*b^j*c^k:i>j>15\text{ and }k>0\}$. It should be intuitively clear that this language should not be regular: if you generate the word from right to left, you have to know how many $b$’s were generated in order to know the minimum number of $a$’s required. You can work directly with this language, or you can notice that this language is regular iff the language $\{a^i*b^j:i>j>15\}$ is regular, and that this is regular iff the language $\{a^i*b^j:i>j\}$ is regular. To show that this last language is not regular, apply the pumping lemma to the word $a^p*b^{p-1}$, where $p$ is the pumping length.

share|cite|improve this answer
Thanks Brian, does your answer change for 1 or 3 if * means concatenation? sorry I haven't been so clear about it – DanielY Dec 7 '12 at 4:54
And @Brian one more thing, can you give me a starting point for 2? I understood the idea but I can't seem to implement it in DFA\NFA – DanielY Dec 7 '12 at 8:10
@user1067083: (ii) You can do it with just five states. Call them $s,s_0,s_0',s_1$, and $s_1'$; $s$ is the initial state, and it should be an acceptor state, since the empty word is in $L$. If the first input is $0$, go to state $s_0$; if it’s $1$, to $s_1$. The words $0$ and $1$ are in $L$, so $s_0$ and $s_1$ should be acceptor states. In $s_0$ a $0$ leaves you where you are, and a $1$ takes you to $s_0'$. Can you finish it from there? – Brian M. Scott Dec 7 '12 at 17:52
I think I've done the rest right. Thanks again :) – DanielY Dec 8 '12 at 19:13
@user1067083: You’re welcome. – Brian M. Scott Dec 8 '12 at 22:09

Hint 1: Try constructing an automaton. If you can't, try one with 2 instead of 3.

Hint 2: Try counting the two numbers for some strings. Like "010" and "01111" and "1010101", maybe you'll notice something.

Hint 3: ?
Sorry, I can't come up with why 3 could be a problem... I guess, trying an automaton is always a good suggestion.

share|cite|improve this answer

Your Answer


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.