$($iii$)$ Using the diagram below identify the regular expression for the automata.

$[4$ marks$]$

Question No$.3$

$($i$)$ Given two languages A and $B,$ what is the formal definition of the expression $"A$

turing reduces to $B^{?}($written $A{?}_{t}B).$

$[2$ marks$]$

$($ii$)$ Explain the difference between a Turing$-$recognisable language and a decidable

language.

$[2$ marks$]$

$($iii$)$ Prove that the following is context free by constructing a Pushdown automata

$L=\{a^m{b}^n|mn2m\}$

$[2$ marks$]$

$($iv$)$ Using a pumping lemma show that

$L=\{a^m{b}^{2m}{a}^m|m>0\}is$ not context free