use algorithm 6.2.2 to construct a regular expression for the languages accepted by the automaton.

Algorithm 6.2.2 Construction of a Regular Expression from a Finite Automaton input: state diagram G of a finite automaton with one accepting state Let q0 be the start state and qt the accepting state of G. 1. repeat 1.1. choose a node qi that is neither q0 nor qt 1.2. delete the node qi from G according to the following procedure: 1.2.1 for every j,k not equal to i (this includes j=k ) do i) if wj,i=,wi,k= and wi,i=. then add an arc from node j to node k labeled wj,iwi,k ii) if wj,i=,wi,k= and wi,i=, then add an arc from node qj to node qk labeled wj,i(wi,i)wi,k iii) if nodes qj and qk have arcs labeled w1,w2,,ws connecting them, then replace the arcs by a single arc labeled w1w2ws 1.2.2 remove the node qi and all arcs incident to it in G until the only nodes in G are q0 and qt 2. determine the expression accepted by G that accepts (ab)abba(ab), the strings over {a,b} that contain the substring abba. The states q0,q1,q2,q3 record the progress toward obtaining the substring abba. The states of the machine are A nondeterministic approach to accepting (ab)abba(ab) is illustrated by the machine Algorithm 6.2.2 Construction of a Regular Expression from a Finite Automaton input: state diagram G of a finite automaton with one accepting state Let q0 be the start state and qt the accepting state of G. 1. repeat 1.1. choose a node qi that is neither q0 nor qt 1.2. delete the node qi from G according to the following procedure: 1.2.1 for every j,k not equal to i (this includes j=k ) do i) if wj,i=,wi,k= and wi,i=. then add an arc from node j to node k labeled wj,iwi,k ii) if wj,i=,wi,k= and wi,i=, then add an arc from node qj to node qk labeled wj,i(wi,i)wi,k iii) if nodes qj and qk have arcs labeled w1,w2,,ws connecting them, then replace the arcs by a single arc labeled w1w2ws 1.2.2 remove the node qi and all arcs incident to it in G until the only nodes in G are q0 and qt 2. determine the expression accepted by G that accepts (ab)abba(ab), the strings over {a,b} that contain the substring abba. The states q0,q1,q2,q3 record the progress toward obtaining the substring abba. The states of the machine are A nondeterministic approach to accepting (ab)abba(ab) is illustrated by the machine