$($Due January $24)$ In class, we designed automata for recognizing integers and real numbers.

$1\mathrm{.}1.$ Use the same ideas to describe an automaton for the following task. Most Russian female last names end in a letter $"a".$ Describe an automaton for recognizing words that end in $"a".$ For example, "Ivanov" should be rejected, but "Ivanova" or "IVANOVA" should be accepted.

A natural idea is to have $3$ states:

the start state S$,$

the state A indicating that the last read letter was $"$a$"$ or $"$A$",$ and

the state D indicating that the last read letter was different from $"a"$ and $"A".$

Start is the starting state, $A$ is the only final state. The transitions are as follows:

from $S,$ letters $"$a$"$ and $"$A$"$ lead to state $A,$ any other letter leads to state $D$;

from A$,$ letters $"a"$ and $"$A$"$ lead to state A$,$ any other letter leads to state D;

from D$,$ letters $"a"$ and $"$A$"$ lead to state A$,$ any other letter leads to state D$.$

$1\mathrm{.}2.$ Trace, step$-$by$-$step, how the finite automaton from Part $1\mathrm{.}1$ will check whether the following two words $($sequences of symbols$)$ are ends with the letter $"a"($small or capital$)$:

the word Iva $($which this automaton should accept$)$ and

the word Iv $($which this automaton should reject$).$

$1\mathrm{.}3.$ Write down the tuple corresponding to the automaton from Part $1\mathrm{.}1$:

Q is the set of all the states,

$$ is the alphabet, i$.$e$.,$ the set of all the symbols that this automaton can encounter; for simplicity, consider only three letters: $a,r,$ and $A$;

$$:$QQ$ is the function that describes, for each state $q$ and for each symbol $s,$ the state $(q,s)$ to which the automaton that was originally in the state q moves when it sees the symbol s $($you do not need to describe all possible transitions this way, just describe two of them$)$;

$q_0$ is the starting state, and

$F$ is the set of all final states.

$1\mathrm{.}4.$ For each automaton $A,$ let $L_A$ denote the language of all the words accepted by this automaton, i$.$e$.,$ of all the words for which this automaton ends up in a final state. In class, we learned a general algorithm that:

given two automata A and $B$ that correspond to languages $L_A$ and $L_B,$

constructs two new automata for recognizing, correspondingly, the union and intersection o languages $L_A$ and $L_B.$

Apply this algorithm to the following two automata:

the automaton from Part $1\mathrm{.}1$ as Automaton $A,$ and

an automaton for words not containing letter $"r"($since some people have difficulty pronouncing this sound$)$ as Automaton $B.$

A natural idea is to have $3$ states for Automaton B: start $($s$),$ words with no $"r"$ letters $($n$),$ and words with $"r"$ letter $($r$).$ Start is the starting state, $n$ is the only final state. The transitions are a follows:

from s$,$ letter $"r"$ leads to $r,$ any other symbol leads to $n$;

from n$,$ letter $"r"$ leads to $r,$ any other symbol leads to $n$;

from r$,$ every symbol leads back to r$.$

For simplicity, in your automaton for recognizing the union and intersection of the two languages, feel free to assume that you only have symbols a$,$ r$,$ and A$.$