WIXLIB

Nondeterministic Finite Automataand Regular ExpressionsCS 2800: Discrete Structures, Spring 2015Sid Chaudhuri

Recap: Deterministic Finite Automaton A DFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})–δ is a transition function δ : Q Σ Q–q0 Q is the start/initial state–F Q is the set of final/accepting states01YesNo10

csunplugged.com, clubpenguin.wikia.com

P NP!!!csunplugged.com, clubpenguin.wikia.com

P NP!!!csunplugged.com, clubpenguin.wikia.com

A NON-deterministic finite automatonlets you try all possible choices inparallel. If ANY choice leads you to thetreasure, the pirate can't harm you!P NP!!!csunplugged.com, clubpenguin.wikia.com

A non-deterministic finite automaton0,1q01q10,1q20,1

A non-deterministic finite automatonDifferent transitionsfrom q0 on input 10,1q01q10,1q20,1

A non-deterministic finite automatonDifferent transitionsfrom q0 on input 10,1q01q10,1q2An NFA accepts a string x if it can getto an accepting state on input x0,1

A non-deterministic finite automaton0,1q01q10,1q2What language does this automaton accept?0,1

A non-deterministic finite automaton0,1q01q10,1q2Answer: All strings ending with 10,1

Another NFA0,1q01q10,1q20,1q3What language does this automaton accept?0,1

Another NFA0,1q01q10,1q20,1q3Answer: All strings with 1 in the penultimate place0,1

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of statesq0q1q2q3

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})q0q1q2q3

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})–δ is a transition function δ : Q Σ 20,1q01q10,1q20,1Qq30,1

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})–δ is a transition function δ : Q Σ 20,1q01q10,1q20,1Only changefrom DFAsQq30,1

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})–δ is a transition function δ : Q Σ 2–q0 Q is the start/initial state0,1q01q10,1q20,1Only changefrom DFAsQq30,1

Non-deterministic Finite Automaton An NFA is a 5-tuple M (Q, Σ, δ, q0, F)–Q is a finite set of states–Σ is a finite input alphabet (e.g. {0, 1})Only changefrom DFAsQ–δ is a transition function δ : Q Σ 2–q0 Q is the start/initial state–F Q is the set of final/accepting states0,1q01q10,1q20,1q30,1

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x–Think of it as trying many options in parallel, andhoping one path gets lucky

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x– Think of it as trying many options in parallel, andhoping one path gets luckyTransition f (state, symbol) is possible

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x– Think of it as trying many options in parallel, andhoping one path gets luckyTransition f (state, symbol) is possible– the NFA treats this as a rejecting path (the stringmay still reach an accepting state by another path)

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x– Think of it as trying many options in parallel, andhoping one path gets luckyTransition f (state, symbol) is possible– the NFA treats this as a rejecting path (the stringmay still reach an accepting state by another path)–A convenient shortcut for our “hell/black-hole” state

Non-deterministic Finite Automaton An NFA accepts a string x if it can get to anaccepting state on input x– Think of it as trying many options in parallel, andhoping one path gets luckyTransition f (state, symbol) is possible– the NFA treats this as a rejecting path (the stringmay still reach an accepting state by another path)–A convenient shortcut for our “hell/black-hole” state–Class convention: Draw all possible transitions for DFA.Not required for NFA (missing transitions lead to hell).

Non-deterministic Finite Automaton Every DFA is an NFA

Non-deterministic Finite Automaton Every DFA is an NFA–If we're strict with our notation, we need to replace thetransitionf (state1, symbol) state2 withf (state1, symbol) {state2}

Non-deterministic Finite Automaton Every DFA is an NFA– If we're strict with our notation, we need to replace thetransitionf (state1, symbol) state2 withf (state1, symbol) {state2}Every NFA can be simulated by a DFA

Non-deterministic Finite Automaton Every DFA is an NFA– If we're strict with our notation, we need to replace thetransitionf (state1, symbol) state2 withf (state1, symbol) {state2}Every NFA can be simulated by a DFA– i.e. they accept exactly the same language

Non-deterministic Finite Automaton Every DFA is an NFA– If we're strict with our notation, we need to replace thetransitionf (state1, symbol) state2 withf (state1, symbol) {state2}Every NFA can be simulated by a DFA– i.e. they accept exactly the same language–Exponential blowup: if the NFA has n states, the DFAncan require up to 2 states

Thought for the Day #1Find an NFA with n states that can't bensimulated by a DFA with less than 2 states

Every NFA can be simulated by a DFA

Every NFA can be simulated by a DFAapqarNFA(fragment)

Every NFA can be simulated by a DFAapqarNFA(fragment)DFA (fragment){p}a{q, r}

