$($a$)$ Using the Master theorem write the time complexity of the following, making every step clear:

T$($n$)=3$ T$($n$/5)+$O$($n$)$

$($b$)$

i$.$

ii$.$

$[4$ marks$]$

Design a context$-$free grammar that accepts the language of all binary strings in which the number of $0$s is greater than the number of $1$s$.$ For example, $0001$ and $10100$ should be accepted while $1010$ and $1100$ should not.

$[4$ marks$]$

Modify your context$-$free grammar to accept the language of all binary strings in which the number of $0$s is greater than the number of $1$s AND all $0$s appear before $1$s$.$ For example, $0001$ and $001$ should be accepted while $10100$ and $11000$ should not.

$[4$ marks$]$

$($c$)$ Design a Turing Machine for the following language

L$=$ww $|$wE $($aUb$)\}$

we means reverse of w$.$ For example, if w$=$"abb" then w$=$"bba". So$,$ strings such as

"abba" and "bbaabb" should be accepted while strings such as "ababa" and "abab" should not.