Lecture Notes 7 Equivalence of Regular Languages and FSMs 1Equivalence of Regular Languages and FSMs Read K & S 2.4 Read Supplementary Materials: Regular Languages and Finite State Machines: Generating Regular Expressions from Finite State Machines. Do Homework 8. Equivalence of Regular Languages and FSMs Theorem: 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 Strategies Possible 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) commutativity 2. 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 FSM We'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 FSMs 2For Every Regular Expression There is a Corresponding FSM Formalizing 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 star Clearly we can construct an FSM for any finite language, and thus for ∅ and all the singleton strings. If we could show that the class of languages accepted by FSMs is also closed under the operations of union, concatenation, and Kleene star, then we could recursively 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 Expressions An FSM for ∅: An FSM for ε (∅*): An FSM for a single element of Σ: Closure of FSMs Under Union To 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 Concatenation To 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 FSMs 3Closure of FSMs Under Kleene Star To 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 Complementation To 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 q2 Closure of FSMs Under Intersection L1 ∩ L2 = L1 L2 Write this in terms of operations we have already proved closure for: • Union • Concatenation • Kleene star • Complementation An Example (b ∪ ab*a)*ab*Lecture Notes 7 Equivalence of Regular Languages and FSMs 4For Every FSM There is a Corresponding Regular Expression Proof: (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 Proof Idea 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 J Idea 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), or 2. Go from I to K, then from K to K any number of times, then from K to J, in each
View Full Document
Unlocking...