Question

Question: The following are the state diagrams of two DFA_s , M₁ and M₂ . Answer the following questions about each of these machines.

a. What is the start state ?

b. What is the set of accept states ?

c. What sequence of states does the machine go through on input aabb ?

d. Does the machine accept the string aabb ?

e. Does the machine accept the string $\epsilon$ ?

Short answer

Answer :

(a) is the initial state of machines M₁ and M₂ .

(b)computer M , the approved state is q₂ , while in computer M₂ , the acceptable states include q₁ & q₄

(c)It travels around $q_1->q_2,q_2->q_3,q_3->q_1$ , and $q_2->q_4$ in computer M₁ . Computer M₂ runs through into the steps $q_1->q_1,q_1->q_1,q_2->q_2$ , and $q_2->q_4$.

(d)When Machine M₂ gets to the final condition, it approves the sequence aabb , so it accepts the string. However, machine M₁ will not accept the string because it is not in the final state.

(e)Machine M₂ accepts the null string because it can transition from either the beginning to the receptive state without needing to read additional alphabet symbols

Step-by-step solution

Definition of DFA

In the afore mentioned question, we must identify different DFA situations from the beginning to the end, which would be string-based machine acceptability.

Start state of the diagram

a) M₁ 's begin position is q₁ , and M₂ 's begin status is q₁ // the beginning state is denoted by an arrow.

b) M₁ : q₁ and M₂ : q₁ , q₄ A double circle represents the accepting state.

c) input $aabb$

Progression of states in

Progression of states in

d) input $aabb$

For M₁ is not an accommodating state

For M₂ is an tolerant state

e) input

For M₁ is not an agree state

For M₂ is an allow state

2) DFA is formally represented with

Q : Set of all states

$\Sigma$: Set of input symbols

$\delta$ : Transition Function $\delta :QX\Sigma -->Q$ .

q : Initial state

F : Set of final state

For M₁ :

$$\begin{gathered} Q=\left\{q_1,q_2,q_3\right\} \\ \sum =\left\{a,b\right\} \\ q=q_1 \\ F=\left\{q_2\right\} \\ TransitionFunction\delta :QX\Sigma -->Q. \end{gathered}$$

ar	Next state for Input a	Next state for Input b
q1	q2	q1
q2	q3	q3
q3		q1

For M₂ :

$$\begin{gathered} Q=\left\{q_1,q_2,q_3,q_4\right\} \\ \sum =\left\{a,b\right\} \\ q=q_1 \\ F=\left\{q_1,q_4\right\} \\ TransitionFunction\delta :QX\Sigma -->Q. \end{gathered}$$

Present state	Next state for Input a	Next state for Input b
q1	q1	q2
q2	q3	q4
q3	q2	q1
q4	q3	q4

3)a) Image-1 :

b)Image-2