**Reading**-
Sections 2.2 of
*Theory of Computing, A Gentle Introduction* **Homework**- Printout the homework and answer the questions on that paper.

**Designing Nondeterministic Finite Automata - Part I**-
Your previous homework gave you a non-deterministic machine
and a string and asked you to trace several different
computations for that string. Remember: the machine accepts
the string as long as there is at least one computation that
gets it in an accepting state after all input has been read!
Now we'll try the other way round: you design a machine given
a specification of the strings it's supposed to accept.
Design a machine that accepts the language of all strings over {1,0,x} of the form uv, where v=1x0 and u consists of any number of copies a block of x's with a 1 on each side. Strings like

*1xx11x11x0*or*1xxxx11x0*or*1xxx1111x0*or*1x11x0*or*1x0*.One way to do this is to design a machine that acccepts

*1x0*,and a machine that accepts zero or more copies of*1*followed by zero or more*x*'s followed by*1*, and then tie them together. **Designing Nondeterministic Finite Automata - Part II**-
Let's try another excercise: Construct a machine that accepts
the language of all strings over
*{a,b,c}*that start and end with the same letter and have length at least 2. This turns out to be quite easy!

This is, of course, too easy! So let's try to make a machine that accepts strings that look like some number of strings accepted by the above machine, all tacked end to end. In other words, I should accept a string if it can be broken up into pieces, each of which starts and ends with the same letter and has length at least 2

Hopefully you're starting to see that these λ-transitions make creating new machines from old ones quite easy. In fact we could have done both of our big examples just using regular old non-dterminism --- i.e. two or more transitions for the same state/character combination. However, the λ-transisions let us do things without having to pick apart the original machines and see how they work. That'll help us later when we construct algorithms on nondeterministic machines.

**A formal definition of a nondeterministic finite automaton**-
If we're going to start exploring languages accepted by
nondeterministic finite automata, proving theorems and
constructing algorithms, we're going to need a formal
definition of a
*nondeterministic*finite automaton just like we had for*deterministic*finite automata. If you think about it, the only part of our 5-tuple definition of a deterministic finite automaton that doesn't work for the nondterministic case is δ, the transition function. The problem is threefold:- in the nondeterministic case we have "missing" transitions, so our δ wouldn't be defined for all elements of its domain
- in the nondeterministic case we have more than one possible state for some combinations of state/character, in other words our δ wouldn't be single-valued as a function must be
- in the nondeterministic case we have λ-transitions which are defined for λ, not for an element of the alphabet - i.e. our δ needs to function outside of its domain

*(p,x,q)*, denoting that we have a transition from*p*to*q*reading character (or empty string)*x*. The set of transitions represented this way is called the*transition relation*, and we denote it with Δ.**[**Another equally valid approach would be to make δ a function that returns*subsets*of*Q*, rather than*elements*. In this approach, a "missing transition" is just a state-character combination for which δ returns the empty set. We use 2^{Q}to represent the set of all subsets of*Q*, and then we would write the new prototype for δ as follows: δ:*Q*x(Σ ∪ {λ}) → 2^{Q}.**]****Definition:**a nondeterministic finite automaton is an ordered 5-tuple*(Q,Σ,Δ,s,W)*where*Q*is the set of states (must be finite)- Σ is the alphabet
*Δ ⊆ Q x (Σ ∪ {λ}) x Q*is the transition relation*s ∈ Q*is the start state*W ⊆ Q*is the set of accepting states

This allows us to look at all the same kind of examples we had for deterministic machines, going back and forth from diagram representation to 5-tuple representation.

**5-tuple definition***({q0,q1,q2}, {a,b,c}, {(q0,b,q1),(q1,a,q1),(q1,b,q1), (q1,c,q1),(q1,c,q2)}, q0, {q0,q2})***diagram definition****What about the rules governing how an NDFA computes?**Well, we can borrow the idea of configuration, "yields in one step" and "yields in many steps" from DFAs, as long as we add the possibility of λ-transitions to "yields". However, "yields" kind of mean different things for DFAs versus NDFAs. Instead of*(p,u) ⇒ (q,v)*meaning "if you're in configuration*(p,u)*then after one step you*will*be in configuration*(q,v)*", for NDFAs we may only say that*(q,v)*is one possibility ... there may well be others.**Definition:**For NDFA*M = (Q,Σ,Δ,s,W)*, we say that configuration*(p,v)**yields in one step*configuration*(q,w)*if*x ∈ Σ ∪ {λ}*we have*v = xw*and*(p,x,q) ∈ Δ*. This is sometimes denoted*(p,v) ⇒ (q,w)*, or*(p,v) ⇒*when you need to clearly indicate which machine you're referring to._{M}(q,w)Next we will define the "yields" notion ("yields eventually" or "yields in zero of more steps") just as we did for DFAs.

**Definition:**For NDFA*M = (Q,Σ,Δ,s,W)*, we say that configuration*(p,v)**yields*configuration*(q,w)*if there is some sequence of configurations*(q1,w1), (q2,w2), ..., (qk,wk)*such that*(p,v) = (q1,w1) ⇒ (q2,w2) ⇒ ... ⇒ (qk,wk) = (q,w)**(p,v) ⇒* (q,w)*or, when you need to clearly indicate which machine you're referring to,*(p,v) ⇒**._{M}(q,w)Now the big question is how do we define "accept" and "reject" for NDFAs? Well, we define it the same way as for DFAs, it just means something a little different.

**Definition:**NDFA*M = (Q,Σ,Δ,s,W)*accepts string*w*if*(s,w) ⇒* (q,λ)*for some*q ∈ W*.We can't talk about "the state we're in after all the input has been read", because there may be many possible states to be in after all the input is read (i.e. we have to say a rather than the), or the may be no possible states to be in with all the input read. This uncertainty is captured by the new yields definition, which says that

*(s,w) ⇒* (q,λ)***if there is some sequence of configurations ...**.

Christopher W Brown Last modified: Wed Sep 16 15:41:03 EDT 2009