Regular Languages and Finite State MachinesPlan for the Day:• Regular Expressions• Properties of Regular Expressions• Equivalence of NFAs and Regular Expressions1Regular Expres sionsExercise: For each language, find a regular expressio n that defines it.1. L = {w ∈ {a, b}∗||w| is even}2. L = {w ∈ {a, b}∗|w contains at mos t one b}2Properties of Regular LanguagesDefinitio n: A collection of objects is closed under some binary operation if applying thatoperation to two members of the collection produces another member of the collection.Theorem: The regular languages are closed under union. (That is, if L1, L2are regular, thenL1∪ L2is als o regular . )Proof: in cla ssTheorem: The regular la nguages are closed under concatenation. (That is, i f L1, L2areregular, then L1L2is regular.)Proof: in cla ss3More Closure Properties of Regular LanguagesTheorem: The regular languages ar e closed under the star operation. (That is, if L is aregular language, then L∗is regular.)Proof: in cla ss4Equivalence of NFAs and Regular ExpressionsTheorem: A language is regular if and only if some regular expressio n describes i t .There are two directions. So we will prove the following two lemmas:Lemma: If a language is described by a regular expression, then it is regular.Lemma: If a language is regular, then it is described by a regular expression.5Proof o f Lemma 1Lemma 1: If a language L i s described by a regular expression, then L is regular.Proof: L et L be an arbit r a ry language, and assume that L is described by a regular expressionR. We must s how that L is regular. We will do this by defining an NFA N that recognizes L.There are six cases in the definition of a regular expression that we must consider.1. R = a for some a ∈ Σ. So L(R) = {a}. The following NFA r ecognizes L ( R):a6Proving Equivalence of NFAs and Regular Expressions2. R = ǫ. So L(R) = {ǫ},a nd the following NFA recognizes L(R):7Proof o f Lemma 13. R = ∅. So L(R) = ∅, and the fo l lowing NFA recognizes i t :4. R = R1∪ R25. R = R1R26. R = R∗1For these last three cases, use the constructions given in the proofs of the closure properties(union, concatenation, a nd s tar). 8Proof o f Lemma 2Lemma 2: If a language L i s regular, then it is described by a regular expressi o n.Proof: Let L be an arbitrary language. Assume L is regular. We will show that there is aregular expression R that defines L.Let D be a DFA such that L = L( D). We will show, in 2 steps, how to convert D to a regularexpression R such t hat L = L( R).9Proof o f Lemma 2Step 1: Convert D into a generalized NFA that has regular expressions on its arrows. A GNFAreads blocks of symbols at a t i me, and can move from state q to state p by reading a blockof input symbols that is described by the regular expression on the arrow from st ate q to state p.Some rules about GNFAs:• The start s t ate has outgoing arrows to every other state. Add a new start state to D withan ǫ-arr ow to the old start state.• There is only one final state and it has i ncomi ng arrows from every ot her s t ate. Add a newfinal state with an incoming ǫ-arrow fro m the old final states.• Except for the state and final states (which must be different) , there is an arrow in eachdirection between a ny two states. This includes a self-loop on each state other than thestart a nd final states. Add ∅ t r a ns itions in place of missing transition arrows, and replacemultiple labels on any t r a ns ition arrow by the union of thos e labels.10Proof o f Lemma 2Step 2: Convert the GNFA for D into a regular ex pression. To do this , we remove all statesexcept the start a nd final states from the GNFA, one at a time. We do this in such a way thatthe language o f the updated GNFA remains the same.while the number of st ates > 2:• Pick a st ate qripthat is not the start o r final st a tes.• To r emove qripwithout changing the language of the ma chine, we update the labels on theremaining arrows so that they compensate for the absence of qrip. The new la bel from astate qito state qjis a regular expression that describes all str ings that take the machinefrom qito qjdirectly or via qrip. A description of the updated label is given below:RRRRq qqijrip1234123R u R R *R4 q qi j11Once only the start and final states remain, the regular expression on the ar row from the startstate to the final state is D’s equivalent regular expression.12Equivalence of Regular Expressio ns and FAsExample: Given the following DFA, convert it to an equivalent regular
View Full Document
Unlocking...