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.
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?