We are using the package automata$-$lib for DFAs in python. Install it using pip: pip$3$ install automata$-$lib

The basic format is your$\_$nfa $=$ NFA$(...)$ and fill in parameters like in the last assignment.

Use $\text{'}\text{'}$ for the empty string $($lambda$),$ and if a state has two transitions with the same value leading to different states then enter a list of states where you would normally enter the destination.

$$ Here is an example to illustrate both of these: $\text{'}$q$0\text{'}$: $\{\text{'}\text{'}$: $\{\text{'}$q$1\text{'},\text{'}$q$2\text{'}\}\}$

You must use the provided names for the FSMs$.$

$1\mathrm{.}8$Use the construction in the proof of The class of regular languages is closed under the union operation.PROOF IDEA: We have regular languagesA$1$andA$2$and want to prove thatA$1\backslash$cup A$2$is regular. The idea is to take two NFAs, N$1$andN$2$forA$1$andA$2,$ and combine them into one newNFA, N$.$Machine N must accept its input if eitherN$1$orN$2$accepts this input. The new machine has a new start state that branches to the start states of the old machines with $\backslash$epsi arrows. In this way, the new machine nondeterministically guesseswhich of the two machines accepts the input. If one of them accepts the input,Nwill accept it$,$ too.We represent this construction in the following figure. On the left, we in$-$dicate the start and accept states of machinesN$1$andN$2$with large circles andsome additional states with small circles. On the right, we show how to combineN$1$andN$2$intoNby adding additional transition arrows. to give the state diagrams ofNFAs recognizing the union of the languages described in

$1.$ a$.\{$w$|$wbegins with a$1$and ends with a$0\}$ and b$.\{$w$|$wcontains at least three$1$s$\}$

$2.$ c$.\{$w$|$wcontains the substring$0101\}$ Outline:

from automata.fa$.$nfa import NFA

example$\_$nfa $=$ NFA$($

states$=\{\text{'}$q$0\text{'},\text{'}$q$1\text{'},\text{'}$q$2\text{'}\},$

input$\_$symbols$=\{\text{'}0\text{'},\text{'}1\text{'}\},$

transitions$=\{$

$\text{'}$q$0\text{'}$: $\{\text{'}\text{'}$: $\{\text{'}$q$1\text{'},\text{'}$q$2\text{'}\}\},$

$\text{'}$q$1\text{'}$: $\{\text{'}0\text{'}$: $\{\text{'}$q$1\text{'}\},\text{'}1\text{'}$: $\{\text{'}$q$2\text{'}\}\},$

$\text{'}$q$2\text{'}$: $\{\text{'}0\text{'}$: $\{\text{'}$q$1\text{'}\},\text{'}1\text{'}$: $\{\text{'}$q$2\text{'}\}\}$

$\},$

initial$\_$state$=\text{'}$q$0\text{'},$

final$\_$states$=\{\text{'}$q$1\text{'}\}$

$)$

# prob$\_1\_8$a $=$ NFA$($

# NFA for language a $($w begins with a $1$ and ends with a $0)$

# $)$

# prob$\_1\_8$b $=$ NFA$($

# NFA for language c $($w contains the substring $0101)$

# $)$