CSC 363 — Assignment 1 Solution
Due Monday, February 4th, 5:00pm
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand may not receive full marks. Mark values for each question are contained in the [square brackets].
I will be in my office all Monday afternoon (on the 4th) or you can put the assignment in my mailbox in DH 3008.
1. Complete the pushdown automata M (in the figure below), such that L(M) = a∗b∗c∗ − {anbncn | n ≥ 1},
where Σ = {a, b, c}.
For example, once complete, your PDA should accept the strings: ε, aab, abbc, and aaabbbcccc, but reject the strings: abc, abbac, aabbcc. Hint: based on the structure of the incomplete PDA, you should deduce that the machine will accept the string if one of three conditions is met. [10]
1
SOL:
Note, the above machine doesn’t accept ε. To address this, we could put a transition directly from the start state to an accept state, or make the start state and accept state. Either of those options, or just having the machine above will receive full grades.
2. Although we didn’t see it in class, one can draw a Turing Machine using circles and arrows similar to a DFA, NFA, PDA, etc. However, in these picture the arrows are captioned by something like x, y, D. Meaning, the transition can only be taken if the read-write head is currently reading an x from the tape, and moreover, if this transition is taken, overwrite the x with a y and move the read-write head one cell over in direction D, where D equals L or R.
Construct and draw a Turing machine M such that, L(M) is the set of all binary strings where the numerical value of that binary string is a multiple of five. Your TM should have no more than five states, not including qaccept and qreject. For example, your TM should accept the strings 101, 1010, 1111, 00, and ε, but reject strings like 111, 1, 100.
Hint: using a TM for this language is actually overkill, it can be done with a DFA. Perhaps first try to do it on a DFA, then construct a TM which mimics that DFA’s behaviour. [5]
SOL:
2
Note, I used b for the blank symbol.
3. Turing machines can also be used to output more than just Accept/Reject. When they halt, they may also have useful output written on the tape. For example, a Turning machine may add numbers by taking in strings such as: 101#111 and having the string 1100 written on the tape when is halts. Note, 1100 equals 101 + 111. One way, to do this is to iteratively go through the two input binary numbers, calculate the output bit for each digit, and write it on the tape one by one, where the digit could be a 0 (0 + 0), 1 (1 + 0, or 0 + 1), or a carry bit c (1 + 1). Don’t worry about all the details here. During the execution of the machine, the tape may look like this:
101#111# c1c
You are responsible for addressing the carry bits in the output. Assuming the read-write head is directly at the end of the string (the second c in this case), write the portion of the Turing machine which reads the string after the second # ( c1c here) and determines its binary string equivalent. Continuing with the example, after your portion of the Turing machine runs, the tape would now look like:
101#111#1100 Some more before → after examples are given below
111#11# 1cc 001#100# 101 000#100# 100
→ 111#11#1010 → 001#100# 101 → 000#100# 100
3
Give your portion of the Turing machine as a table of transitions (similar to that seen in lecture). Furthermore, give a one/two sentence description of each of your states. Assume when you begin your portion of the machine the Turing machine is in state qbegin and when you end your portion of the machine the Turing machine is in state qend. When your portion completes its work, the read-write head should be directly over the second #. [10]
SOL:
qbegin : Reading in a bit, where there is no carry bit from the previous digit. qbegin : Reading in a bit, where there is a carry bit from the previous digit.
4
0
1
c
qbegin
(qbegin, 0, L)
(qbegin, 1, L)
(qcarry , 0, L)
qend,, L
qcarry
(qbegin, 1, L)
(qcarry , 0, L)
(qcarry , 1, L)
(qend, 1, L)