1
$\begingroup$

I need help proving whether this language is regular or not.

$$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$

That is, the number of $a$'s is even and the number of $b$'s in $w$ is even.

I'm not sure whether I can draw a dfa for this. Thanks, all help is appreciated.

$\endgroup$
1
$\begingroup$

There will be 4 states. One where $n_a(w)$ even and $n_b(w)$ even, one where $n_a(w)$ even and $n_b(w)$ odd, one where $n_a(w)$ odd and $n_b(w)$ even, and one where $n_a(w)$ odd and $n_b(w)$ even.

$\endgroup$
1
$\begingroup$

HINT: Try making a DFA with four states, $s_{00},s_{01},s_{10}$, and $s_{11}$. Design it so that when it has read a word with $m$ $a$’s and $n$ $b$’s, it’s in state $s_{m\bmod 2,n\bmod 2}$. (Here $n\bmod 2$ is the remainder when $n$ is divided by $2$, so it’s $0$ if $n$ is even and $1$ if $n$ is odd.)

Added: Here’s your DFA, from the comments, with $q_0$ starred as initial state and underlined as acceptor state. As you can see, each $a$ input moves the automaton horizontally, and each $b$ input moves it vertically, so the states in the top row correspond to an even number of $b$’s, and the states in the lefthand column to an even number of $a$’s.

$$\begin{array}{rcl} \underline{q_0^*}&\overset{a}\longleftrightarrow&q_1\\ b\updownarrow&&\updownarrow b\\ q_2&\underset{a}\longleftrightarrow&q_3 \end{array}$$

$\endgroup$
  • $\begingroup$ Hi just wondering if you could check my answer. my dfa is the following: a b q0 q1 q2 q1 q0 q3 q2 q3 q0 q3 q2 q1 $\endgroup$ – Thresh Feb 12 '13 at 6:15
  • $\begingroup$ @TonsOfDamage: I’m interpreting that to mean that there are $a$-transitions from $q_0$ to $q_1$, $q_1$ to $q_0$, $q_2$ to $q_3$, and $q_3$ to $q_2$, and $b$-transitions from $q_0$ to $q_2$, $q_1$ to $q_3$, $q_2$ to $q_0$, and $q_3$ to $q_1$. If $q_0$ is both your initial state and your only acceptor state, that DFA works fine. $\endgroup$ – Brian M. Scott Feb 12 '13 at 6:27
  • $\begingroup$ Yes, you interpreted that right. However, I made my initial state q0 and my final/acceptor state q1. Could you tell me if this works? or if q0 should be my initial and accepting state? $\endgroup$ – Thresh Feb 12 '13 at 6:42
  • $\begingroup$ @TonsOfDamage: $q_0$ should also be your acceptor state. If you start in $q_0$, after an even number of $a$’s you’ll be in $q_0$ or $q_2$, and after an even number of $b$’s you’ll be in $q_0$ or $q_1$; you want both, so you want to be in $q_0$. If you’re in $q_1$, you’ve read an odd number of $a$’s and an even number of $b$’s. $\endgroup$ – Brian M. Scott Feb 12 '13 at 6:49
  • $\begingroup$ Alright, I understand now. Thank you very much for your help. $\endgroup$ – Thresh Feb 12 '13 at 6:50
0
$\begingroup$

Providing a regular expression would work as well. The key point is to observe, that you could split any word of $L$ into chunks $ba^k$ and some simple leftovers. The only thing we need to fix is that the number of $b$s and $a$s has to be even, but then $ba^*ba^*$ would do the job. One could derive from this a single expression, however, it is much easier to split it in two and intersect (regular languages are closed for intersection).

\begin{align} L_a &= b^*(ab^*ab^*)^*, \text{ the language of even $a$s}\\ L_b &= a^*(ba^*ba^*)^*, \text{ the language of even $b$s}\\ L &= L_a \cap L_b. \end{align}

I hope it helps ;-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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