Question

Consider the following DFA in which $s_0$ is the start state and $s_1,s_3$ are the final states.


What language does this DFA recognize?

• A. All strings of x and y which have equal number of x and y
• B. All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y
• C. All strings of x and y
• D. All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y

Answer 1

The correct option is D All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y

Given DFA can be redesigned as S0 as q00, S1 as q10, S2 as q11, S3 as q01.

Each state is $q_{ab}[a=n_{a}mod2,b=n_{b}mod2]$

q00 as $n_{a}mod2=0,n_{b}mod2=0$ [ number of x is even, number of y is even].


q01 is final state mean where number of x is even and number of y is odd.

q10 is final state mean where number of x is odd and number of y is even.