Problem $1.(4$ points$)$

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

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

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:

$L_1=\{a,b{\}}^{**}\{a\}.$

$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.