1) Build a Turing Machine that multiplies two integers. Explain the logic behind your design shortly....

Transcribed Image Text:

1) 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:aaaaabbAAA.... Final configuration: AAAAAAbbAccccccccccAAA.. The example above indicates that 5 is multiplied by 2 and the result which consists of 10 c's resides on the tape after the input. You can change the letters during the process as in the above example a's are turned to A's to mark them during the process of the Turing machine. 2) Consider the following languages over the alphabet E={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) L1={abmc | n,m 20} ii) L2={abc" | n 0} 3) Explain halting problem briefly. 1) 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:aaaaabbAAA.... Final configuration: AAAAAAbbAccccccccccAAA.. The example above indicates that 5 is multiplied by 2 and the result which consists of 10 c's resides on the tape after the input. You can change the letters during the process as in the above example a's are turned to A's to mark them during the process of the Turing machine. 2) Consider the following languages over the alphabet E={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) L1={abmc | n,m 20} ii) L2={abc" | n 0} 3) Explain halting problem briefly.

Answer rating: 100% (QA)

1 Turing Machine for Multiplication To design a Turing Machine that multiplies two integers you can follow a general approach using a loop and repetitive addition Heres a highlevel overview of the log... View the full answer