CS5170/6070: Assignment 5 [Version 2]
1 Instructions
• The assignment comprises of one problem with five sub-parts totalling 20 points. If your answer to
any question is wrong or incomplete, you will be awarded partial score depending on your attempt.
• If you have any questions, post it on canvas.
• The assignment is due on Dec 01, 2020 by 5:00 PM via Canvas as a single PDF or DOC file.
I will not be accepting your work via email.
• Late Penalty: You will be assessed a penalty of 5% of your score for each day of delay in
your submission for a maximum of 2 additional days of delay. Thereafter, you’ll receive
a zero for the assignment. So any submission after 5:00 PM on Dec 03, 2020 will receive
an automatic zero score. If you are submitting after the Dec 01 deadline, email me and
cc the TA with the subject [CS5170_Fall2020_Assignment 5]
• Any suspicion of cheating will be resolved by asking the student to solve a similar prob-
lem. First-time cheaters will result in an automatic zero score for the entire assignment.
Repeat offenders will face harsher penalties!
• The work turned in by you will be considered independent work. The work you submit
for evaluation must be your own ideas, thoughts, arguments. Most importantly, it must
be described in your own words.
2 Questions
Q1 Suppose one were to devise a Novel non-deterministic PDA (NNPDA) device with two stacks, say
Stack A and Stack B. This machine is indexed by an 8-tuple (Q,Σ,ΓA,ΓB , δ, q0, ZA, ZB , F ), where ΓA
is the alphabet for Stack A, and ΓB is the stack alphabet for Stack B and ZA, ZB are the special stack
symbols for the two stacks. The transition function for an NNPDA is defined as follows:
δ : Q× (Σ ∪ {λ})× ΓA × ΓB → Q× Γ∗A × Γ∗B
In other words, at any instant this machine:
• chooses to read a symbol from the tape or chooses to undergo a λ-transition (if the two stacks
allow it);
• pops a symbol from Stack A and can push a string onto Stack A; and
• independently of Stack A, pops a symbol from Stack B, and can push a string onto Stack B.
Note that δ(q, x,A,B) = (q′, sA, sB) indicates that upon reading x ∈ Σ ∪ {λ} from the input tape, A
from Stack A, and B from Stack B in state q ∈ Q, the NNPDA will move to state q′ ∈ Q and replace
A by string sA ∈ Γ∗A and B by string sB ∈ Γ∗B . Assume that the acceptance is based on reaching a
final state upon reading the entire input string.
Now for this class of machines, answer the following:
1
• What is the class of languages C that is accepted by these machines? Provide first an intuition
and how each component (Stack A, Stack B, machine state, and tape are used) plays a role in
accepting languages in C. Note that C is one of five choices: regular, CF, deterministic CF, r.e.,
or recursive languages. [1+1 points]
• Formally argue that given a finite representation of a language L in the class C, how you’ll devise
an NNPDA that accepts L. For example, if you claim in the previous part that C is the class of
regular languages, I want you to start with a DFA or regular grammar or regex for any regular L
and devise an NNPDA for that very same language. If you claim in the previous part that C is
the class of deterministic CF languages, then argue that any deterministic PDA can be converted
to an NNPDA without affecting the language accepted.
Note that in this part you need to provide a procedure to convert the machine/grammar/regex
(as the case may be) into an NNPDA. So I want you to use the tuple version of the former and
define the 8 ingredients of the latter. [3 points]
• What if I posed the question to define NNPDAs to have ` > 2 stacks? Does your answer change?
If yes, why? If not, why not? [1 point]
Q2 Devise a TM that computes the remainder when one number is divided by another. Use any format of
your choice to represent the two input numbers and the output as strings. Indicate this choice clearly.
Provide the transition diagram and highlight the blocks of the TM in as much detail as you can. Plan
that your TM halts in a final state and the read head is pointing the leftmost bit of the output. [1+5
points]
Q3 Devise a TM to compute the function f(n) = dlog2 ne for n > 0. Use any format of your choice
to represent the input number and the output as strings. Indicate this choice clearly. Provide the
transition diagram and highlight the blocks of the TM in as much detail as you can. Plan that your
TM halts in a final state and the read head is pointing the leftmost bit of the output. [1+5 points]
Q4 Let f : N → N be a computable and strictly increasing function, i.e., f(1) < f(2) < f(3) < ..... Now
let me define another function g as follows:
g(i) =
{
j if there is j such thatf(j) = i
0 if there is no j such that f(j) = i
Explain in detail whether or not g is computable. If your answer is “yes,” then provide a high-level
description of how you’ll compute g. If not, reason why one cannot. [2 points]
2

欢迎咨询51作业君