Problem $6$

Prove the language below is not context$-$free.

$L=\{0^n{1}^n{2}^n|n0\}$

Problem $7$

Consider a Turing Machine $($TM$)$ designed to operate on inputs from the alpha$-$

bet $\{0,1\}.$ This TM is tasked with duplicating the input string. An example

execution is provided below, where $w$ represents any string in $\{0,1{\}}^{**}$ :

#$w$#$$#$w$#$w$#

Compute the following:

$($a$)$ State transition diagram.

$($b$)$ State transition table.

$($c$)$ Demonstrate the steps for the following execution: #$010$# $$ #$010$#$010$#$.$

Note: You may introduce additional characters to the working alphabet

if deemed necessary for your solution.

Problem $8$

Design a Turing Machine $($TM$)$ that counts the number of $a\text{'}$s in a given input

string. It should do this by writing a string containing as many I$\text{'}$s as there

are $a^{\text{'}}\text{'}$s following the input string. The initial configuration of the machine is

#xax $....$xax...# where $x\text{'}$s represent symbols other than $a\text{'}$s$.$ Assuming there

are a total of $\frac{n}{b}ar(a^{\text{'}}s),$ the transformation can be represented as:

$\frac{?}{?}$#xax....xax... $\frac{?}{?}$# $\frac{?}{?}$#xax....xax... $\frac{?}{?}$# IIIIIIII $\frac{?}{?}$#

Note: You may assume that AAx:$x$

Problem $9$

Design a Turing machine that calculates the modulo $3$ equivalent of a given

number represented using $\frac{}{s},$ where the count of I $\text{'}$s indicates the number itself.

Initially, the tape head will be positioned on the blank symbol # before the

number. At the completion of execution, the machine will append $\text{'}$s to the

number to represent the result.

The following example demonstrates the initial and final configurations for $5-=2$

$(mod3).$

#