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

  • 1
    You should certainly show some effort.2012-12-06
  • 0
    I'm confused, the $\mathord{*}$ is concatenation (should be a circle, I think) or repetition (should be higher) or just a symbol?2012-12-06
  • 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
    Thanks Brian, does your answer change for 1 or 3 if * means concatenation? sorry I haven't been so clear about it2012-12-07
  • 0
    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\NFA2012-12-07
  • 1
    @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?2012-12-07
  • 0
    I think I've done the rest right. Thanks again :)2012-12-08
  • 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.