Report

COSC 3340: Introduction to Theory of Computation University of Houston Dr. Verma Lecture 4 1 Lecture 4 UofH - COSC 3340 - Dr. Verma Formal definition of NFA acceptance Define *(q, w) as a set of states: p ε *(q, w) if there is a directed path from q to p labeled w – *(q0, 1) = ? – Ans: {q0, q1} *(q0, 11) = ? – 2 Example: consider NFA of Lecture 3 Ans: {q0, q1, q2} Lecture 4 UofH - COSC 3340 - Dr. Verma NFA acceptance (contd.) 3 w is accepted by NFA M iff *(q0, w) F is nonempty. L(M) = {w in * | w is accepted by M}. Lecture 4 UofH - COSC 3340 - Dr. Verma NFA vs. DFA Is NFA more powerful than DFA? – Theorem: – For every NFA M there is an equivalent DFA M' Proof Idea: – – Ans: No. NFA is in a set of states at any point during reading a string. DFA will use a lot of states to keep track of this. Important Assumption: – No transition labeled by epsilon. (Will get rid of this assumption later.) 4 Lecture 4 UofH - COSC 3340 - Dr. Verma Equivalent DFA construction. NFA M = (Q, , , s, F) DFA M' = (Q', , , s', F') where: – – – – Q' = 2Q s' = {s} F' = {P | P F is nonempty} ({p1, p2, pm}, ) = *(p1, ) *(p2, ) ... *(pm, ) i.e. find all the states that can be reached on from all the NFA states in a DFA state. 5 Lecture 4 UofH - COSC 3340 - Dr. Verma Example: Equivalent DFA construction NFA 6 Lecture 4 UofH - COSC 3340 - Dr. Verma Equivalent DFA construction (contd.) 7 Lecture 4 UofH - COSC 3340 - Dr. Verma How to handle epsilon transitions? Define e-closure of state q as *(q, ). – 8 notation: e-closure(q). Example: Lecture 4 UofH - COSC 3340 - Dr. Verma Handling epsilon transitions (contd.) Extend e-closure to sets of states by: – e-closure({s1, ... , sm}) = e-closure(s1) ... e-closure(sm) Now let s' = e-closure({s}). and, ({p1,..., pm}, ) = e-closure(*(p1, )) ... e-closure(*(pm, )) to complete construction of DFA. 9 Lecture 4 UofH - COSC 3340 - Dr. Verma Example: Handling epsilon transitions. 10 Lecture 4 UofH - COSC 3340 - Dr. Verma DFA = ? 11 Lecture 4 UofH - COSC 3340 - Dr. Verma Language Operations 1. Concatenation. Notation: LL' or just LL' – 2. Kleene Star. Notation: L* – L* = { w in * | w = w1...wk for some k >= 0 and each wi in L}. Examples: if L = {a(2n+1) | n >= 0}. L' = {b(2n) | n > = 0}. LL' = ? – Ans: LL' = {a(2n+1) b(2m) | n, m > = 0} L* = ? – Ans: {an | n >= 0} U, ., * are called regular operations. 12 L L' = {uv | u in L, v in L'}. Lecture 4 UofH - COSC 3340 - Dr. Verma Closure properties of regular languages. Previously we saw closure under and . New: Regular languages are closed under – – – 13 Concatenation Kleene star Complement. Lecture 4 UofH - COSC 3340 - Dr. Verma Examples L = {w in {a,b}* | w has even a’s } 14 Lecture 4 UofH - COSC 3340 - Dr. Verma Examples L' = {w in {a,b}* | w has at least one b} 15 Lecture 4 UofH - COSC 3340 - Dr. Verma Construction for LL' 16 L’’ = (K,,,s,F) K = K1 K2 s = s1 F = F2 = 1 2 F1 X {e} X {s2} Lecture 4 UofH - COSC 3340 - Dr. Verma L* and L'* L* M = (K, , , s, F) K = {s} K1 F = {s} F1 = 1 F1 X {e} X {s1} {(s, e, s1)} Given M1 = (K1, , 1, s1, F1) L’* 17 Lecture 4 UofH - COSC 3340 - Dr. Verma Complement of L and L' Complement of L Complement of L’ 18 Lecture 4 UofH - COSC 3340 - Dr. Verma General Construction for Complement DFA M = (K, , δ, s, F) K = K1 s = s1 F = K - F1 δ = δ1 L(M) = Complement of L(M1) DFA M1 = (K1, , δ1, s1, F1) Exercise: Will this construction work for NFAs? Explain your answer. 19 Lecture 4 UofH - COSC 3340 - Dr. Verma