1CMSC 330: Organization of Programming LanguagesExamples of REs & Finite AutomataCMSC 330 2Describing Regular Expressionsa) 0(0|1)*0– All strings beginning and ending in 0b) ((ε|0)1*)*– All strings c) (0|1)*0(0|1)(0|1)– All strings with 0 as third digit from rightCMSC 330 3Creating Regular ExpressionsFor all strings of 0’s and 1’s that…a) Begin in 1– 1(0|1)*b) End in 1– (0|1)*1c) Contains 00– (0|1)*00(0|1)*d) Do not contain 00– (01|1)*(ε|0)CMSC 330 4Creating NFAFor all strings of 0’s and 1’s that…a) Begin in 1b) End in 1c) Contains 00d) Do not contain 0010,110 00,100,10,11εεεεεεεεεεεε0Based on regular expressionεεεεCMSC 330 5Creating 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 6εεεεεεεεa) Construct NFA b) Accept ababbab7,5,1,2,6,8,7,5,3,4,6,8,7,5,1,2,6,8,7,5,3,4,6,8,7,5,3,4,6,8,7,5,1,2,6,8,7,5,3,4,6,8 acceptFor RE (a | b )*a3 4b1 256εεεεεεεεεεεε78εεεεεεεεεεεε2CMSC 330 7For RE (a | b )*c) Reduce NFA to DFA– Start = ε-closure(7) = {7,5,1,3,8}– R = {{7,5,1,3,8}}– r ∈R = {7,5,1,3,8}// mark DFA state– move ({7,5,1,3,8}, a) = {2}• e = ε-closure({2}) = {2,6,8,7,5,1,3} // new DFA state• R = R ∪ {2,6,8,7,5,1,3} // add to R• δ = δ ∪ ({7,5,1,3,8}, a, {2,6,8,7,5,1,3})– move ({7,5,1,3,8}, b) = {4}• e = ε-closure({4}) = {4,6,8,7,5,1,3} // new DFA state• R = R ∪ {4,6,8,7,5,1,3} // add to R• δ = δ ∪ ({7,5,1,3,8}, b, {4,6,8,7,5,1,3})CMSC 330 8For RE (a | b )*– R = {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}– r ∈R = {2,6,8,7,5,1,3} // mark DFA state– move ({2,6,8,7,5,1,3}, a) = {2}• e = ε-closure({2}) = {2,6,8,7,5,1,3} // existing DFA state• δ = δ ∪ ({2,6,8,7,5,1,3}, a, {2,6,8,7,5,1,3})– move ({2,6,8,7,5,1,3}, b) = {4}• e = ε-closure({4}) = {4,6,8,7,5,1,3} // existing DFA state• δ = δ ∪ ({2,6,8,7,5,1,3}, b, {4,6,8,7,5,1,3})CMSC 330 9For RE (a | b )*– R = {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}– r ∈R = {4,6,8,7,5,1,3} // mark DFA state– move ({4,6,8,7,5,1,3}, a) = {2}• e = ε-closure({2}) = {2,6,8,7,5,1,3} // existing DFA state• δ = δ ∪ ({4,6,8,7,5,1,3}, a, {2,6,8,7,5,1,3})– move ({4,6,8,7,5,1,3}, b) = {4}• e = ε-closure({4}) = {4,6,8,7,5,1,3} // existing DFA state• δ = δ ∪ ({4,6,8,7,5,1,3}, b, {4,6,8,7,5,1,3})– R = {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}• No more unmarked states to process– Fd= {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}• Since 8 ∈ FnCMSC 330 10For RE (a | b )*– Resulting DFAΣ= {a,b}R = {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}r0= {7,5,1,3,8} Fd= {{7,5,1,3,8}, {2,6,8,7,5,1,3}, {4,6,8,7,5,1,3}}δ = { ({7,5,1,3,8}, a, {2,6,8,7,5,1,3}), ({7,5,1,3,8}, b, {4,6,8,7,5,1,3}), ({2,6,8,7,5,1,3}, a, {2,6,8,7,5,1,3}), ({2,6,8,7,5,1,3}, b, {4,6,8,7,5,1,3}), ({4,6,8,7,5,1,3}, a, {2,6,8,7,5,1,3}), ({4,6,8,7,5,1,3}, b, {4,6,8,7,5,1,3}) }CMSC 330 11For RE (a | b )*– NFA to DFA reduction pictorial7,5,1,3,82,6,8,7,5,1,34,6,8,7,5,1,3abababCMSC 330 12For RE (a | b )*d) Minimize DFA– Initial partitions• Accept →{1,2,3} →P1• Reject →Ø– Split partition?• move(1,a) →P1• move(2,a) →P1• move(3,a) →P1• move(1,b) →P1• move(2,b) →P1• move(3,b) →P1Not required, minimization doneababab123P1P1a,bAfter cleanup3CMSC 330 13εεεεεεεεFor RE (a* | b* )*a) Construct NFA b) Accept ababbab11,9,3,1,2,4,10,12,11,9,7,5,6,8,10,12,11,9,3,1,2,4,10,12…111 2εεεεεεεεεεεεεεεε3εεεεεεεεεεεεa4εεεε5 67εεεεεεεεb8εεεε910εεεεεεεεεεεε12CMSC 330 14For RE (a* | b* )*c) Reduce NFA to DFA– Start = ε-closure(1) = {11,9,3,1,4,7,5,8,10,12}– R = {{11,9…12}}– r ∈R = {11,9…12}}}– move ({11,9…12}, a) = 2• ε-closure({2}) = {2,11,9…12}– move ({11,9,…,12}, b) = 6• ε-closure({6}) = {6,11,9…12}– …– NFA to DFA reduction pictorial11,9,3,1,4,7,5,8,10,122,11,9,3,1,4,7,5,8,10,126,11,9,3,1,4,7,5,8,10,12abababCMSC 330 15For RE (a* | b* )*d) Minimize DFA– Initial partitions• Accept →{1,2,3} →P1• Reject →Ø– Split partition?• move(1,a) →P1• …Not required,minimization donee) Compare 2 minimized DFAs– Identical up to state names!ababab123P1P1a,bAfter
View Full Document
Unlocking...