# cs3102: Theory of Computation (aka cs302: Discrete ...

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

## Recently Viewed Presentations

• What is a timeline? ... -used to describe the time before the birth of Christ ; the dates get smaller as time passes, so the larger the number, the earlier the date ... Era - a long period of time...
• RTI Lab: Research-Based Intervention to Manage Challenging Behaviors in the Classroom Jim Wright www.interventioncentral.org
• These cities will be Techno-centric, People-centric and Eco-centric. The FM professional must brace up for the management of the mega cities. 3. Emergence of new business models. ... AI carry out task with greater precision and accuracy.
• SREDNJA ŠKOLA ZLATAR REZULTATI NATJECANJA 2014./2015. 58. Glazbene svečanosti hrvatske mladeži u Varaždinu Djevojački zbor Srednje škole Zlatar Ime i prezime učenica Rezultat (državno natjecanje) Mentor Parlaj Klara Nadine, 1.u Mikulec Iva, 3.g1 2. mjesto Josipa Hopek, prof. Pavetić Izidora,...
• Testing & Usability: Making It Work Joseph A. Busch & Ron Daniel, Jr. Agenda Qualitative methods Quantitative methods Qualitative taxonomy testing methods Walk ...
• Improving Community Living disAbility Services. Human Services Research Institute. 7690 SW Mohawk Street. Tualatin, OR 97062 +1 503-924-3783 . www.hsri.org. John . Agosta . [email protected]
• hyporesponsive to ESA therapy? A. The primary cause of the hyporesponsiveness to ESA therapy is. overt iron deficiency. B. The chronic inflammation associated with his osteomyelitis has. produced a deficiency in H1Fα resulting in anemia resistant to ESA. therapy. C....
• The London Protocol Background While it is sometimes straightforward to identify a particular action or omission as the immediate cause of an incident, closer analysis usually reveals a series of events leading up to an adverse outcome. The identification of...