Construct the RE and DFA over the input alphabet Σ = {a, b} that accepts:

- Even number of a’s OR even number of b’s OR the words that have even length of a’s and b’s
- Even number of a’s AND odd number of b’s
- Odd number of a’s AND even number of b’s

## 1- RE

**A = [aa + bb + (ab+ba) (aa+bb)* (ab+ba)]***

This above RE will accept the words having

- all the even numbers of a’s
- all the even numbers of b’s
- the word that has even length of a’s and b’s

## DFA

This DFA machines will accept all the words having:

- even length of a’s
- even length of b’s
- even length of a’s and b’s

## 2- Even a’s and odd b’s

### RE

The RE of the language Σ = {a, b} containing even number of a’s and an odd number of b’s will be made by adding an extra “b” to the above RE.

**A = [aa + bb + (ab+ba) (aa+bb)* (ab+ba)]***

**B = b(A) + a[ A(ab+ba)A ]**

We can’t write the above RE (A) as:

**B = A (b) A**

Because it is not generating the substring “aba” which has an even number of a’s and an odd number of b’s.

### DFA

## 3- Odd a’s and even b’s

### RE

The RE of the language Σ = {a, b} containing an odd number of a’s and an even number of b’s will be made by adding an extra “a” to the first RE.

**A = [aa + bb + (ab+ba) (aa+bb)* (ab+ba)]***

**B = a(A) + b[ A(ab+ba)A ]**

We can’t write the above RE (A) as:

**B = A (a) A**

Because this is generating the substring “bab” which has an odd number of a’s and an even number of b’s.