Question $1[18]$

$($a$)$ Determine a regular expression for the language L over the alphabet $\{$a$,$ b$\}$ that ends

with a letter that is different from the letter that it starts with.

For example, ab$,$ ababab and aaaaabaaaabbbbbb are words in L but aaa, baabbaab,

aaaaabaaaaaa and abaa are not. $(2)$

$($b$)$ Design a deterministic finite automaton $($DFA$)$ that will recognise all of the words in

as defined above. $(4)$

$($c$)$ Use Theorem $21$ to develop a context$-$free grammar $($CFG$)$ for the language L$.(4)$

$($d$)$ Convert the following CFG to Chomsky Normal Form $($CNF$)$:

S $->$ bY aZ $|$ aXaY

X $->$ baY $|$ abZ

Y $->$ aX $|\backslash$Lambda

Z $->$ bX $|\backslash$Lambda