Question

Question 5. Let S = {a,b}, and consider the language L = {a" : n is even} U{b" : n is odd}. Draw a graph representing a DFA (not NFA) that accepts this language.

Answer 1

L = {a" : n is even} U{" : n is odd}.

The given language accepts strings of the form

• empty string, aa, aaaa, aaaaaa, ....where number of a's are even
• b, bbb, bbbbb, ..... where number of b's are odd

Strings containing both a's and b's should be rejected.

Strings containing only a's but odd number must be rejected.

Strings containing only b's but even number must be rejected.

The DFA is as follows:

Start а b q1 b а q2 q3 a,b a,b b b 96 o 97 ат a a b 95 q4

State

q1: Start state, accepts empty string  (ACCEPTING STATE)

q2: Strings containing only a's but odd number

q3: Strings containing only b's and odd number (ACCEPTING STATE)

q4: Strings containing only a's and even number (ACCEPTING STATE)

q5 Strings containing only b's but even number

q6: Strings containing both a's and b's

q7: Strings containing both a's and b's

Hence for the given DFA q1, q3, q4 are accepting states and

The given DFA accepts strings of the form

• empty string, aa, aaaa, aaaaaa, ....where number of a's are even
• b, bbb, bbbbb, ..... where number of b's are odd

------------------------------------------------------

I hope this helps you,

Please rate this answer if it helped you,

Thanks for the opportunity