Given an alphabet $\Sigma = \{0, 1\}$ and a formal language $$L = \{ w \in \Sigma^* |\ |\mathrm{odd}(w)|_1, |\mathrm{even}(w)|_1 \text{are even numbers} \}$$

That means that the number of 1's in the odd and even positions of a given string are always an even number. I've tried using the Pumping-Lemma on a $1^{4n}$ string but to no avail.

Any ideas how I can proove it is not regular. (I strongly assume it isn't regular).

  • 1
    Your language is regular. In fact, it is accepted by a DFA having 8 states. – Yuval Filmus Nov 11 '17 at 16:36
  • I can't figure out how to build the DFA. I know how to build one for the languages EVEN(L) and ODD(L) by skipping every odd or even step but I think I'm going in the wrong direction. – Billy Joel Nov 11 '17 at 16:49
  • Try spending a few hours on the question. Sometimes solving a problem takes a while. – Yuval Filmus Nov 11 '17 at 16:50
up vote 1 down vote accepted

To create the DFA, just start doing it. I assume there is no requirement that the number of elements in the string is even.

You start in the state A. In state A, you have an even number of 1's in the even and odd positions (initially, both counts are 0), so A is an accepting state. To get to an accepting state again, there must be a string following with an even number of 1's in the even and odd positions.

In state A, the next symbol can be 0 or 1. In case of 0, you have the exact same situation again, you need another string following with an even number of 1's in the even and odd positions. So A followed by 0 goes to A.

If the next symbol is 1, then the rest of the string must have an even number of 1's in even positions, and an odd number of 1's in odd positions. That's another state B.

In state B, if the next symbol is 0 then you now need an even number of 1's in odd positions, and an odd number of 1's in even positions. That's a new state C. In state B, if the next symbol is 1 then you now need an odd number of 1's in even and odd positions. That's a new state D.

Now you do the same for states C and D, and you find that whatever the input, you'll end up in one of the states A, B, C and D.

Don't think about "state" as some abstract state in a DFA. Think of it as something that you can describe in words. From any state, which you can describe in words, you get to another state, which you can describe in words again. If you compare those descriptions, and they are the same, then the state is the same.

The case where you don't get a DFA is when the number of states is not finite. For example, for $0^n1^n$, the initial state is "I need any number n of 0's and the same number n of 1's". If you get a 0 then you get a state where you need any number n of 0's and n+1 1's. Another 0 and you need n 0's and n+2 1's. And so on. The number of states is not finite. In your problem, there are only four states needed.

If that's too practical, then given any prefix X of a string in the language L, define the set of suffixes Y such that XY is in the language. Any such set of suffices is a state. An accepting state is one where the set contains the empty string. The initial state is the set of suffices when X is the empty string. In your case, there are only four different sets of suffices.

  • I managed to do it with 18 states, every state containing either 0, 2k+1 or 2k (k being a natural number) 1's in odd OR even positions and at the same time tracking if I have an odd or even number of characters in the whole string. That makes 3 * 3 * 2 = 18 states in total. My end states are 2k, 2k, odd and 2k, 2k, even. Thank you a lot sir, I think I'll need more practice with DEA's in the future. – Billy Joel Nov 14 '17 at 10:01

The following general result holds:

Let $L = \{ w : \mathrm{odd}(w) \in L_1 \text{ and } \mathrm{even}(w) \in L_2 \}$. Then $L$ is regular iff $L_1,L_2$ are regular.

Indeed, suppose first that $L$ is a regular language over the alphabet $\Sigma$. Define a substitution $s\colon \Sigma \to 2^{\Delta^*}$, where $\Delta = \{ \sigma, \sigma' : \sigma \in \Sigma \}$ by $s(\sigma) = \{\sigma, \sigma'\}$ and the homomorphism $d\colon \Delta \to \Sigma^*$ by $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Using $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$, we have $$ \begin{align*} L_1 &= d(s(L) \cap (\Sigma\Sigma')^*(\Sigma+\epsilon)), \\ L_2 &= d(s(L) \cap (\Sigma'\Sigma)^*(\Sigma'+\epsilon)). \end{align*} $$ This shows that if $L$ is regular then $L_1,L_2$ are regular.

In the other direction, suppose that $L_1,L_2$ are regular. Let $s_1\colon \Sigma \to \Sigma^*$ be the substitution $s_1(\sigma) = \{ \sigma \tau : \tau \in \Sigma$, and let $s_2\colon \Sigma \to \Sigma^*$ be the substitution $s_2(\sigma) = \{ \tau \sigma : \tau \in \Sigma \}$. Then $$ L = (s_1(L_1) \cap s_2(L_2)) \cup d(s(s_1(L_1)) \cap s_2(L_2) \Sigma \Sigma'), $$ showing that $L$ is regular if $L_1,L_2$ are regular.


Given DFAs for $L_1,L_2$, you can construct a DFA for $L$ as follows (the same construction works for NFAs):

  • The set of states is $Q = Q_1 \times Q_2 \times \{odd,even\}$.
  • The initial state is $q_0 = (q_{0,1},q_{0,2},even)$.
  • The final states are $F = F_1 \times F_2 \times \{odd,even\}$.
  • The transition function is given by $\delta((q_1,q_2,even),\sigma) = (\delta_1(q_1,\sigma),q_2,odd)$ and $\delta((q_1,q_2,odd),\sigma) = (q_1,\delta_2(q_2,\sigma),even)$.

You can check that for a word $w$ of odd/even length, $$\delta(q_0,w) = (\delta_1(q_{0,1},\mathrm{odd}(w)),\delta_2(q_{0,2},\mathrm{even}(w)),odd/even),$$ and so $\delta(q_0,w) \in F$ iff $\delta_1(q_{0,1},\mathrm{odd}(w)) \in F_1$ and $\delta_2(q_{0,2},\mathrm{even}(w)) \in F_2$.

This also shows that if $L_1,L_2$ can be accepted by DFAs with $n_1,n_2$ states, then $L$ can be accepted by a DFA with $2n_1n_2$ states.

  • This was really helpful! I still have trouble constructing the DEA though. – Billy Joel Nov 11 '17 at 18:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.