Equivalence of Regular Languages and FSMsAn Algorithm to Generate a Regular Grammar from an NDFSMRegularRegularEquivalence of Regular Languages and FSMsRead K & S 2.4Read Supplementary Materials: Regular Languages and Finite State Machines: Generating Regular Expressions from Finite State Machines.Do Homework 8.Equivalence of Regular Languages and FSMsTheorem: The set of languages expressible using regular expressions (the regular languages) equals the class of languages recognizable by finite state machines. Alternatively, a language is regular if and only if it is accepted by a finite state machine.Proof StrategiesPossible Proof Strategies for showing that two sets, a and b are equal (also for iff):1. Start with a and apply valid transformation operators until b is produced. Example: Prove: A (B C) = (A B) (A C)A (B C) = (B C) A commutativity= (B A) (C A) distributivity= (A B) (A C) commutativity2. Do two separate proofs: (1) a b, and (2) b a, possibly using totally different techniques. In this case, we show first (by construction) that for every regular expression there is a corresponding FSM. Then we show, by induction on the number of states, that for every FSM, there is a corresponding regular expression.For Every Regular Expression There is a Corresponding FSMWe'll show this by construction.Example:a*(b )a*Review - Regular Expressions The regular expressions over an alphabet * are all strings over the alphabet {(, ), , , *} that can be obtained as follows:1. and each member of is a regular expression.2. If , are regular expressions, then so is .3. If , are regular expressions, then so is .4. If is a regular expression, then so is *.5. If is a regular expression, then so is ().6. Nothing else is a regular expression.We also allow and +, etc. but these are just shorthands for * and *, etc. so they do not need to be considered for completeness.Lecture Notes 7 Equivalence of Regular Languages and FSMs1For Every Regular Expression There is a Corresponding FSMFormalizing the Construction: The class of regular languages is the smallest class of languages that contains and each of the singleton strings drawn from , and that is closed under Union Concatenation, and Kleene starClearly we can construct an FSM for any finite language, and thus for and all the singleton strings. If we could show that theclass of languages accepted by FSMs is also closed under the operations of union, concatenation, and Kleene star, then we couldrecursively construct, for any regular expression, the corresponding FSM, starting with the singleton strings and building up the machine as required by the operations used to express the regular expression.FSMs for Primitive Regular ExpressionsAn FSM for : An FSM for (*):An FSM for a single element of :Closure of FSMs Under UnionTo create a FSM that accepts the union of the languages accepted by machines M1 and M2:1. Create a new start state, and, from it, add -transitions to the start states of M1 and M2.Closure of FSMs Under ConcatenationTo create a FSM that accepts the concatenation of the languages accepted by machines M1 and M2:1. Start with M1. 2. From every final state of M1, create an -transition to the start state of M2.3. The final states are the final states of M2.Lecture Notes 7 Equivalence of Regular Languages and FSMs2Closure of FSMs Under Kleene StarTo create an FSM that accepts the Kleene star of the language accepted by machine M1:1. Start with M1.2. Create a new start state S0 and make it a final state (so that we can accept ).3. Create an -transition from S0 to the start state of M1.4. Create -transitions from all of M1's final states back to its start state.5. Make all of M1's final states final.Note: we need a new start state, S0, because the start state of the new machine must be a final state, and this may not be true of M1's start state.Closure of FSMs Under ComplementationTo create an FSM that accepts the complement of the language accepted by machine M1:1. Make M1 deterministic.2. Reverse final and nonfinal states.A Complementation Example a b q1 q2Closure of FSMs Under IntersectionL1 L2 = L1 L2Write this in terms of operations we have already proved closure for: Union Concatenation Kleene star ComplementationAn Example(b ab*a)*ab*Lecture Notes 7 Equivalence of Regular Languages and FSMs3For Every FSM There is a Corresponding Regular ExpressionProof:(1) There is a trivial regular expression that describes the strings that can be recognized in going from one state to itself ({} plus any other single characters for which there are loops) or from one state to another directly (i.e., without passing through any other states), namely all the single characters for which there are transitions.(2) Using (1) as the base case, we can build up a regular expression for an entire FSM by induction on the number assigned to possible intermediate states we can pass through. By adding them in only one at a time, we always get simple regular expressions, which can then be combined using union, concatenation, and Kleene star.Key Ideas in the ProofIdea 1: Number the states and, at each induction step, increase by one the states that can serve as intermediate states. b a a 1 2 3 I K JIdea 2: To get from state I to state J without passing through any intermediate state numbered greater than K, a machine may either:1. Go from I to J without passing through any state numbered greater than K-1 (which we'll take as the induction hypothesis),or2. Go from I to K, then from K to K any number of times, then from K to J, in each case without passing through any intermediate states numbered greater than K-1 (the induction hypothesis, again).So we'll start with no intermediate states allowed, then add them in one at a time, each time building up the regular expression with operations under which regular languages are closed.The FormulaAdding in state k as an intermediate state we can use to go from i to j, described using paths that don't use k: i
View Full Document
Unlocking...