CS154 Assignment #1

Due Monday, January 17, 2000, 3:15PM

Deadline Extended to Noon 1/18 Because of MLK Holiday

(25 pts.) In the book and the notes, we defined delta-hat by a recursion on the last symbol, as delta-hat(q,wa) = delta(delta-hat(q,w),a). We could just as well have defined delta-hat by recursion on the first symbol, i.e., delta-hat(q,bx) = delta-hat(delta(q,b),x). The basis rule is delta-hat(q,epsilon) = q for both definitions. We expect that these definitions give the same answers, and the intuitive argument is that both definitions describe the path from state q with a given string as the label. However, we need a formal proof, and it is a good exercise to construct one carefully.
To be precise, define delta-hat by:
1. delta-hat(q,epsilon) = q.
2. delta-hat(q,wa) = delta(delta-hat(q,w),a).
Define a new function f by:
1. f(q,epsilon) = q.
2. f(q,bx) = f(delta(q,b),x).
Your task is to prove, by induction on the length of y (and no other way --- we really want to see an induction), that delta-hat(q,y) = f(q,y).
(25 pts.) Design a deterministic finite automaton to accept the set of binary strings that, when interpreted as an integer, is divisible by 5. Note that the most significant digit is the first to be read. Give the five-tuple notation for your automaton, with the transition function expressed as a table. Then, draw the transition diagram for your FA. Hint: Think of each state as representing a particular remainder when the number seen so far is divided by 5. To simplify, you may make the reasonable assumption that the empty string represents integer 0, and thus is one of the accepted strings.
(25 pts.) Below is the transition table of an NFA with start state p and accepting states q and s.

0 1

p {q,s} {q}

q {r} {q,r}

r {s} {p}

s {} {p}

Use the subset construction to find an equivalent DFA.
(25 pts.) Design an NFA to accept the set of strings of 0's and 1's that either:
1. End in 010 and have 011 somewhere preceding, or
2. End in 101 and have 100 somewhere preceding.
In order to make sure that you use nondeterminism, your NFA should have no more than 13 states and 15 arcs. You may represent your NFA by a transition diagram.

	0	1
p	{q,s}	{q}
q	{r}	{q,r}
r	{s}	{p}
s	{}	{p}