1CMSC 330: Organization of Programming LanguagesTheory of Regular ExpressionsDFAs and NFAsCMSC 330 2Reminders• Project 1 due Sep. 24• Homework 1 posted• Exam 1 on Sep. 25• Exam topics list posted• Practice homework (and solutions) postedCMSC 330 3Previous Course Review• {s | s defined} means the set of string s such that s is chosen or defined as given•s ∈ A means s is an element of the set A• De Morgan’s Laws:• There exists and for all symbols•Etc…CMSC 330 4Review• Basic parts of a regular expression?• What does a DFA do?• Basic parts of a DFA?concatenation, |, *, εεεε, ∅∅∅∅,{a}alphabet, set of states, start state, final states,transition function (,Q,q0,F,)CMSC 330 5Example DFA–S0= “Haven’t seen anything yet” OR “seen zero or more b’s” OR “Last symbol seen was a b”–S1= “Last symbol seen was an a”–S2= “Last two symbols seen were ab”–S3= “Last three symbols seen were abb”• Language?• (a|b)*abbCMSC 330 6Notes about the DFA definition• Can not have more than one transition leaving a state on the same symbol – the transition function must be a valid function)• Can not have transitions with no or empty labels– the transitions must be labeled by alphabet symbols2CMSC 330 7Nondeterministic Finite Automata (NFA)•AnNFA is a 5-tuple (, Q, q0, F, ) where– is an alphabet–Qis a nonempty set of states–q0 Q is the start state–F Q is the set of final states• There may be 0, 1, or many– Q x ({}) x Q specifies the NFA's transitions• Transitions on are allowed – can optionally take these transitions without consuming any input• Can have more than one transition for a given state and symbol• An NFA accepts s if there is at least one path from its start to final state on sCMSC 330 8NFA for (a|b)*abb•ba– Has paths to either S0 or S1– Neither is final, so rejected• babaabb– Has paths to different states– One leads to S3, so acceptedCMSC 330 9• Language?• (ab|aba)*Another example DFACMSC 330 10NFA for (ab|aba)*• aba– Has paths to states S0, S1• ababa– Has paths to S0, S1– Need to use -transitionCMSC 330 11Relating R.E.'s to DFAs and NFAs• Regular expressions, NFAs, and DFAs accept the same languages!DFA NFAr.e.cantransformcantransformcantransform(we’ll discuss this next)CMSC 330 12Reducing Regular Expressions to NFAs• Goal: Given regular expression e, construct NFA: <e> = (, Q, q0, F, )– Remember r.e. defined recursively from primitive r.e. languages– Invariant: |F| = 1 in our NFAs• Recall F = set of final states• Base case: a<a> = ({a}, {S0, S1}, S0, {S1}, {(S0, a, S1)} )3CMSC 330 13Reduction (cont’d)• Base case: <> = (, {S0}, S0, {S0}, )• Base case: <> = (, {S0, S1}, S0, {S1}, )CMSC 330 14Reduction (cont’d)• Induction: AB<A><B>CMSC 330 15Reduction (cont’d)• Induction: AB–<A> = (A, QA, qA, {fA}, A)–<B> = (B, QB, qB, {fB}, B)– <AB> = (AB, QAQB, qA, {fB}, AB{(fA, , qB)} )<A><B>CMSC 330 16Practice• Draw the NFA for these regular expressions using exactly the reduction method:–ab– hello• Write the formal (5-tuple) NFA for the same regular expressionsCMSC 330 17Reduction (cont’d)• Induction: (A|B)CMSC 330 18• Induction: (A|B)–<A> = (A, QA, qA, {fA}, A)–<B> = (B, QB, qB, {fB}, B)– <(A|B)> = (AB, QAQB{S0,S1}, S0, {S1},AB{(S0,,qA), (S0,,qB), (fA,,S1), (fB,,S1)})Reduction (cont’d)4CMSC 330 19Practice• Draw the NFA for these regular expressions using exactly the reduction method:–ab| bc– hello | hi• Write the formal NFA for the same regular expressionsCMSC 330 20Reduction (cont’d)• Induction: A*CMSC 330 21Reduction (cont’d)• Induction: A*–<A> = (A, QA, qA, {fA}, A)– <A*> = (A, QA{S0,S1}, S0, {S1},A{(fA,,S1), (S0,,qA), (S0,,S1), (S1,,S0)})CMSC 330 22Practice• Draw the NFA for these regular expressions using exactly the reduction method:– (ab | bc*)*– hello | (hi)*• Write the formal NFA for the same regular expressionsCMSC 330 23Reduction Complexity• Given a regular expression A of size n...Size = # of symbols + # of operations• How many states does <A> have?– 2 added for each |, 2 added for each *–O(n)– That’s pretty good!CMSC 330 24PracticeDraw NFAs for the following regular expressions and languages:• (0|1)*110*• 101*|111• all binary strings ending in 1 (odd numbers)• all alphabetic strings which come after “hello” in alphabetic order• (ab*c|d*a|ab)d5CMSC 330 25Handling ε-transitionsWhat if we want to remove all those unneeded ε-transitions?First, some definitions:•We say:– if it is possible to transition from state p to state q taking only ε-transitions–if ∃ p, p1, p2, … pn, q ∈ Q (p ≠ q) such that CMSC 330 26ε-closure• For any state p, the ε-closure of p is defined as the set of states q such that • {q | }CMSC 330 27Example• What’s the ε-closure of S2 in this NFA?• {S2, S0}CMSC 330 28Example• Find the ε-closure for each of the states in this NFA:CMSC 330 29Example• Make the NFA for the regular expression – (0|1*)111(0*|1)• Find the epsilon closure for each of the states of your
View Full Document
Unlocking...