# Proving a language is regular or irregular

I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to create a DFA for L1, I found that the language is in fact regular. But I am unsure how to begin to prove it.

L1: {w | contains the same number of occurrences of 01 as 10}

L2: {w | contains the same number of occurrences of 00 as 11}

I appreciate any help with these.

Many Thanks in advance.

-
I really don't see how a question with sets is automatically about set theory. –  Asaf Karagila Jan 26 '13 at 22:26
Just providing an example of automaton or regular expression or syntax monoid that would recognize the language would be enough (of course you need to prove that the given object indeed recognizes the language). –  dtldarek Jan 26 '13 at 22:59
Thanks for the reply. I already have a DFA for L1, so the next step would be to explain why the machine accepts the language? Is there a systematic way to do this? –  Epsilon Jan 27 '13 at 2:02

## 1 Answer

For $L_1$ I’d set up a DFA with initial state $s_0$ and four other states, $s_{00},s_{01},s_{11}$, and $s_{10}$. The acceptor states are $s_0,s_{00}$, and $s_{11}$. The transition table is:

$$\begin{array}{c|c|c} &0&1\\ \hline\\ s_0&s_{00}&s_{11}\\ s_{00}&s_{00}&s_{01}\\ s_{01}&s_{00}&s_{01}\\ s_{11}&s_{10}&s_{11}\\ s_{10}&s_{10}&s_{11} \end{array}$$

This is essentially two otherwise disjoint automata with a common initial state. If the first input is $0$, states $s_{11}$ and $s_{10}$ are never entered, and if the first input is $1$, states $s_{00}$ and $s_{01}$ are never entered.

Clearly any word of length at most $1$ is accepted; that’s correct, since those words have neither $01$ nor $10$. Show by induction on $|w|$ that a word $w\in\{0,1\}^*$ of length at least $1$ with first symbol $i$ takes the automaton to state $s_{ii}$ if and only if its last symbol is $i$. Finally, show that $w\in L_1$ if and only if the first and last symbols of $w$ are equal. You can do this by induction on $|w|$, but you can also simply observe that if $w=s_1\dots s_n$, and we call $k\in\{1,\dots,n-1\}$ a transition point if $s_k\ne s_{k+1}$, then $w\in L_1$ if and only if $w$ has an even number of transition points and therefore identical first and last symbols: consecutive transitions must be of opposite types. (That is, a $01$ transition cannot be followed by another $01$ transition without an intervening $10$ transition.)

HINT for $L_2$: What language do you get when you intersect $L_2$ with the regular language generated by the regular expression $00^*11^*$? Is that language regular?

-
+1 Thanks for the reply. For L2, I think it is... why wouldnt it be? (00)^2(11)^2, (00)^3(11)^3, ... (00)^n(11)^n, am I wrong? –  Epsilon Jan 27 '13 at 16:13
@MHZ: You’re welcome. The intersection isn’t quite what you wrote; it’s $\{0^n1^n:n\ge 1\}$, which is one of the classic examples of a language that is context-free but not regular. See here for a proof using the pumping lemma. –  Brian M. Scott Jan 27 '13 at 20:22