Let $E=a{a}^{**}+b$ be a regular expression over the alphabet $=\{a,b\}.$ Use the template

method to construct an $-$NFA that accepts the language of $E.$

Let $=\{0,1\}.$ Prove the equivalence: $(1+{100}^{**}{)}^{**}-=({10}^{**}{)}^{**}.$

Let $L(A)$ be the language accepted by the DFA in Question $(5).$ By Kleene's Theorem,

$L(A)$ is regular. It is known that the pumping constant for $L(A)$ is $n=3.$

$($a$)$ Show that $w=1101$inL$(A).$

$($b$)$ Find a decomposition $1101=xyz$ that satisfies the conditions of the Pumping

Lemma, namely, $|y|1,|xy|3$ and $x{y}^k$zinL$(A)$ for all $k0.$