retagged by
106,697 views
19 votes
19 votes
The alphabets are a and b.
Construct a DFA
retagged by

3 Answers

Best answer
35 votes
35 votes

The above DFA is the required one..

More info:
State 1: even number of a's and even number of b's
State 2: odd number of a's and even number of b's
State 3: even number of a's and odd number of b's
State 4: odd number of a's and odd number of b's

 

selected by
7 votes
7 votes

There's a systematic approach to this problem. Let $L_1$ and $L_2$ are the two languages of odd number of $b$'s and even number of $a$'s respectively.

$\therefore \mathrm{DFA}(L_1)$ is below.

 

$\therefore \mathrm{DFA}(L_2)$ is below.

 

We need to determine $L=(L_1 \cup L_2)^{*}$

So, the states of $\mathrm{DFA}(L)$ will be the cross product of the states of $\mathrm{DFA}(L_1)$ and $\mathrm{DFA}(L_2)$. In this automation, the pair containing the initial states of both $\mathrm{DFA}(L_1)$ and $\mathrm{DFA}(L_2)$ will be the initial state and the pair containing final (accepting) states of both of them will be final (accepting) state. Besides all other pair of states will preserve the edges of $\mathrm{DFA}(L_1)$ and $\mathrm{DFA}(L_2)$. So there will be 4 pair of states: $(13)$, $(14)$, $(23)$ and $(23)$. 

 

$(13)$ will be the initial state as both $1$ and $3$ are the initial states of $\mathrm{DFA}(L_1)$ and $\mathrm{DFA}(L_2)$ respectively. Thus $(23)$ will be final (accepting) state.

$\therefore \mathrm{DFA}(L)$ is below.

 

 

 

1 votes
1 votes

To construct an automaton that accepts strings with an even number of a's and an odd number of b's, we can follow these steps:

  1. Start by creating a state diagram with three states: q0, q1, and q2.

  2. State q0 will be the initial state and the only accepting state will be q2.

  3. Transitions from q0 to q1 are labeled with "a" and from q0 to q2 with "b".

  4. Transitions from q1 to q0 are labeled with "a" and from q1 to q2 with "b".

  5. Transitions from q2 to q1 are labeled with "a" and from q2 to q0 with "b".

  6. Any other transitions (not mentioned above) will lead to a trap state that is not accepting.

The resulting state diagram looks like the following:

 

 

Starting from the initial state q0, the automaton reads an "a" and transitions to state q1. Then, for every "a" read, it alternates between states q0 and q1. For every "b" read, it transitions to state q2. If the string ends in state q2, the automaton accepts it. If it ends in any other state, it rejects it.

Here's the formal definition of the automaton:

  • Q = {q0, q1, q2, trap}
  • Σ = {a, b}
  • δ: Q × Σ → Q
  • δ(q0, a) = q1, δ(q0, b) = q2, δ(q1, a) = q0, δ(q1, b) = q2, δ(q2, a) = q1, δ(q2, b) = q0, δ(q, x) = trap (for any other q and x)
  • q0 ∈ Q (initial state)
  • {q2} ⊆ Q (accepting states)

Related questions

4 votes
4 votes
1 answer
2
Aakanchha asked May 22, 2015
5,090 views
Build an FA that accepts the language of all strings of a's and b's such that next-to-last letter is an $a$.