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.
DFA
