QUESTIONS

Build a Turing Machine that multiplies two integers. Explain the logic behind your design shortly. An example initial and final configuration is given below.

Initial configuration:aaaaa $bbdots$

Final configuration: AAAAA$bbcccccccccdots$

The example above indicates that $5$ is multiplied by $2$ and the result which consists of $10$ c$\text{'}$s resides on the tape after the input. You can change the letters during the process as in the above example a$\text{'}$s are turned to A$\text{'}$s to mark them during the process of the Turing machine.

Consider the following languages over the alphabet $=\{a,b,c\}.$ If they are regular find a regular expression that defines the language. Otherwise, prove that thay are non$-$regular using pumping lemma.

i$)Ll=\{a^{2n}{b}^{m}c|n,m0\}$

ii$)L2=\{a^{2n}bc{c}^n|n0\}$

Explain halting problem briefly.