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.

a)

a and c

b)

b and c

c)

a and d

d)

a and b

2.

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(1111001) is disjoint from L.
		b)	L(00011101) is disjoint from L.
		c)	L(110101) is contained in L.
		d)	L(1111001) is contained in L.

3.

Examine the following DFA: Identify in the list below the string that this automaton accepts.

		a)	1100111			b)	101111			c)	100			d)	0110

4.

Identify which automata define the same language and provide the correct counterexample if they don't. Choose the correct statement from the list below.

		a)	(c) and (f) define the same language.
		b)	(a) and (c) define the same language.
		c)	(c) and (b) do not define the same language and the following counterexample shows it. String 0012 is accepted by one and not by the other.
		d)	(b) and (f) define the same language.

5.

Here is a nondeterministic finite automaton: Some input strings lead to more than one state. Find, in the list below, a string that leads from the start state A to three different states (possibly including A).

		a)	1010			b)	00100			c)	101000			d)	1000

6.

Convert the following nondeterministic finite automaton: to a DFA, including the dead state, if necessary. Which of the following sets of NFA states is not a state of the DFA that is accessible from the start state of the DFA?

a)

{B}

b)

{A,C}

c)

{B,C}

d)

{}

7.

The following nondeterministic finite automaton: accepts which of the following strings?

a)

1100101

b)

01010110

c)

1110100

d)

01010011