Problem $1.(4$ points$)$

Let L be the language AnBn $=\{$a$^$nb$^$n $|$ n $0\}.$

$1.$ Find two distinct strings x and y that are L$-$indistinguishable. Explain

why they are L$-$indistinguishable.

$2.$ Find an infinite set of pairwise L$-$distinguishable strings. Explain why

they are L$-$distinguishable.

Problem $2.(3$ points$)$

Draw the diagrams for the finite automata that accept the following languages:

$1.$ L$1=\{$a$,$ b$\}\{$a$\}.$

$2.$ L$2=\{$ba$\}.$

Problem $3.(4$ points$)$

Find the finite automaton M $=($Q$,\{$a$,$ b$\},$ q$0,$ A$,$ $)$ that accepts the language L

given by the intersection of the two languages from the previous exercise, i$.$e$.$

L $=$ L$1$ L$2.$ Build the FA by using the cartesian product construction, i$.$e$.$ by

taking as the set of state Q $=$ Q$1$ Q$2,$ where Q$1$ and Q$2$ are the sets of states

of the automata that accept L$1$ and L$2,$ respectively. Try to simplify the final

result by getting rid of the redundant states and corresponding transitions.