# 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 which 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
3. Any other combination result is the rejection of the input string.

Description:
Given DFA has 2 parts. First part consisting of states 0, 1, 5 and 6 which is for both n and m being odd. Second part consist of states 2, 3 and 4 is for both n and m is even.

DFA State Transition Diagram:

Let’s see code for the demonstration:

## C

 `// C program to implement DFA that accepts ` `// all strings which follow the language ` `// L = { a^n b^m ; n+m=even } ` `#include ` `#include ` ` `  `// dfa tells the number associated ` `// with the present state ` `int` `dfa = 0; ` ` `  `// This function is for ` `// the starting state (zeroth) of DFA ` `void` `start(``char` `c) ` `{ ` `    ``if` `(c == ``'a'``) ` `        ``dfa = 1; ` `    ``else` `if` `(c == ``'b'``) ` `        ``dfa = 2; ` ` `  `    ``// -1 is used to check for any invalid symbol ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the first state of DFA ` `void` `state1(``char` `c) ` `{ ` `    ``if` `(c == ``'a'``) ` `        ``dfa = 0; ` `    ``else` `if` `(c == ``'b'``) ` `        ``dfa = 5; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the second state of DFA ` `void` `state2(``char` `c) ` `{ ` `    ``if` `(c == ``'b'``) ` `        ``dfa = 3; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the third state of DFA ` `void` `state3(``char` `c) ` `{ ` `    ``if` `(c == ``'b'``) ` `        ``dfa = 4; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the fourth state of DFA ` `void` `state4(``char` `c) ` `{ ` `    ``if` `(c == ``'b'``) ` `        ``dfa = 3; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the fifth state of DFA ` `void` `state5(``char` `c) ` `{ ` `    ``if` `(c == ``'b'``) ` `        ``dfa = 6; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `// This function is for the sixth state of DFA ` `void` `state6(``char` `c) ` `{ ` `    ``if` `(c == ``'b'``) ` `        ``dfa = 5; ` `    ``else` `        ``dfa = -1; ` `} ` ` `  `int` `isAccepted(``char` `str[]) ` `{ ` `    ``// store length of string ` `    ``int` `i, len = ``strlen``(str); ` ` `  `    ``for` `(i = 0; i < len; i++) { ` `        ``if` `(dfa == 0) ` `            ``start(str[i]); ` ` `  `        ``else` `if` `(dfa == 1) ` `            ``state1(str[i]); ` ` `  `        ``else` `if` `(dfa == 2) ` `            ``state2(str[i]); ` ` `  `        ``else` `if` `(dfa == 3) ` `            ``state3(str[i]); ` ` `  `        ``else` `if` `(dfa == 4) ` `            ``state4(str[i]); ` ` `  `        ``else` `if` `(dfa == 5) ` `            ``state5(str[i]); ` ` `  `        ``else` `if` `(dfa == 6) ` `            ``state6(str[i]); ` ` `  `        ``else` `            ``return` `0; ` `    ``} ` `    ``if` `(dfa == 3 || dfa == 5) ` `        ``return` `1; ` `    ``else` `        ``return` `0; ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``char` `str[] = ``"aaabbb"``; ` `    ``if` `(isAccepted(str)) ` `        ``printf``(````" ACCEPTED "````); ` `    ``else` `        ``printf``(````"NOT ACCEPTED "````); ` `    ``return` `0; ` `} `

