CMSC 330: Organization of Programming LanguagesSlide 2Slide 3Slide 4Describing Regular ExpressionsCreating Regular ExpressionsSlide 7Creating DFACreating NFACMSC 330: Organization of Programming LanguagesDiscussion Section, 2/11Examples of REs & Finite AutomataWhat do we know about REs?•The Formal Vocab–Symbol–Alphabet–String–Language•The Special Symbol: ε•The Formal Operations–Concatenation, e.g. /ab/–Union, e.g. /a|b/–Kleene Closure, e.g. a*ha(ha)*More About REs•Operator Precedence–Kleene closure * > concatenation > union |–Like arithmetic, use parentheses to override•How’d we get from here to DFA again?Anything but DFA!!!!CMSC 330 5Describing Regular Expressions●0(0|1)*0●All strings beginning and ending in 0●((ε|0)1*)*●All strings ●(0|1)*0(0|1)(0|1)●All strings with 0 as third digit from rightCMSC 330 6Creating Regular ExpressionsFor all strings of 0’s and 1’s that…a) Begin in 1–1(0|1)*a) End in 1–(0|1)*1a) Contain 00–(0|1)*00(0|1)*a) Do not contain 00–(01|1)*(ε|0)Finite Automata•We can further formalize regular expressions as finite automata.–Why? To reason about them.•What are the choices?–Deterministic–Non-deterministic•Why have two choices?•What are the differences?CMSC 330 8Creating DFAFor all strings of 0’s and 1’s that…a) Begin in 1b) End in 1c) Contains 00d) Do not contain 00100,10110 0110,10 0110,1Swap final / non-final states!CMSC 330 9Creating NFAFor all strings of 0’s and 1’s that…a) Begin in 1b) End in 1c) Contain 00d) Do not contain 0010,110 00,100,10,11εεε0Based on regular
View Full Document