PS1 is due now! cs3102: Theory of Computation Class 4: Nondeterminism Spring 2010 University of Virginia David Evans Adding Nondeterminism a

b 1 2 b a, b Deterministic machine: at every step, there is only one choice

Nondeterministic machine: at some steps, there may be more than one choice. Nondeterminism in Practice Nondeterminism in Theory Omnipotent: Machine splits into a new machine for each choice; if any machine accepts, accept.

Omniscient: Whenever it has to make a choice, machine always guesses right. Example NFA a 1 b 2

a, b 3 Defining DFAs A deterministic finite automaton is a 5-tuple: Q finite set (states) S finite set (alphabet) d : Q S Q transition function

q0 Q start state FQ set of accepting states How do we need to change this to support nondeterminism? Defining NFAs A nondeterministic finite automaton is a 5-tuple: Q finite set (states) S finite set (alphabet)

function : Q ( [ f g) ! transition P (Q) q0 Q start state FQ set of accepting states Output of transition function is a set of states, not just one state. Computation Model of NFA Computation Model of NFA

Is an NFA more powerful than a DFA? Power of Machines Languages that can be recognized by an A Languages that can be

recognized by a B A and B are non-comparable. Power of Machines Languages Languages that can be that can

be recognized recognized by an A by a B B is less powerful than A: (1) Some A can recognize every language a B can recognize. (2) There is some language

that can be recognized by an A but not by any B. Power of Machines Languages that can be recognized by byan a BA

A and B are equal: (1) every language that can be recognized by an A can be recognized by some B (2) every language that can be recognized by a B can be recognized by some A Power of NFA/DFA Easy part: is there any language a DFA can recognize that cannot be recognized by an NFA?

Hard part: is there any language an NFA can recognized that cannot be recognized by a DFA? L(NFA) L(DFA) A nondeterministic finite automaton is a 5-tuple: Q finite set (states) S finite set (alphabet)

: Q ( [ f g) ! P (Q) q0 Q start state FQ set of accepting states Proof by construction: Construct the NFA N corresponding to any DFA A = (Q, S, d, q0,F): N = (Q, S, d, q0,F) where q Q, d(q, q, ) = reject a S , d(q, q, a) = {d (q, q, a) }

Power of NFA/DFA Easy part: is there any language a DFA can recognize that cannot be recognized by an NFA? No: NFAs are at least as powerful as DFAs. Hard part: is there any language an NFA can recognized that cannot be recognized by a DFA? L(DFA) L(NFA) L(DFA) L(NFA)

Example Conversion a 1 b 2 a, b 3

a 1 b 2 3

a, b {1} {} {2} {1, 2} {3}

{2, 3} {1, 3} {1,2, 3} a 1

b 2 3 a, b b {1} a

{} {2} a {1, 2} b {3}

a {1, 3} b {2, 3} b {1,2, 3} Converting NFAs to DFAs

How many states may be needed for the DFA corresponding to and NFA with N states? How much bigger is the transition function for the DFA corresponding to and NFA with N states? Regular Expressions something formatted like an [email] address [email protected]

[A-Za-z0-9]*@[A-Za-z0-9]*(. [A-Za-z0-9]*)* This matches most email addresses. Matching the full spec of all possible email addresses is left as exercise. Regular Expression Base: Language aS {a} {} {} Induction: R1, R2 are regular expressions

R1 R2 L(q, R1) L(q, R2) R1 R2 { xy | xL(q, R1) and yL(q, R2) } R1* { xn | xL(q, R1) and n 0 } How powerful are Regular Expressions? Is there a Regular Expression that describes the same language as any NFA? Is there some NFA that describes the same language as any Regular Expression?

L(RE) L(NFA) Base: Language aS {a} Proof by construction. Trivial to draw NFAs for {} Each of these languages. {} Induction: R1, R2 are regular expressions R1 R2 L(q, R1) L(q, R2)

R1 R2 { xy | xL(q, R1) and yL(q, R2) } R1* { xn | xL(q, R1) and n 0 } L(RE) L(NFA) Base: Language aS {a} {}

{} Proof by construction. Trivial to draw NFAs for Each of these languages. L(RE) L(NFA) Induction: R1, R2 are regular expressions R1 R2 L(q, R1) L(q, R2) R1 R2

{ xy | xL(q, R1) and yL(q, R2) } R1* { xn | xL(q, R1) and n 0 } Proof by induction and construction. Assume there are NFAs A1 and A2 that recognize the languages L(q, R1) and L(q, R2). Show how to construct an NFA that recognizes the produced language for each part. Proving: R1 R2 Charge

PS2 will be posted by tomorrow Finish reading Chapter 1 Thursday: how to prove a language is nonregular