kleene

Please download to get full document.

View again

of 3
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Categories
Published
CS 360 Naomi Nishimura State elimination Note: this information is meant to cover some material used in class but absent from the textbook. This is not intended to be comprehensive or a replacement for attending lecture. This handout is based on material developed by Jeff Shallit
  CS 360Naomi Nishimura State elimination Note: this information is meant to cover some material used in class but absent from thetextbook. This is not intended to be comprehensive or a replacement for attending lecture.This handout is based on material developed by Jeff Shallit for CS 360, in turn based onmaterial developed by Eric Bach of the University of Wisconsin.In Section 3.2.2 of the textbook, an algorithm is given for constructing a regular expressionfrom a DFA. The algorithm presented here (and in class) is simpler to understand, and appliesto NFA’s and   -NFA’s as well.As in the textbook, we will remove states from the automaton, replacing labels of arcs, sothat in the end a single regular expression is formed. The single regular expression will be thelabel on an arc that goes from the start state to the accepting state, and this will be the onlyarc in the automaton.The algorithm forms the simpler automaton as follows. In step 1, we modify the automatonto have a start state that is not an accepting state and has no transitions in (either self-loops orfrom other states). In step 2, we create an equivalent automaton that has a single accepting statewith no transitions out. These will be the two states that remain at the end of the algorithm.In step 3, the other states are eliminated, in any order. Details of the algorithm follow, alongwith a running example, illustrated below. 1 2 3 4aababab   3 4  Step 1 If the start state is an accepting state or has transitions in, add a new non-accepting startstate and add an   -transition between the new start state and the former start state. 1 2 3 4aababab0   3 4   CS 360: State elimination  2 Step 2 If there is more than one accepting state or if the single accepting state has transitions out,add a new accepting state, make all other states non-accepting, and add an   -transition fromeach former accepting state to the new accepting state. 1 2 3 4aababab0 0   5  Step 3 For each non-start non-accepting state in turn, eliminate the state and update transitionsaccording to the procedure given on page 99 of the textbook, Figures 3.7 and 3.8. The followingillustrations depict the removal of states 1, 2, 3, and 4 in that order. 2 3 4baba0 0   5baaa  ab +   CS 360: State elimination  3 3 4bb0 0   5  b  +  a ( aa ) ∗ ( ab  +   ) a  +  a ( aa ) ∗ ( ab  +   ) 40 0   5 ( a  +  a ( aa ) ∗ ( ab  +   )) b ∗ b   + ( a  +  a ( aa ) ∗ ( ab  +   )) b ∗ ( b  +  a ( aa ) ∗ ( ab  +   )) b ∗ b ( b  +  a ( aa ) ∗ ( ab  +   )) b ∗ 0 0   5 (( b  +  a ( aa ) ∗ ( ab  +   )) b ∗ b )(( a  +  a ( aa ) ∗ ( ab  +   )) b ∗ b ) ∗ (   + ( a  +  a ( aa ) ∗ ( ab  +   )) b ∗ ) ( b  +  a ( aa ) ∗ ( ab  +   )) b ∗ +
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks