0
$\begingroup$

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

  • 0
    It means concatenation, in this case2012-12-07

2 Answers 2

1

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.

  • 0
    @user1067083: You’re welcome.2012-12-08
1

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.