edited by
6,414 views
29 votes
29 votes

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 $\textsf{DFA}$ recognize?

  1. All strings of $x$ and $y$
  2. All strings of $x$ and $y$ which have either even number of $x$ and even number of $y$ or odd number of $x$ and odd number of $y$
  3. All strings of $x$ and $y$ which have equal number of $x$ and $y$
  4. 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$
edited by

8 Answers

Best answer
37 votes
37 votes

Above DFA can be redesigned as: [$S_0$ as $q00$, $S_1$ as $q10$ , $S_2$ as $q11$, $S_3$ as $q01$ ]

Where, each state as $q_{ab} [a = n_a \ mod \ 2 , b = n_b \ mod \ 2]$

$q00$ as $n_a \ mod \ 2 =0, n_b \ mod \ 2=0$  [no of $x$ is even no of $y$ is even ]

and $\delta(q00, x) \rightarrow q10 \ \ \   [(0+1) \ mod \ 2 =1$ as $x$ increase from $0$ to $1] \ \  \delta (q00, y) \rightarrow q01$ 

and $\delta (q10, x) \rightarrow q00  [(1+1) \ mod \ 2 =0]$    $\delta(q00, y) \rightarrow q01$ and soon 

$q01$ is final state mean where no of $x$ is even and no of $y$ is odd 

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

So, D is correct answer.

edited by
17 votes
17 votes
D is the answer. Just simulate the running of the DFA on all options- A, B and C are false and D is true.
9 votes
9 votes

During Exam we can use here option elimination to approach it quickly.

A. All strings of x and y . false Counter Ex. i/p xy rejects here.

B. All strings of x and y which have either even number of x and even number of y or odd number of x and odd number of y.false. Counter Ex. i/p xyy rejects here

C. All strings of x and y which have equal number of x and y. false. Counter Ex. i/p xy rejects here

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. True.

So D is Ans.

9 votes
9 votes

The given DFA can be minimised to the following DFA:

L = (x+y)((x+y)(x+y))* = {w ∈ Σ* : w has even number of xs and odd number of ys or odd number of xs and even number of ys}

Ans -> D

Answer:

Related questions

42 votes
42 votes
7 answers
1
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?
47 votes
47 votes
4 answers
2