## Java

 `// Java program to implement DFA that accepts ` `// all strings which follow the language ` `// L = { a^n b^m ; n+m=even } ` `class` `GFG { ` ` `  `    ``// dfa tells the number associated ` `    ``// with the present state. ` `    ``static` `int` `dfa = ``0``; ` ` `  `    ``// This function is for ` `    ``// the starting state (Q0)of DFA ` `    ``static` `void` `start(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'a'``) { ` `            ``dfa = ``1``; ` `        ``} ` `        ``else` `if` `(c == ``'b'``) { ` `            ``dfa = ``2``; ` `        ``} ` ` `  `        ``// -1 is used to check for any invalid symbol ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for ` `    ``// the first state (Q1) of DFA ` `    ``static` `void` `state1(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'a'``) { ` `            ``dfa = ``0``; ` `        ``} ` `        ``else` `if` `(c == ``'b'``) { ` `            ``dfa = ``5``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for the ` `    ``// second state (Q2) of DFA ` `    ``static` `void` `state2(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'b'``) { ` `            ``dfa = ``3``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for the ` `    ``// third state (Q3)of DFA ` `    ``static` `void` `state3(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'b'``) { ` `            ``dfa = ``4``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for the ` `    ``// fourth state (Q4) of DFA ` `    ``static` `void` `state4(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'b'``) { ` `            ``dfa = ``3``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for the ` `    ``// fifth state (Q5) of DFA ` `    ``static` `void` `state5(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'b'``) { ` `            ``dfa = ``6``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``// This function is for the ` `    ``// sixth state (Q6) of DFA ` `    ``static` `void` `state6(``char` `c) ` `    ``{ ` `        ``if` `(c == ``'b'``) { ` `            ``dfa = ``5``; ` `        ``} ` `        ``else` `{ ` `            ``dfa = -``1``; ` `        ``} ` `    ``} ` ` `  `    ``static` `int` `isAccepted(``char` `str[]) ` `    ``{ ` `        ``// store length of string ` `        ``int` `i, len = str.length; ` ` `  `        ``for` `(i = ``0``; i < len; i++) { ` `            ``if` `(dfa == ``0``) ` `                ``start(str[i]); ` ` `  `            ``else` `if` `(dfa == ``1``) ` `                ``state1(str[i]); ` ` `  `            ``else` `if` `(dfa == ``2``) ` `                ``state2(str[i]); ` ` `  `            ``else` `if` `(dfa == ``3``) ` `                ``state3(str[i]); ` ` `  `            ``else` `if` `(dfa == ``4``) ` `                ``state4(str[i]); ` ` `  `            ``else` `if` `(dfa == ``5``) ` `                ``state5(str[i]); ` ` `  `            ``else` `if` `(dfa == ``6``) ` `                ``state6(str[i]); ` ` `  `            ``else` `                ``return` `0``; ` `        ``} ` `        ``if` `(dfa == ``3` `|| dfa == ``5``) ` `            ``return` `1``; ` `        ``else` `            ``return` `0``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``char` `str[] = ``"aaabbb"``.toCharArray(); ` `        ``if` `(isAccepted(str) == ``1``) ` `            ``System.out.println(``"ACCEPTED"``); ` `        ``else` `            ``System.out.println(``"NOT ACCEPTED"``); ` `    ``} ` `} `

## Python3

 `# Python3 program to implement DFA that accepts  ` `# all strings which follow the language  ` `# L = a ^ n b ^ m n + m = even  ` ` `  `# This function is for the dfa = starting ` `# dfa = state (zeroth) of DFA  ` `def` `start(c): ` `    ``if` `(c ``=``=` `'a'``): ` `        ``dfa ``=` `1` `    ``elif` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `2` `     `  `    ``# -1 is used to check for any ` `    ``# invalid symbol  ` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `# This function is for the first  ` `# dfa = state of DFA  ` `def` `state1(c):  ` `    ``if` `(c ``=``=` `'a'``): ` `        ``dfa ``=` `0` `    ``elif` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `5` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `# This function is for the second  ` `# dfa = state of DFA  ` `def` `state2(c): ` `    ``if` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `3` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `# This function is for the third  ` `# dfa = state of DFA  ` `def` `state3(c): ` `    ``if` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `4` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `# This function is for the fourth ` `# dfa = state of DFA  ` `def` `state4(c): ` `    ``if` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `3` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `# This function is for the fifth  ` `# dfa = state of DFA  ` `def` `state5(c):  ` `    ``if` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `6` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  ` `  `# This function is for the sixth  ` `# dfa = state of DFA  ` `def` `state6(c):  ` `    ``if` `(c ``=``=` `'b'``): ` `        ``dfa ``=` `5` `    ``else``: ` `        ``dfa ``=` `-``1` `    ``return` `dfa ` ` `  `def` `isAccepted(String): ` `     `  `    ``# store length of Stringing  ` `    ``l ``=` `len``(String) ` `     `  `    ``# dfa tells the number associated ` `    ``# with the present dfa = state ` `    ``dfa ``=` `0` `    ``for` `i ``in` `range``(l):  ` `        ``if` `(dfa ``=``=` `0``):  ` `            ``dfa ``=` `start(String[i])  ` ` `  `        ``elif` `(dfa ``=``=` `1``):  ` `            ``dfa ``=` `state1(String[i])  ` ` `  `        ``elif` `(dfa ``=``=` `2``) : ` `            ``dfa ``=` `state2(String[i])  ` ` `  `        ``elif` `(dfa ``=``=` `3``) : ` `            ``dfa ``=` `state3(String[i])  ` ` `  `        ``elif` `(dfa ``=``=` `4``) : ` `            ``dfa ``=` `state4(String[i])  ` `  `  `        ``elif` `(dfa ``=``=` `5``) : ` `            ``dfa ``=` `state5(String[i])  ` ` `  `        ``elif` `(dfa ``=``=` `6``):  ` `            ``dfa ``=` `state6(String[i])  ` ` `  `        ``else``: ` `            ``return` `0` `    ``if``(dfa ``=``=` `3` `or` `dfa ``=``=` `5``) : ` `        ``return` `1` `    ``else``: ` `        ``return` `0` ` `  `# Driver code  ` `if` `__name__ ``=``=` `"__main__"` `: ` `    ``String ``=` `"aaabbb"` `    ``if` `(isAccepted(String)) : ` `        ``print``(``"ACCEPTED"``)  ` `    ``else``: ` `        ``print``(``"NOT ACCEPTED"``)  ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

## PHP

 ` `

Output:

`ACCEPTED`