Every NFA can be simulated by a DFA“Subset construction”apqaMain idea: ONE state of DFAtracks current states of ALLevolving paths of NFArNFA(fragment)DFA (fragment){p}a{q, r}(This is merely illustrative – formal construction on following slides)

Every NFA can be simulated by a DFANFASpecificationStatesAlphabetTransition FunctionInitial StateAccepting StatesEquivalent DFA

Every NFA can be simulated by a DFASpecificationStatesAlphabetTransition FunctionInitial StateAccepting StatesNFAEquivalent DFA(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')

Every NFA can be simulated by a DFANFAEquivalent DFASpecification(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')StatesQ2QAlphabetTransition FunctionInitial StateAccepting States

Every NFA can be simulated by a DFANFAEquivalent DFASpecification(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')StatesQ2QAlphabetΣΣTransition FunctionInitial StateAccepting States

Every NFA can be simulated by a DFANFAEquivalent DFASpecification(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')StatesQ2QAlphabetΣΣTransition Functionδδ'(S, a) s S δ(s, a)Initial StateAccepting States

Every NFA can be simulated by a DFANFAEquivalent DFASpecification(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')StatesQ2QAlphabetΣΣTransition Functionδδ'(S, a) s S δ(s, a)Initial Stateq0q'0 {q0}Accepting States

Every NFA can be simulated by a DFANFAEquivalent DFASpecification(Q, Σ, δ, q0, F)(2Q, Σ, δ', q'0, F')StatesQ2QAlphabetΣΣTransition Functionδδ'(S, a) s S δ(s, a)Initial Stateq0q'0 {q0}Accepting StatesFF' {S 2Q S F }

Why NFAs?

Why NFAs? They can be way more compact than DFAs

Why NFAs? They can be way more compact than DFAsq01q10,10,1q30,1NFAq2

Why NFAs? They can be way more compact than DFAs1q01q10,10,1q30,1NFAq2q000 10q001 010q010 1100q1011100q100q011q1100q111Equivalent minimal DFA1

Why NFAs? They can be way more compact than DFAs1q01q10,10,1q30,1NFA q2q000 10q001 010q010 1100q1011100q100q011q1100q111Equivalent minimal DFAIt's easier to directly convert regular expressions(“wildcard search” on steroids) to NFAs1

XKCD

Playing with regexes http://regex101.com/ http://rubular.com/ http://www.google.com/search?q online regex tester

Regular expressions (“regex”-es) aredefined by structural induction(start with simple base expressions, construct morecomplicated ones recursively)

Empty setL( )

Empty stringL(ε) {ε}

Literal characterL(x) {x}e.g. L(1) {1}, L(2) {2}, L(a) {a}

ConcatenationL(AB) {ab a L(A), b L(B)}e.g. L(12) {12}, L(aabb) {aabb}

ConcatenationL(AB) {ab a L(A), b L(B)}e.g. L(12) {12}, L(aabb) {aabb},L(aε) ?

ConcatenationL(AB) {ab a L(A), b L(B)}e.g. L(12) {12}, L(aabb) {aabb},L(aε) {a}

ConcatenationL(AB) {ab a L(A), b L(B)}e.g. L(12) {12}, L(aabb) {aabb},L(aε) {a}, L(a ) ?

ConcatenationL(AB) {ab a L(A), b L(B)}e.g. L(12) {12}, L(aabb) {aabb},L(aε) {a}, L(a )

AlternationL(A B) L(A) L(B)e.g. L(1 2) {1, 2}, L(aa bb) {aa, bb}

AlternationL(A B) L(A) L(B)e.g. L(1 2) {1, 2}, L(aa bb) {aa, bb},L(a ε) ?

AlternationL(A B) L(A) L(B)e.g. L(1 2) {1, 2}, L(aa bb) {aa, bb},L(a ε) {a, ε}

AlternationL(A B) L(A) L(B)e.g. L(1 2) {1, 2}, L(aa bb) {aa, bb},L(a ε) {a, ε}, L(a ) ?

AlternationL(A B) L(A) L(B)e.g. L(1 2) {1, 2}, L(aa bb) {aa, bb},L(a ε) {a, ε}, L(a ) {a}

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .}

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) ?

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .}

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) ?

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, .}

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, .},L(ε*) ?

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, .},L(ε*) {ε}

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, .},L(ε*) {ε}, L( *) ?

Kleene starL(A*) {ε} { x1x2.xn n N, xi L(A) }e.g. L(a*) {ε, a, aa, aaa, aaaa, .},L((ab)*) {ε, ab, abab, ababab, .},L((a b)*) {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, .},L(ε*) {ε}, L( *) {ε}

An NFA accepts a string x if it can get to an accepting state on input x – Think of it as trying many options in parallel, and hoping one path gets lucky Transition f (state, symbol) is possible – the NFA treats this as a rejecting path (the s