CSC 341: January 31, 2007

From CSWiki

Previous Lecture Next Lecture

Contents 1 Instructor's notes for the class session 1.1 Leftovers 1.2 From Sipser, section 1.2 1.3 Other activities 2 Study questions 2.1 Proposed Solutions

Instructor's notes for the class session

Leftovers

The construction of the union machine in Theorem 1.25; a Scheme program that implements it.

The regular operations on languages: union, concatenation, star.

From Sipser, section 1.2

Conceptual models of nondeterminism: magical self-duplication, prescience. Depth-first search of the alternative lines of computation, with backtracking in the event of rejection, is not a good model for nondeterministic machines generally, because some of our machines never halt or get blocked (so that there is no point to backtrack from). It is possible to implement non-determinism with breadth-first search, although most people don't find this conception very intuitive.

-transitions provide additional options and can be taken no matter what character is at the front of the input channel (and even if the input has already been exhausted).

The type of the transition function for a nondeterministic finite automaton: .

Theorem 1.39: For every nondeterministic finite automaton, there is a deterministic finite automaton that recognizes the same language. The construction; a Scheme program that implements it.

Other activities

Exercise 1.7, Problem 1.31.

Study questions

1. How many deterministic finite automata have the states q₁,q₂,q₃,q₄ (and no others) and the alphabet ? How many non-deterministic finite automata?
2. Let M be any deterministic finite automaton, let A be the alphabet of M, and let A' be any superset of A. Prove that there is a deterministic finite automaton M' with alphabet A' such that L(M) = L(M'). (I call this proposition the Alphabet Extension Lemma for deterministic finite automata.)
3. In a nondeterministic finite automaton, what happens if all of the copies of the machine die before reaching the end of the input, by reaching states from which no out-transitions are available?
4. Could a nondeterministic finite automaton have only -transitions, and no transitions at all on symbols from its alphabet? What language(s), if any, could be recognized by such an NFA?
5. Sipser observes that a completely rigorous proof of Theorem 1.39 would proceed "by induction on the number of steps in the computation." What computation is he referring to? How would one set up that formal proof?

Proposed Solutions

1. • With a DFA, each state may have up to three transitions leaving it (one for each symbol in the alphabet), and each of these may point to one of three other choices. We can think of this as always having three transitions which may just point nowhere, in other words 4³ possibilities per state. If we are treating each state as a unique entity, these possibilities apply to each of the four states, in (4³)⁴ total ways. Each of these possibilities may me made into different automata depending on choice of start state and accept states, respectively. So the total number of automata with the specified states and alphabet is .
   • Answer for NFAs
2. M' can be constructed by starting with M and adding a new transition from each state of M to the reject state for every character in A' that is not in A.
3. The NFA rejects its input.
4. Such a machine could exist. It would only accept at most the empty string, since it only has epsilon transitions. This follows directly from the formal definition of an NFA -- there can't exist a sequence of states following the required conditions to accept a nonempty string if all the transitions are epsilon transitions. Depending on the configuration of the transitions and the accept states, it might not even accept the empty string.
5. The formal proof by induction would first set up the DFA that simulates the NFA, as is done in the less formal proof. After that, we would prove by induction that every string accepted by the NFA is accepted by the DFA. The variable of induction would be the length of the string. For the inductive step, we would show that if every string of length n accepted by the NFA is accepted by the DFA, then every string of length n+1 accepted by the NFA is accepted by the DFA. Similarly, we would prove by induction that every language accepted by the DFA is accepted by the NFA, again using the string length as the variable of induction.

Presumably Sipser is referring to the computation represented by the finite automata. To prove by induction, one would show that if a NFA of n steps that has an equivalent DFA, we can construct an equivalent DFA for an NFA of n + 1 steps. Then we simply must show that a base case (perhaps a DFA with one state and no transitions) is true, and by induction any larger case will be shown true.

---

Previous Lecture Next Lecture

Front Door