Proving that a language is regular

Question

I want to show that $$L = \{1^a2^b3^c | a + b + c \text{ is even}\}$$ is a regular language. I thought about a final state machine or about defining a grammar, but that didn't work good.

Do you have any hint for me what I can try?

Thanks in advance!

Answer 1

You can do that by building a FSA with 6 states:

• $a$ is even
• $a$ is odd
• $a+b$ is even
• $a+b$ is odd
• $a+b+c$ is even
• $a+b+c$ is odd

Answer 2

Hint: $L = L_1 \cap L_2$ where $L_1 = \{a^*b^*c^*\}$ and $L_2 = \{w \in \Sigma^* : |w|\text{ is even}\}$.

Answer 3

You can also do it with a grammar that builds any string of $1$’s, followed by any string of $2$’s, followed by any string of $3$’s of the right parity. You’ll need non-terminal symbols that keep track of what terminals you’re generating and whether you’ve generated an odd or an even number of them. If $S$ is the initial symbol, you could start with $$S\to 1A_o\mid 2B_o\mid 3C_o\mid\lambda\;,$$ where the $o$ subscripts are for odd. Then continue with $$\begin{align*} A_o&\to 1A_e\mid 2B_e\mid 3C_e\mid\lambda\\ A_e&\to 1A_o\mid 2B_o\mid 3C_o\mid 3\\ B_o&\to 2B_e\mid 3C_e\mid\lambda\\ B_e&\to 2B_o\mid 3C_o\mid 3\\ C_o&\to 3C_e\mid 3\\ C_e&\to 3C_o\mid\lambda\;. \end{align*}$$

Note how this parallels the six-state FSA construction.

Answer 4

Note that this is a bit of a tricky problem. Normally if you have some arbitrary constraint given by a predicate $P$ over the variables:

$$L = \{1^a2^b3^c | P(a, b, c) \}$$

this won't be regular in that general case. How can a language like this with a constraint given mathematically be regular?

But $(a + b + c) | 2$ is an interesting special case.

To determine whether the sum of three numbers is odd or even, we just have to look at the last binary digit. When we add binary numbers together, the least significant digit is a simple boolean function of the operands: the xor function.

So, intuitively, we suspect that the recognizer for the language we are working does not have to be able to count or memorize anything, which points to regularity.

$a + b$ is even precisely when both $a$ and $b$ are even, or when they are both odd. $a + b + c$ is even if and only if all three variables are even, or if exactly one of them is even (any two out of the three are odd).

So, this gives us four cases:

 (11)*(22)*(33)*   # regex for even number of 1's, 2's and 3's:
 1(11)*2(22)*(33)* # regex for odd number of 1's, odd number of 2's, even 3's:
 1(11)*(22)*3(33)* # two more cases:
 (11)*2(22)*3(33)*

Now these are just combined with the branch | operator into a single regex:

 (11)*(22)*(33)*|1(11)*2(22)*(33)*|1(11)*(22)*3(33)*|(11)*2(22)*3(33)*

This can probably be simplified, but it is not necessary to do so.

By the equivalence of regexes, finite automata, and regular languages, quod erat demonstrandum.