Finite-state automata $A$ and $A ^ { \prime }$ are defined by the transition diagrams shown below.

(a) Find the quotient automaton for A.
(b) Find the quotient automaton for$A ^ { \prime }$
(c) Are A and $A ^ { \prime }$ equivalent? Explain.

Question

Finite-state automata $A$ and $A ^ { \prime }$ are defined by the transition diagrams shown below.

(a) Find the quotient automaton for A.
(b) Find the quotient automaton for$A ^ { \prime }$ 
(c) Are A and $A ^ { \prime }$  equivalent? Explain.

Quizplus · Accepted Answer

The Answer is a. For

A

:
the 0 -equivalence classes are

\left\{ s _ { 0 } , s _ { 1 } , s _ { 2 } , s _ { 3 } , s _ { 5 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}

.
the 1-equivalence classes are

\left\{ s _ { 0 } , s _ { 1 } , s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}

.
the 2 -equivalence classes are

\left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}

.
the

*

-equivalence classes are

\left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\}

.
The quotient automaton for

A , \bar { A }

, has the following transition diagram:
$a. For A : the 0 -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } , s _ { 2 } , s _ { 3 } , s _ { 5 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the 1-equivalence classes are \left\{ s _ { 0 } , s _ { 1 } , s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the 2 -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the * -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . The quotient automaton for A , \bar { A } , has the following transition diagram: A b. For A ^ { \prime } : the 0 -equivalence classes are \left\{ s _ { 0 } ^ { \prime } , s _ { 1 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\} . the 1 -equivalence classes are \left\{ s _ { 0 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\} . the 2-equivalence classes are \left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\} . the * -equivalence classes are \left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\} . The quotient automaton for A ^ { \prime } , \overline { A ^ { \prime } } , has the following transition diagram: c. The transition diagrams for \bar { A } and \overline { A ^ { \prime } } are identical except for the names of the states. Thus both accept the same language, and since A accepts the same language as \bar { A } and A ^ { \prime } accepts the same language as \overline { A ^ { \prime } } , A and A ^ { \prime } accept the same language. Hence they are equivalent automata.$
A b. For

A ^ { \prime }

:
the 0 -equivalence classes are

\left\{ s _ { 0 } ^ { \prime } , s _ { 1 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\}

.
the 1 -equivalence classes are

\left\{ s _ { 0 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\}

.
the 2-equivalence classes are

\left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\}

.
the

*

-equivalence classes are

\left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\}

.
The quotient automaton for

A ^ { \prime } , \overline { A ^ { \prime } }

, has the following transition diagram: $a. For A : the 0 -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } , s _ { 2 } , s _ { 3 } , s _ { 5 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the 1-equivalence classes are \left\{ s _ { 0 } , s _ { 1 } , s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the 2 -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . the * -equivalence classes are \left\{ s _ { 0 } , s _ { 1 } \right\} , \left\{ s _ { 5 } \right\} , \left\{ s _ { 2 } , s _ { 3 } \right\} , \left\{ s _ { 4 } , s _ { 6 } \right\} . The quotient automaton for A , \bar { A } , has the following transition diagram: A b. For A ^ { \prime } : the 0 -equivalence classes are \left\{ s _ { 0 } ^ { \prime } , s _ { 1 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\} . the 1 -equivalence classes are \left\{ s _ { 0 } ^ { \prime } , s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 2 } ^ { \prime } \right\} . the 2-equivalence classes are \left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\} . the * -equivalence classes are \left\{ s _ { 0 } ^ { \prime } \right\} , \left\{ s _ { 1 } ^ { \prime } \right\} , \left\{ s _ { 3 } ^ { \prime } , s _ { 4 } ^ { \prime } \right\} \left\{ s _ { 2 } ^ { \prime } \right\} . The quotient automaton for A ^ { \prime } , \overline { A ^ { \prime } } , has the following transition diagram: c. The transition diagrams for \bar { A } and \overline { A ^ { \prime } } are identical except for the names of the states. Thus both accept the same language, and since A accepts the same language as \bar { A } and A ^ { \prime } accepts the same language as \overline { A ^ { \prime } } , A and A ^ { \prime } accept the same language. Hence they are equivalent automata.$ c. The transition diagrams for

\bar { A }

and

\overline { A ^ { \prime } }

are identical except for the names of the states. Thus both accept the same language, and since

A

accepts the same language as

\bar { A }

and

A ^ { \prime }

accepts the same language as

\overline { A ^ { \prime } } , A

and

A ^ { \prime }

accept the same language. Hence they are equivalent automata.

Finite-State Automata AAA And A′A ^ { \prime }A′ Are Defined by the Transition Diagrams Shown Below

Finite-State Automata $A$ And $A ^ { \prime }$ Are Defined by the Transition Diagrams Shown Below