Task $1$:

$[45$ Marks$]$

a$.$ Turing Machines $($TM$)$ can recognize many languages by exhaustively searching over all

possible options until a solution is found. There are many applications of TM one among them

is the manipulate of string handling.

On the above context, draw a Turing machine diagram that transforms a string containing only

p$\text{'}$s$,$ q$\text{'}$s$,$ and r$\text{'}$s of length $4$ and replace each letter preceding $"$p to q$"[20$ Marks$].$ Elaborately

explaining the algorithm and states of the Turing machine $[05$ Marks$].$

Automata Languages and Computation $($COMP $20042)-$Spring $2024-$ CW$2($Assignment$)-$ All $-$ QP

$[$Example: consider a string qrrq would remain unchanged because there is no p$\text{'}$s available and,

in the string, while rprrpp would change to qprqqp$.]$

$[$Note: Please follow the naming conventions explained during the module delivery. Eg if the

student name is BADER ABDULLAH NASSER AL HARRASI, then replace $p=B,q=A,r=N]$

$[25$ Marks$]$

b$.$ Give an algorithm for the Turing machines that decide the following languages over the

alphabet $\{p,q,r\}.$

contains more than $5$ times as many q$\text{'}$s as p$\text{'}$s

i want you to solve it as automata language $,,$this the fourth time i asked to solve