Theory of Computing TA Times and Homework Insights

Theory of Computing TA times #3 Hsu, Hung-Wei 2014/05/21

Leftmost derivation e.g., What is the leftmost derivation of ? + ? + ? ?

Machines recognize the same class of languages? Machines of type A recognize a language iff machines of type B recognize the language. To proof that two kinds of machines have the same power, you have to show that: 1. Machines of type A can do all the jobs that those of B can do, which provides that type A might be more powerful than B. 2. On the other hand, machines of type B also can do all the jobs that those of A can do, providing that type A isn t more powerful than type B they actually have same power.

CAUTION CAUTION Most solutions we showed in TA s slides are more like the ideas rather then completed solutions. You may take them as guides, but shouldn t consider them as everything you need to complete an exercise.

Stats. Homework #5 Average 71.0 Std. Dev. 15.6 Homework #6 Average 71.8 Std. Dev. 17.3 Homework #7 Average 70.1 Std. Dev. 15.3

HW#5 Q2 (1/2) Let s eliminate ?. ? ??? ??? ??? ? ??? ? ? ? ? | ? And change the variables names. ? ? ?? ? ? ? ?? ? ? ?? ? ???????? ? ?? ???????? ? ?? ? ?? ? ?? ? ?? ? ?? ? ?? ? | ?

HW#5 Q2 (2/2) Then we can recognize that: 1. This grammar will generate a same amount of characters on both the left and the right sides. 2. Within these characters, the rule ???????? guarantees that there must be at least one pair of characters on the symmetrical position that are different. 3. Thus indicate that any string generated by the grammar can never be a palindrome.

HW#5 Q4 We modified the answer for generating the palindromes to be our answer: ? ? ?#? ?#? | ?#?#? ? ?? ?? #? | ? ? ??? ??? ? ? ? | # | #?# ? stands for the Target , and ? stands for the Universal cases .

HW#5 Q7 (1/3) Add ?0, a new start variable. ?? ? ? ??? ? ? ? 00 | ? Remove ? rules. Firstly, ? ?, ?0 ? ? ??? ?? ?? ? ? | ? ? 00 | ? Then, ? ?, ?0 ? | ? ? ??? ?? ?? | ?? ? ? | ? ? 00

HW#5 Q7 (2/3) Remove unit rules. Firstly, ? ?, ?0 ? | ? ? ??? ?? ?? ?? ? | ? ? 00 Then, ? ?, ?0 ? | ? ? ??? ?? ?? ?? ?? ? 00 Then, ?0 ?, ?0 ??? ?? ?? ?? ?? | ? ? ??? ?? ?? ?? 00 ? 00

HW#5 Q7 (3/3) Variables replacement. ?0 ??? ?? ?? ?? ????| ? ? ??? ?? ?? ?? ???? ? ???? ?? ?? ?? ??

HW#6 Q4 (1/3) Suppose ??is a PDA recognizing ? and ??a DFA recognizing ?. To show that ?/? is context free, we construct a PDA ??/?that recognizes ?/?. According to the description of the question, if an input belongs to ?/?, then it s a string that if being added a proper ? string behind, it would becomes an ? string. The non-input-part ? should be accepted by ??and a half-way- configured ??corresponding to different inputs. The strategy used to construct ??/?is that we run ??on the input first, and then we managed ??/? to run an specialized intersection of ??and the half-way-configured ?? s to check if the previous input is good.

HW#6 Q4 (2/3) Luckily, ??is a DFA, so we don t have to worry about the stack at the time we construct the specialized intersection. We use ?-transitions to handle all the possibilities while dealing with the non-input-part . Here s the definition of ??/?= (??/?, ,??,??/?,?0?,??/?) with ??= (??, ,??,??,?0?,??), ??= (??, ,??,?0?,??). ??/?= ?? ?? ?? ??/?= ?? ??

