Gradiance Online Accelerated Learning

Prentice-Hall Addision-Wesley

Gradiance Online Accelerated Learning

Deterministic Finite Automata

Which automata define the same language?

Note: (b) and (d) use transitions on strings. You may assume that there are nonaccepting intermediate states, not shown, that are in the middle of these transitions, or just accept the extension to the conventional finite automaton that allows strings on transitions and, like the conventional FA accepts strings that are the concatenation of labels along any path from the start state to an accepting state.

b and c

a and d

b and d

a and b

The finite automaton below:

accepts no word of length zero, no word of length one, and only two words of length two (01 and 10). There is a fairly simple recurrence equation for the number N(k) of words of length k that this automaton accepts. Discover this recurrence and demonstrate your understanding by identifying the correct value of N(k) for some particular k. Note: the recurrence does not have an easy-to-use closed form, so you will have to compute the first few values by hand. You do not have to compute N(k) for any k greater than 14.

		a)	N(13) = 84
		b)	N(14) = 280
		c)	N(12) = 1366
		d)	N(11) = 10

Here is the transition function of a simple, deterministic automaton with start state A and accepting state B:

	0	1
A	A	B

B	B	A

We want to show that this automaton accepts exactly those strings with an odd number of 1's, or more formally:

δ(A,w) = B if and only if w has an odd number of 1's.

Here, δ is the extended transition function of the automaton; that is, δ(A,w) is the state that the automaton is in after processing input string w. The proof of the statement above is an induction on the length of w. Below, we give the proof with reasons missing. You must give a reason for each step, and then demonstrate your understanding of the proof by classifying your reasons into the following three categories:

Use of the inductive hypothesis.

Reasoning about properties of deterministic finite automata, e.g., that if string s = yz, then δ(q,s) = δ(δ(q,y),z).

Reasoning about properties of binary strings (strings of 0's and 1's), e.g., that every string is longer than any of its proper substrings.

Basis (|w| = 0):

(1)

w = ε because ________

(2)

δ(A,ε) = A because ________

(3)

ε has an even number of 0's because ________

Induction (|w| = n > 0)

(4)

There are two cases: (a) when w = x1 and (b) when w = x0 because ________

Case (a):

(5)

In case (a), w has an odd number of 1's if and only if x has an even number of 1's because ________

(6)

In case (a), δ(A,x) = A if and only if w has an odd number of 1's because ________

(7)

In case (a), δ(A,w) = B if and only if w has an odd number of 1's because ________

Case (b):

(8)

In case (b), w has an odd number of 1's if and only if x has an odd number of 1's because ________

(9)

In case (b), δ(A,x) = B if and only if w has an odd number of 1's because ________

(10)

In case (b), δ(A,w) = B if and only if w has an odd number of 1's because ________

		a)	(7) for reason B.
		b)	(1) for reason A.
		c)	(8) for reason A.
		d)	(5) for reason A.

Examine the following DFA:

This DFA accepts a certain language L. In this problem we shall consider certain other languages that are defined by their tails, that is, languages of the form (0+1)*w, for some particular string w of 0's and 1's. Call this language L(w). Depending on w, L(w) may be contained in L, disjoint from L, or neither contained nor disjoint from L (i.e., some strings of the form xw are in L and others are not).

Your problem is to find a way to classify w into one of these three cases. Then, use your knowledge to classify the following languages:

L(1111001), i.e., the language of regular expression (0+1)*1111001.
L(11011), i.e., the language of regular expression (0+1)*11011.
L(110101), i.e., the language of regular expression (0+1)*110101.
L(00011101), i.e., the language of regular expression (0+1)*00011101.

		a)	L(00011101) is disjoint from L.
		b)	L(11011) is contained in L.
		c)	L(11011) is neither disjoint from L nor contained in L.
		d)	L(110101) is contained in L.

Examine the following DFA:

Identify in the list below the string that this automaton accepts.

		a)	10000			b)	01111			c)	1100111			d)	101111