Pushdown Automata$(10\%)$

Suppose that the previous Pushdown automata run on the input $x**(z+x**(y+z)).$ Trace the sequence of transitions that are applied in a computation that accept this input. In each step, write the input consumed, the stack and the derivation.

Turing Machine$(10\%$

Find a State Diagram for the Turing Machine that recognizes the language $L=$

$\{$:$\{a^{\text{'}}b\}=c^{\text{'}}|i**j=k\}$

Time Complexity$(10\%)$

Find the time complexity for the Turing Machine that recognizes the language

$L=\{a^{\text{'}}b=c^k|i**j=k\}$

$2$