Equivalence of Regular Expressions and FSMsGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinRegular Language• Recall that a language is a (possibly infinite) set of strings over somespecified alphabet• For any FSM M , the language accepted by M is the set of all stringsaccepted by M• A language is regular if it is equal to the set of strings defined by someregular expression• We’ll prove that regular expressions and FSMs are equivalent in power– Every FSM accepts a regular language– Every regular language is accepted by some FSMTheory in Programming Practice, Plaxton, Spring 2005Every FSM Accepts a Regular Language• Fix an FSM M, and number the states of M from 1 to n arbitrarily• Let Rkijdenote the set of strings that cause M to transition from statei to state j without visiting an intermediate state numbered higherthan k• Claim: For all i, j, and k, Rkijis a regular language– We’ll prove the claim by induction on k ≥ 0– Why does the claim imply the desired result?• The key observation for carrying out the induction step is thatRkij= Rk−1ij∪ Rk−1ik(Rk−1kk)∗Rk−1kjTheory in Programming Practice, Plaxton, Spring 2005Every Regular Language is Accepted by Some FSM• We prove this result in three stages:– First, we define the notion of a nondeterministic FSM and prove thatdeterministic and nondeterministic FSMs are equivalent in power– Second, we define the notion of a nondeterministic FSM with ²-transitions and prove that nondeterministic FSMs with and without²-transitions are equivalent in power– Finally, we prove that every regular language is accepted by somenondeterministic FSM with ²-transitionsTheory in Programming Practice, Plaxton, Spring 2005Nondeterministic Finite State Machines• A nondeterministic FSM is the same as a (deterministic) FSM exceptthat the transition function maps each state/symbol pair to a (possiblyempty) subset of the states, as opposed to a single state• When we run a nondeterministic machine on a given input string, werepeatedly choose the next state arbitrarily from the subset specifiedby the transition function– An execution is good if the transition function never specifies anempty subset from which to choose the next state; otherwise, it isbad– A nondeterministic FSM M is said to accept a string x if thereexists some good execution of M on string x that terminates in anaccepting stateTheory in Programming Practice, Plaxton, Spring 2005Simulation of a Nondeterministic FSM by a(Deterministic) FSM• Fix a nondeterministic FSM M and let S denote the set of states of M• We simulate M via an FSM M0with 2|S|states, one corresponding toeach subset of S• The key idea is to define the transition function of M0so that thefollowing condition holds for any input x– The execution of M0on input x terminates in the state of M0corresponding to the set of all states α of M such that some goodexecution of M on input x terminates in state α• How do we define the accepting states of M0in order to complete theconstruction properly?Theory in Programming Practice, Plaxton, Spring 2005Nondeterministic FSMs with ²-Transitions• A nondeterministic FSM with ²-transitions is the same as anondeterministic FSM except that we allow transitions labeled ² (andcalled ²-transitions) that do not consume an input symbol• The notion of a good execution is the same as we had for anondeterministic FSM without ²-transitions, except that whenever wefind ourselves in a state with one or more outgoing ²-transitions, wehave the option to make such a transition without consuming an inputsymbol• Acceptance is then defined in the same way as for nondeterministicFSMs:– A nondeterministic FSM M with ²-transitions is said to accept astring x if there exists some good execution of M on string x thatterminates in an accepting stateTheory in Programming Practice, Plaxton, Spring 2005Simulation of a Nondeterministic FSM with²-Transitions by a (Ordinary) Nondeterministic FSM• Fix a nondeterministic FSM M with ²-transitions• We’d like to create a nondeterministic FSM M0without ²-transitionsthat simulates M• Let the states of M0be the same as the states of M• We define the transition function of M0so that there is a transitionfrom state α to state β on input symbol a if and only if M admitsa path from α to β where one transition is labeled with a and theremaining transitions are ²-transitions• How do we define the accepting states of M0in order to complete theconstruction properly?Theory in Programming Practice, Plaxton, Spring 2005Every Regular Language is Accepted by someNondeterministic FSM with ²-Transitions• Recall that regular languages are defined in terms of regular expressions• We prove the claim by structural induction on the definition of a regularexpression• Base case: We need to exhibit machines that accept the languages ∅,{²}, and {a} where a is an arbitrary symbol in the alphabet• For the induction step, we need to consider regular expressionsformed by concatenation, union, and Kleene closure of smaller regularexpressionsTheory in Programming Practice, Plaxton, Spring