Report

NFA vs. DFA CSC 361 NFA vs. DFA 1 NFAs vs. DFAs NFAs can be constructed from DFAs using transitions: Called NFA- Suppose M1 accepts L1, M2 accepts L2 CSC 361 Then an NFA can be constructed that accepts: L1 U L2 (union) L1L2 (concatenation) L1* (Kleene star) NFA vs. DFA 2 Closure Properties of NFA-s M1 M2 L(M)* L(M1) U L(M2) M M1 M2 L(M1) L(M2) CSC 361 NFA vs. DFA 3 NFA to DFA Conversion CSC 361 NFA vs. DFA 4 DFA vs NFA Deterministic vs nondeterministic For every nondeterministic automata, there is an equivalent deterministic automata Finite acceptors are equivalent iff they both accept the same language L(M1) = L(M2) CSC 361 NFA vs. DFA 5 DFA vs NFA Deterministic vs nondeterministic In DFA, label resultant state as a set of states For a set of |Q| states, there are exactly 2Q subsets CSC 361 {q1, q2, q3,…} Finite number of states NFA vs. DFA 6 Removing Nondeterminism By simulating all moves of an NFA-λ in parallel using a DFA. λ-closure of a state is the set of states reachable using only the λ-transitions. CSC 361 NFA vs. DFA 7 NFA-λ p2 λ a p1 λ q1 p3 λ λ q2 p5 a p4 t (q1, a) { p1, p2, p3, p4, p5} CSC 361 NFA vs. DFA 8 λ – Closure Selected λ closures q1: {q1,q2} p1: {p1,p2,p3} q2: {q2} CSC 361 NFA vs. DFA 9 Equivalence Construction Given an NFA-λ M1, construct a DFA M2 such that L(M) = L(DM). Observe that CSC 361 A node of the DFA = Set of nodes of NFA-λ Transition of the DFA = Transition among set of nodes of NFA- λ NFA vs. DFA 10 Special States to Identify Start state of DFA = - closure({q0}) Final/Accepting state of DFA = All subsets of states of NFA-λ that contain an accepting state of the NFA-λ Dead state of DFA = CSC 361 NFA vs. DFA 11 Example a a b q1 q0 λ a q2 c CSC 361 NFA vs. DFA 12 Example Identify λ-closures CSC 361 q0: {q0} q1: {q1} q2: {q1,q2} NFA vs. DFA 13 Example Identify transitions Start with λ-closure of start state {q0}: Where can you go on each input? a: {q0,q1,q2} So, {q0,q1,q2} is a state in the DFA b, c: Nowhere, so {Φ} is in the DFA Next slide… Next, do the same for {q0,q1,q2} and {Φ} Find destinations from any node in the set for each of the three alphabet symbols CSC 361 Subsequent slide… NFA vs. DFA 14 All steps from {q0} {q0} a {q0} b c CSC 361 {q0,q1,q2} NFA vs. DFA 15 All steps from {q0,q1,q2} a a {q0} {q0,q1,q2} {q1} c b c b {q1,q2} a,b,c CSC 361 NFA vs. DFA 16 All steps from {q1} and {q1,q2} b {q1} a,c c b {q1,q2} CSC 361 a {q1} NFA vs. DFA 17 Equivalent DFA a a {q0} {q0,q1,q2} b b,c a,c b {q1} c c {q1,q2} b a a,b,c CSC 361 NFA vs. DFA 18 NFA vs. DFA Theorem: Given any NFA N, then there exists a DFA D such that N is equivalent to D • Proven by constructing a general NFA and showing that the closure exists among the possible DFA states P(Q) • Every possible transition goes to an element of P(Q) CSC 361 NFA vs. DFA 19 Limitations of Finite Automata Obvious: Can only accept languages that can be represented in finite memory! Can this language be represented with a FA? L(M)=(aibi | i n) How about this one? CSC 361 L(M)=(aibi | i > 0) NFA vs. DFA 20 Exercise: Convert this NFA p2 λ a p1 λ q1 p3 λ λ q2 p5 a p4 CSC 361 NFA vs. DFA 21