QUESTION 2

Given a language,L₁ = {x^my^mxⁿzⁿ| m, n 0}.

1. Choose the suitable machine and language type of L₁.
   1. A DFA - regular expression
   2. A PDA - context free grammar
   3. A Turing machine - not context free
2. Design the DFA/ PDA/ TM of L₁as answered in (a).
3. Discuss how the machine match any dependent parts of the string in the languageL₁.

QUESTION 3

Construct a Turing Machine copy(x) = x-x, where x {a, b}*and - is a special character. Basically, the machine will start with the tape having the form BxB and terminate with the tape Bx-xB where B is the blank symbol. For example, if the input is abba, so the output will be abba-abba.

1. Give a high-level descriptionof the TMcopy(w).
2. Draw the state diagramof the TMcopy(w)

6.Given a TM transition table with strings of 0s and 1s. The tape head will stop anywhere within the string when finishing its execution.

	Symbols
State	0	1	B
q1	(q2, B, R)	(q3, B, R)	(q4, B, R)
q2	(q2, 0, R)	(q3, 0, R)	(q4, 0, R)
q3	(q2, 1, R)	(q2, 1, R)	(q3, 1, R)
q4*	-	-	-

1. Based on the table above, draw the transition diagram of the TM.
2. Based on the transition table given, explain what this Turing Machine does?
3. Modify the above TM so that the head will be back to the starting position after the execution is finished.

QUESTION 7

1. Finite automata (FA) can only accept regular language. Context free language requires push down automata (PDA) to be recognized. Give one example of context free language, explain why Push down Automata (PDA) can recognize this language and show how it works. (Hint: no need to formally define or draw the state diagram. Just describe the implementation).
2. The language L = {aⁿbⁿcⁿ | n 0} is not recognizable by a PDA. Explain why this language cannot be recognized by a PDA.
3. Give another language that is not recognizable by PDA.

QUESTION 8

Given the language, () = {0^j1^k0ⁿ| = ( + ); , > 0}answer the following questions:

1. Describe in words what the above language does.
2. Design the Turing Machine that accept the above language. (Tips: if the input string is 011000, change this input to XYYZZZ)
3. Trace the computation for the input string011000.

QUESTION 9

1. Discuss the differences between Pushdown Automata (PDA) and Turing Machine (TM) in terms of their transition function and acceptance criteria.

2. Give one example of language that can be accepted/represented by both PDA and TM machines. Choose one valid string of the language and show the computation of the string on both PDA and TM.