Class 11: Formal definition of Nondeterministic Finite Automata

Reading

Sections 2.2 of Theory of Computing, A Gentle Introduction

Homework

1. Draw the diagram of the nondeterministic finite automaton defined by the following 5-tuple:

   ({0,1,2,3}, {a,b,c}, {(0,a,0), (0,b,0), (0,c,0), (0,a,1), (0,e,2), (1,b,0), (1,c,0), (2,a,2), (2,b,2), (2,c,2), (2,b,3), (3,a,2), (3,c,2)}, 0, {2,3})

2. Draw the 5-tuple representing the following machine:

   

3. Draw a nondeterministic finite automtaton that accepts the language of all strings over alphabet {a,b,c} that contain the substring caab. For example, bacabcaabba would be accepted wheras acaacab would be rejected.

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 strings over {a,b,c} of the form: a string containing an even number of a's followed by a string that starts with b and ends with c. Note: This example is not so compelling, a better one would be the language of strings of the form: "a string containing an even number of a's followed by a string whose length is odd".

So, for example, the string cabcacbac should be accepted by your machine, becase cabcacbac breaks it up into a piece with an even number of a's followed by a piece that starts with b and ends with c.

One easy way to do this is to construct two machines, one for "even number of a's" and one for "starts with b and ends with c", and hook them together with an e-transistion. Specifically, the e-transistion takes us from the accepting state of the first machine to the start state of the second machine. That way, you'll leave the first machine knowing you've read a string containing an even number of a's, and start the second machine knowing you can only end up in an accepting state if you subsequently read something that starts with b and ends in c.

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 e-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 e-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 deterministicfinite 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:

1. in the nondeterministic case we have "missing" transitions, so our δ wouldn't be defined for all elements of its domain
2. 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
3. in the nondeterministic case we have e-transitions which are defined for e, not for an element of the alphabet - i.e. our δ needs to function outside of its domain

Obviously our goold friend δ, the transition function, isn't going to work for nondeterministic machines. There are several ways of working around this. the one we'll use is the one the book uses. The transitions will be represented by ordered 3-tuples of the form (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 Δ.

Definition: a nondeterministic finite automaton is an ordered 5-tuple (Q,Σ,Δ,s,W) where

• Q is the set of states
• Σ is the alphabet
• Δ ⊆ Q x (&Sigma ∪ {e}) 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" straight from DFAs, as long as we add the possibility of e-transitions to "yields". However, they kind of mean different things. 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. So, the big question is how do we define "accept" and "reject" for NDFAs?

NDFA M = (Q,Σ,Δ,s,W) accepts string W if there exists a sequence of configurations C1, C2, ..., Ck such that C1 = (s,w), C2 ∈ Q x W, and C1 ⇒ C2 ⇒ ... ⇒ Ck.