Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

4 Answers 4

up vote 5 down vote accepted

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
share|improve this answer

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

share|improve this answer
    
Note: This is a way to do it, definitely not the only way. There is a finite state machine with 6 states that will accept the language as well. –  Brandon Carter Apr 25 '12 at 20:14

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.

share|improve this answer
    
It is a peculiar grammar, because you always have at most one non-terminal. Do such grammars have a name? –  Vitalij Zadneprovskij Apr 25 '12 at 20:38
1  
@vitalik: It’s a regular grammar. Otherwise it wouldn’t show that the language is regular. –  Brian M. Scott Apr 25 '12 at 20:53
    
Great, thank you! –  muffel Apr 26 '12 at 6:15

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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