Question

Question 5. Let Σ = {a, b}, and consider the language

L = {a^n : n is even} ∪ {b^n : n is odd}.

Draw a graph representing a DFA (not NFA) that accepts this language.

Answer 1

Given language is

L = { a^n : n is even } U { b^n : n is odd }

Consider the given Language L = L1 U L2 where

L1 = { a^n : n is even } and

L2 = {b^n : n is odd}.

Strings in languages

L1 = {e,aa,aaaa,aaaaaa,..................} and

L2 = {b,bbb,bbbbb,bbbbbbb,...................}

L = L1 U L2

L = {e,b,aa,bbb,aaaa,bbbbb,aaaaaa,................} # e is empty string epsilon

DFA:

This DFA accepts L

Starting state(initial state) = A

Set of States = {A,B,C,D,DEAD(OPTIONAL)}

Set of final states = {A,C}

Transition Table:

States	a	b
A	B	C
B	A	Dead
C	Dead	D
D	Dead	C
Dead	Dead	Dead

DFA Graph:

Da,b. b Dead, B A b. b

If you have any doubts please leave a comment!!!!!!!!