DFA for accepting the language L = { anbm | n+m=even }
Design a deterministic finite automata(DFA) for accepting the language L =
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:
- If both n and m are even then their sum will be even
- 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:
0 Comments