$5.[4$ marks$]$ Suppose that a DFA M $=($Q$,,$ $,$ q$0,$ F $)$ accepts an infinite number of strings. Prove there is some string $=$ w$1$w$2$ wn$,$ where $|$Q$|$ n $2|$Q$|,$ such that is accepted by M $.$

$6.[4$ marks$]$ Prove that the following language is not regular:

L $=\{$w$1$w$2$ wnbn $|$ n $0$ and each wi in $\{$a$,$ b$\}\}.$

For example, the strings bababbbb and abbbbb are both in L$.$

$7.[2$ marks$]$ Consider the regular language L corresponding to the regular expression $($ab$)+.$ Explain what is wrong with the following $$proof$$ that L is non$-$regular.

Assume that L is regular. Let p be the pumping length. Consider the string

s $=($ab$)$p in L$.$ It has length greater than p$.$ Consider s $=$ xyz where x $=$ a and

y $=$ b and z $=($ab$)$p$1.$ Then xyyz $=$ ab b $($ab$)$p$1.$ However, this string is not in

L$,$ contradicting the Pumping Lemma. Thus, L is not regular.

$8.[4$ marks$]$ Give CFGs that generate the following languages over $=\{$a$,$ b$\}$:

$($a$)\{$w $|$ w is non$-$empty and starts and ends with the same symbol$\}$

$($b$)\{$b $|$ and are strings with the same number of a$$s $\}$

$($c$)\{$w $|$ w has the same number of a$$s as b$$s but is not of the form bnan for n $0\}$

Hint: $($c$)$ does not include the empty string. Tweak the reasoning for generating

the same number of a$$s as b$$s$.$

$9.[2$ marks$]$ Before the upcoming elections, a CS professor lays awake wondering: When the ballots are enumerated, will candidate x always be tied or ahead of the other candidate y$?$ Call such a non$-$empty sequence of ballots a ballot sequence. For instance xxyyx is a ballot sequence, but xxyyyxx is not. Prove that the set of all ballot sequences is a context$-$free language by providing a corresponding CFG$.$