Assignment $3$:

$1\mathrm{.}8$ Give regular expressions generating the languages of

a$.\{$w$|$wbegins with a$1$and ends with a$0\}$

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

c$.\{$w$|$wcontains the substring$0101($i$.$e$.,$ w$=$x$0101$yfor some x and y$)\}$

g$.\{$w$|$the length of wis at most $5\}$

i$.\{$w $|$ every odd position of w is a$1\}$

l$.\{$w $|$ w contains an even number of $0$s$,$ or contains exactly two$1$s$\}$

$1\mathrm{.}19$ Use the procedure described in Lemma $1\mathrm{.}55$: If a language is described by a regular expression, then it is regular. PROOF IDEA: Say that we have a regular expression R describing some language A$.$ We show how to convert R into an NFA recognizing A$.$ By Corollary $1\mathrm{.}40,$ if an NFA recognizes Athen A is regular. to convert the following regular expressions to nondeterministic finite automata.

a$.(0\backslash$cup $1)000(0\backslash$cup $1)$

b$.(((00)(11))\backslash$cup $01)$

c$.$

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{'}\}$

$)$

example$\_$nfa$\_$regex $="(1*0)?(11*0|0)*"$

prob$\_1\_18$a $=""$

prob$\_1\_18$b $=""$

prob$\_1\_18$c $=""$

prob$\_1\_18$g $=""$

prob$\_1\_18$i $=""$

prob$\_1\_18$l $=""$

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

#

# $)$

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

#

# $)$

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

#

# $)$