HW#6 Q4 (3/3) The simulation of ?? on the actual input: (It goes into stage two through the ?-transitions when the input were finished.) ??/???,?,? = ????,?,? ??,?0?,? , if ? = ?, ????,?,? , otherwise, for ?? ??; ?,? ?. The simulation of ??and ?? on the imaginary input: ??/?(??,??),?,? = ,?? ,? | ?? ,? ????,? ,? for some ? ,?? = ????,? , if ? = ?, ?? , otherwise, for (??,??) ?? ??; ?,? ?.

HW#6 Q5 The new unambiguous grammar. STMT ASSIGN STMT2 ASSIGN | IF THEN ELSE IF THEN if condition then STMT IF THEN ELSE if condition then STMT2 else STMT ASSIGN a 1 Note that the condition you want to avoid is that there re more than one possible derivation of the structure if-then if-then else . IF THEN IF THEN ELSE

HW#7 Q2 Firstly, the instructions haven t told about in which order a TM can try through all the possible settings. Secondly, since the possible settings are infinitely many, a TM would never finish them; you can t have an instruction for TM that requires it tries all the possibilities first, i.e., otherwise, reject. in this case. But don t be confused. A problem with a infinite possibilities can be a Turing-recognizable problem if the possibilities could be well ordered.

HW#7 Q3 1. Scan the tape to find an unmarked 1 . If we found one, mark the first 1 we found and move the head back to the front of the tape; otherwise, go to step 5. 2. Repeat step 1 again. But this time, the machine rejects the input if no unmarked 1 were found. 3. Scan the tape to find an unmarked 0 . If we found one, mark the 0 and move the head back to the front of the tape; otherwise, the machine rejects. 4. Go to step 1. 5. Scan the tape once from the beginning to the end. If there is no any unmarked 0 remains, the machine accepts; otherwise, rejects.

HW#7 Q6 (1/4) IDEA As the Turing machine with stay put instead of left has a similar operating logic with finite automata, we will show that this type of machines recognize the same class of languages as DFAs. Let s do the easier side first we show that all the things a DFA can do can also be done with a Turing machine with stay put instead of left. Just like the way we simulate a DFA with a normal Turing machine, we can simulate a DFA with the specialized Turing machine here since the simulation of a DFA doesn t need the head left operation. Then we do the other side we show that anything that can be done with a Turing machine with stay put instead of left can also be done with a DFA.

HW#7 Q6 (2/4) We can always build a DFA ? that does the same job as a Turing machine with stay put instead of left ? as below. Before we construct ? , we shall modify ? in two little places: We modify ? to use another new symbol instead of writing down a blank, and treat the new symbol just as a blank. Also, make the head moves right every time when ? reaches an accept state. Note that these changes won t affect the language it recognizes.

HW#7 Q6 (3/4) ,? ; Then, let ? = (?, ,?,?,?0,???????,???????), ? = ? , ,? ,?0 we build ? as such: ? = ?,?0 ? ?,? , for every ? ?,? , check the state ? for the transition that reads a character ?, see if it will lead to a transition that has the head right movement. If so, ? ?,? = ? , where ? is the state reached by the head right transition. Otherwise, ? ?,? = ???????. This handles the cases that make ? loop forever after reading ?. = ?0, = [new symbol for blank]

HW#7 Q6 (4/4) ? ???????,? ? ???????,? ? = ??????? {?}, for ? ?, where ? doesn t belong to ??????? ??????? but reads a real blank and causes ? to eventually enter an accept state. Note that, as we made ? in all the previous definitions, we ve skipped all the transitions in ? that after reading a real blank, would cause ? to loop forever, or lead ? to a reject state. = ???????, for ? . = ???????, for ? .

HW#7 Q7 a) You need to show that there s something 2-PDAs can do that 1- PDAs can t. E.g., recognizing ??????? }. Justify your claim. b) . To show that 3-PDAs (k-PDAs, actually) are not more powerful than 2- PDAs, you can first show that 2-PDAs have same power as TM. (Hint. With two stacks placed head-to-head, you can simulate all the tape operations in TM.) Then show that for any 3-PDA, we can find a multi-tape TM to simulate it. By thus, you ve showed that 2-PDAs are equivalent to 3-PDAs in power.