CSCE 428/828 Homework 6
• This homework is due by 11:59PM on November 10 (Wednesday).
• Please type and submit your homework as a single pdf file on Canvas.
• Recognizing that peer study is an effective learning method, you are encouraged to discuss
with others about the homework. But you must write your own solutions (i.e., no copy-and-
paste or slightly edit), and must clearly indicate with whom you discussed the homework.
• It is also ok for you to search the Internet for more information about the homework. But
you must write your own solutions (i.e., no copy-and-paste or slightly edit), and must clearly
reference the original webpage.
1. (40 points) Please design a standard Turing machine (i.e., single semi-infinite one-dimensional
tape, deterministic) to recognize the following language. Please draw the state transition di-
agram of your machine (35 points), and please briefly describe how your machine works (i.e.,
high-level idea using English, algorithm, or pseudocode) (5 points).
L = { x over {a, b} | x is a palindrome }
Special cases: L contains the empty string, a, and b.
2. (30 points) Please design a Turing machine with two tapes (i.e., two semi-infinite
one-dimensional tapes, deterministic, stay option) to recognize the following language.
Please draw the state transition diagram of your machine (25 points), and please briefly de-
scribe how your machine works (i.e., high-level idea using English, algorithm, or pseudocode)
(5 points). We assume that initially an input string is stored on the first tape and the second
tape is empty. You must use a different high-level idea than the first problem.
L = { x over {a, b} | x is a palindrome }
Special cases: L contains the empty string, a, and b.
You may use one of the following two transition notations.
• The transition notation used in the class and lecture notes : a → c, L, b → d,R which
means that if the current symbol on the first tape is a and the current symbol on the
second tape is b, then for the first tape we replace a with c and move the tape head to
the left, and for the second tape we replace b with d and move the tape head to the
right.
• A shorter transition notation: (a, b) → (c, d), (L,R) which means that if the current
symbol on the first tape is a and the current symbol on the second tape is b, then for
the first tape we replace a with c and move the tape head to the left, and for the second
tape we replace b with d and move the tape head to the right.
Page 1 of 4
3. (30 points) We can prove that for any pushdown automaton (PDA), there is an equivalent
Turing machine with two tapes that recognizes the same language as the PDA. Basically,
the equivalent TM simulates every transition of the PDA. It uses the first tape to store an
input string (read but does not write to the first tape). It uses the second tape to simulate the
PDA stack with the leftmost of the tape as the bottom of the stack and the current symbol
of the tape as the current top stack symbol of the stack.
• To simplify the proof, we assume that the PDA is deterministic. That is, it has only one
copy at any time when reading an input string.
• To simplify the proof, we assume that the input alphabet of the PDA is {a}, and the
stack alphabet of the PDA is {A, $}, and then assume that the tape alphabet for both
tapes of the TM is {a, A, $, ⊔}.
Example 1: let’s consider the following PDA transition.
PDA: p q
a,A → A
The equivalent TM can use the following one transition to simulate above PDA transition.
TM: p q
a → a,R, A → A,S
To help you better understand how the above TM transition works, let’s consider an example
where currently we have following tape symbols and tape head positions and the current state
is p.
tape 1
tape 2
aaa a
$ A
After taking the TM transition, we have
tape 1
tape 2
aaa a
$ A
Page 2 of 4
Example 2: let’s consider the following PDA transition.
PDA: p q
a, ε → $
The equivalent TM can use the following four transitions to simulate above PDA transition.
TM: p r q
a → a, S, A → A,R
a → a, S, $ → $, R
a → a, S, ⊔ → ⊔, R a → a,R, ⊔ → $, S
To help you better understand how the above TM transitions work, let’s consider an example
where currently we have following tape symbols and tape head positions and the current state
is p.
tape 1
tape 2
aaa a
After taking the transition “a → a, S, ⊔ → ⊔, R” from state p to r, we have
tape 1
tape 2
aaa a
After taking the transition “a → a,R, ⊔ → $, S” from state r to q, we have
tape 1
tape 2
aaa a
$
Page 3 of 4
Please show the transitions of the TM to simulate each of the following PDA transitions.
• (10 points) PDA transition “a, A → ε” from state p to q
• (10 points) PDA transition “a, ε→ A” from state p to q
• (10 points) PDA transition “a, ε→ ε” from state p to q
Page 4 of 4





























































































学霸联盟