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

  1. Even number of a’s OR even number of b’s OR the words that have even length of a’s and b’s
  2. Even number of a’s AND odd number of b’s
  3. 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 

even a's or even b's

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

even a's and odd b's

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 

Odd a's and even b's

Related Posts

News Reporter