DFA for accepting the language L = { anbm | n+m=even }

 DFA for accepting the language L = { anbm | n+m=even }

Design a deterministic finite automata(DFA) for accepting the language L = {a^n b^{m} | m+n=even}
For creating DFA for language, L = { a^n b^m ; n+m=even } use elementary mathematics, which says- 
even + even = even and odd + odd = even

Examples: 

Input:  a a b b     // n = 2, m = 2, 2 + 2 = 4 (even)
Output:  ACCEPTED

Input:  a a a b b b b      // n = 3, m = 4, 3 + 4 = 7 (odd) 
Output:  NOT ACCEPTED

Input:  a a a b b b     // n = 3, m = 3, 3 + 3 = 6 (even)
Output:  ACCEPTED

 

Approaches: 
There is 2 cases that results in acceptance of string:  

  1. If both n and m are even then their sum will be even
  2. If both n and m are odd then their sum will be even

Description: 
Given DFA has 2 parts. The first part consists of states 0, 1, 5, and 6 which is for both n and m is odd. The second part consists of states 2, 3, and 4 is for both n and m is even.
DFA State Transition Diagram:

Post a Comment

0 Comments