Type your answers for problems 5-9. Hand-drawn diagrams for problems 1-3 are acceptable.

For each of the languages L1 and L2 given below, show a state diagram of a deterministic finite state automaton (DFA) that accepts the language. The alphabet of the two languages is

{a, b}.

L1={x | x ? (a+b)* contains 3n+2 a?s for n = 0}

L2={x | x ? (a+b)* contains 2n+1 b?s for n = 0}

Show a state diagram of a DFA that accepts the intersection of the two languages given in problem 1.

Show a state diagram of a push-down automaton (PDA) that accepts the language given below. The alphabet of the language is {a, b, c}.

{a2i bk c3i | i, k > 0}

Circle one of the letters R, C or N for each language given below. Circle R if the language is regular (and of course also context-free), circle C if the language is context free but not regular, and circle N if the language is not context free. Note that xR denotes the string x written backward.

{ ai bj ck | i > j > k = 0} Circle one: R C N

{ ai bj ck | i, j, k = 0} Circle one: R C N

{ ai bk | i, k ? 0, and i < k} Circle one: R C N

{ ai bk | i, k ? 0} Circle one: R C N

{ x an xR | n ? 0 and x ? (a+b)*} Circle one: R C N

{ x xR x x | x ? (a+b)*} Circle one: R C N

{ xR x | x ? (a+b)*} Circle one: R C N

{ a2i+1 b2k+1 | i, k ? 0} Circle one: R C N

| i, k ? 0} Circle one: R C N

| i, j = 0} Circle one: R C N

{ a2i b3k

{ a5i bj

{ a5i b2i | i ? 0 } Circle one: R C N

{ ai bj ck | i > j and j, k = 0} Circle one: R C N

Use the pumping lemma for regular languages to prove that the language L given below is not regular. The alphabet of L is

?={a, b}

L = { ai bk | 2i > k }

You may write your proof in your preferred format, but your proof must precisely specify the information required for each of the five blanks in the following template. Note that the third blank requires an integer as an exponent. Use p as the pumping length. Define all variables that you use in your proof.

Proof. The sentence s= _ contradicts the pumping lemma because for all x, y, z ??*

such that xyz=s, if |xy| ?p and |y| >0, then y must be and xy in L because _ . QED.

z =

is not

You need to use the following concepts for problems 6 and 9. Two strings x and y are distinguishable with respect to a language L if there is a string d such that one of xd and yd is a sentence in L but the other is not. The string d is known as a distinguisher for x and y. A set of strings are pair-wise distinguishable if there is a distinguisher for each pair of strings in the set.

Show a set D of 5 strings that are pairwise distinguishable with respect to the language given below. For each pair of strings in the set D, give a distinguisher. The alphabet of L is ? = {a}.

L = {a5n | n = 0 }

(Bonus credit) Without minimizing a DFA that accepts the language L given in problem 6 and without using the pumping lemma, prove that any DFA that accepts the language L must have 5 or more states.

Show an infinite set of strings that are pairwise distinguishable with respect to the language A given below. Also give a distinguisher for each pair of strings in the infinite set.

A={ an bn | n = 0 }

(Bonus credit) Assume that an infinite set required by problem

8 exists. Without using the pumping lemma, prove that the language A given above is not regular.