$1\mathrm{.}9$Use the construction in the proof of The class of regular languages is closed under the concatenation operation. PROOF IDEA We have regular languagesA$1$andA$2$and want to prove thatA$1$A$2$is regular. The idea is to take twoNFAs,N$1$andN$2$forA$1$andA$2,$ andcombine them into a newNFANas we did for the case of union, but this timein a different way, as shown in Figure $1\mathrm{.}48.$AssignN$$s start state to be the start state ofN$1.$ The accept states ofN$1$haveadditional$\backslash$epsi arrows that nondeterministically allow branching toN$2$wheneverN$1$is in an accept state, signifying that it has found an initial piece of the inputthat constitutes a string inA$1.$ The accept states ofNare the accept states ofN$2$only. Therefore, it accepts when the input can be split into two parts, the firstaccepted byN$1$and the second byN$2.$ We can think ofNas nondeterministicallyguessing where to make the split. to give the state diagrams ofNFAs recognizing the concatenation of the languages described in

$1.$ g$.\{$w$|$the length ofwis at most$5\}$ and i$.\{$w$|$every odd position ofwis a$1\}$

$2.$ b$.\{$w$|$wcontains at least three$1$s$\}$ and m$.$The empty set

$1\mathrm{.}10$ Use the construction in the proof of The class of regular languages is closed under the star operation.PROOF IDEAWe have a regular languageA$1$and want to prove thatA$1$alsois regular. We take anNFAN$1$forA$1$and modify it to recognizeA$1,$ as shown inthe following figure. The resultingNFANwill accept its input whenever it canbe broken into several pieces andN$1$accepts each piece.We can constructNlikeN$1$with additional$\backslash$epsi arrows returning to the startstate from the accept states. This way, when processing gets to the end of a piecethatN$1$accepts, the machineNhas the option of jumping back to the start stateto try to read another piece thatN$1$accepts. In addition, we must modifyNso that it accepts$\backslash$epsi $,$ which always is a member ofA$1.$ One $($slightly bad$)$ idea issimply to add the start state to the set of accept states. This approach certainlyadds$\backslash$epsi to the recognized language, but it may also add other, undesired strings.Exercise $1\mathrm{.}15$ asks for an example of the failure of this idea. The way to fix it isto add a new start state, which also is an accept state, and which has an$\backslash$epsi arrowto the old start state. This solution has the desired effect of adding$\backslash$epsi to thelanguage without adding anything else. to give the state diagrams ofNFAs recognizing the star of the languages described in

$1.$ b$.\{$w$|$wcontains at least three$1$s$\}$

$2.$ j$.\{$w$|$wcontains at least two$0$s and at most one$1\}$

$3.$ m$.$ The empty set 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\_9$a $=$ NFA$($

# NFA for language g: $\{$w $|$ the length of w is at most $5\}$

# $)$

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

# NFA for language b: $\{$w $|$ w contains at least three $1$s$\}$

# $)$

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

# Create an NFA to recognize the language b

# $)$

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

# Create an NFA to recognize the language j

# $)$

# prob$\_1\_10$c $=$ NFA$($

# Create an NFA to recognize the empty set $($language m$)$

# $)$

#you must use this outline