1CS 172: Computability and ComplexityDFAs and NFAsSanjit A. SeshiaEECS, UC BerkeleyAcknowledgments: L.von Ahn, L. Blum, M. BlumS. A. Seshia 2What we’ll do today• Introduction to – DFA : Deterministic Finite Automata– NFA : Non-deterministic Finite Automata• DFAs to/from regular languages• Operations on regular languages• Non-determinism and NFAs• HW1 is out today2S. A. Seshia 300,100111start state q0transitionsaccept/final states, Fstates, QDFA TerminologyS. A. Seshia 4Q is the set of statesΣ is the alphabetδδδδ : Q ×××× Σ → Q is the transition functionq0∈∈∈∈ Q is the start stateF ⊆⊆⊆⊆ Q is the set of accept statesA finite automaton is a 5-tuple M = (Q, Σ, δδδδ, q0, F)L(M) = the language of machine M= set of all strings machine M accepts3S. A. Seshia 5Acceptance (Formal Def.)• M is a DFA with alphabet Σ• An input string (word) w is a sequence w1w2w3… wnwhere each wi∈∈∈∈ Σ– ε denotes the empty string• M accepts w if “after fully reading w it ends in an accept state”– If there is a sequence of states s0, s1, … snsuch that• s0= q0• si= δ(si-1, wi) • sn∈∈∈∈ F S. A. Seshia 6Regular Language• M is a DFA with alphabet Σ• L(M) is the set of strings accepted by M– L(M) is the language of M– M recognizes L(M)• Regular language: set of strings that is the language of some DFA• The set of all possible strings is denoted Σ*• Is Σ*regular?4S. A. Seshia 70,1q0L(M) = ?S. A. Seshia 8q0q10110L(M) = ?5S. A. Seshia 9Design a DFAL(M) ={ w | w has an even number of 1s}S. A. Seshia 10q0q10011L(M) ={ w | w has an even number of 1s}6S. A. Seshia 11Sample Regular Languages•ΣΣΣΣ*• ∅∅∅∅• { w | w ends in a 1}• { w | w has an even number of 1s}S. A. Seshia 12Points to PonderFor a DFA M = (Q, Σ, δ, q0, F) • Number of states, |Q|, is finite• Is Σ a finite set? • Is L(M) a finite set? – Does it have a finite representation?• Suppose you are given the 5-tuple in advance, so you know |Q|, etc. Do you know how long you will have to run M on any input? Input length is finite, but unbounded by parameters of M7S. A. Seshia 13Operations on Regular LanguagesGiven: Two regular languages A and B• Union: A ∪∪∪∪ B = {w | w ∈∈∈∈ A or w ∈∈∈∈ B}• Intersection: A ∩∩∩∩ B = ?• Complementation: A = {w | w ∈∈∈∈ A}• Reverse: AR= {w1w2…wk| wkwk-1…w1∈∈∈∈ A}• Concatenation: A ···· B = {vw | v ∈∈∈∈ A and w ∈∈∈∈ B}• Star: A*= {w1w2…wk| k ≥≥≥≥ 0 and each wi∈∈∈∈ A}S. A. Seshia 14Closure• If you perform an operation on one/more regular languages, is the result also a regular language?• Example: Is A ∪∪∪∪ B regular if A and B are regular?YES8S. A. Seshia 15Union TheoremThe union of two regular languages is also a regular languageProof (Hints)?S. A. Seshia 16An Exampleq0q10011p0p111009S. A. Seshia 17q0,p0q1,p011q0,p1q1,p1110000S. A. Seshia 18Closure under Reverse• Reverse: AR= {w1w2…wk| wkwk-1…w1∈∈∈∈ A}• Regular languages are closed under reverse. Here’s an attempt to prove it:– Given M that recognizes A– What if you could “run it backwards”?– Construct MRas M with all arrows reversed & accept state becomes start state– Is MRguaranteed to be a DFA?10S. A. Seshia 19101010,10S. A. Seshia 20101010,10What happens with 100?We will say that the NFA accepts if there is a way to make it reach an accept stateNon-determinism11S. A. Seshia 21Q is the set of statesΣ is the alphabetδδδδ : Q ×××× Σεεεε→ 2Qis the transition functionq0∈∈∈∈ Q is the start stateF ⊆⊆⊆⊆ Q is the set of accept statesA non-deterministic finite automaton (NFA) is also a 5-tuple M = (Q, Σ, δδδδ, q0, F)2Qis the set of subsets of Q and Σε= Σ ∪∪∪∪ {ε}L(M) defined in the same way as for DFAsS. A. Seshia 22NFA Example0, 1110,10, εεεεHow does this differ from the DFAs we’ve seen?• Epsilon transitions• Missing transitions from some states• More than 1 transition from a state on same symbolWhat’s its language?12S. A. Seshia 23NFAs and DFAs• Is every DFA also an NFA? • Is every NFA a DFA?S. A. Seshia 24Tree of ComputationsDeterministicComputationNon-DeterministicComputationaccept or rejectacceptrejectstuck13S. A. Seshia 25Where does non-determinism arise?• In practice: From lack of information– A precise model might use randomness (probabilistic transitions between states), but we might not know the probabilities– Important! Non-determinism is not the same as probabilistic computation.• NFAs and DFAs are “equivalent”!– Their languages are the same• More on this next time– But NFAs are simplerS. A. Seshia 26NFAs are simpler than DFAsAn NFA that recognizes the language {1}:11 0,10,10A DFA that recognizes the language {1}:14S. A. Seshia 27Union Theorem for NFAs• If you have two NFAs N1and N2, with languages L1and L2, how can we get the NFA for L1∪∪∪∪ L2? S. A. Seshia 28Next Steps• Read Sipser 1.2 in preparation for next