Foundations of Computer Science II Project 2

Confidential
CS 341: Foundations of Computer Science II

Project 2

Be sure to read this entire document before starting the assignment.
Academic Integrity
Any student caught cheating on any assignment will be reported to the dean of students.
Cheating includes, but is not limited to, getting solutions (including code) from or giving
solutions to someone else. You may discuss the assignment with others, but ultimately
you must do and turn in your own work.
1 Overview
We define the language A to be a particular set of strings (defined below) that represent
valid arithmetic expressions operating on integers and/or variable names having length ≥
1, with the entire expression contained between two dollar signs. For this assignment you
are to draw a PDA that recognizes this language and write a program that implements
your PDA.
2 The Language A
To precisely define the language A, we first define the context-free grammar G =
(V, Σ, R, S), where V = {S, T, X, C, N, I},
Σ = { a, b, c, . . . , z, A, B, C, . . . , Z, 0, 1, 2, . . . , 9, +, -, ∗, /, (, ), $, }, (1)
which includes both the minus sign (-) and the underscore ( ), the starting variable is
S, and the rules are
S → $T$
T → T+T | T-T | T*T | T/T | (T) | CX | I
X → XX | C | N | | ε
C → a | b | c | · · · | z | A | B | C | · · · | Z |
N → 0 | 1 | 2 | · · · | 9
I → NI | N
1
Confidential
The rule T → T-T has a minus sign on the right side, and the rules X → and
C → have an underscore on the right side. Then we define the language A =
L(G), which contains strings that begin and end with $, and between the $’s is an
arithmetic expression over integers and/or variables, where the variable names have
length ≥ 1 and must start with a Roman letter or underscore. For example, the string
“$(a1-(28*H 3b))$” belongs to A, which we can show by using the derivation
S ⇒ $T$ ⇒ $(T)$ ⇒ $(T-T)$ ⇒ $(T-(T))$ ⇒ $(T-(T*T))$
⇒ $(CX-(T*T))$ ⇒ $(CN-(T*T))$ ⇒ $(aN-(T*T))$
⇒ $(a1-(T*T))$ ⇒ $(a1-(I*T))$ ⇒ $(a1-(NI*T))$
⇒ $(a1-(NN*T))$ ⇒ $(a1-(2N*T))$ ⇒ $(a1-(28*T))$
⇒ $(a1-(28*CX))$ ⇒ $(a1-(28*CXX))$ ⇒ $(a1-(28*CXXX))$
⇒ $(a1-(28*HXXX))$ ⇒ $(a1-(28*H XX))$ ⇒ $(a1-(28*H 3X))$
⇒ $(a1-(28*H 3b))$
The grammar G does not include the rule T → -T nor the rule T → ε, so the strings
“$-gq$” and “$st+-mr$” do not belong to A. Also, note that the grammar G is ambiguous; e.g., the string $ap+bn*cm$ ∈ A has two different parse trees.
3 PDA for A
First you are to construct a PDA M = (Q, Σ, Γ, δ, q1, F) that recognizes A, where Σ
is defined in equation (1). The PDA M must satisfy the following conditions:
ˆ The PDA must be defined with the alphabet Σ defined in equation (1). In other
words the PDA must be able to handle any string of symbols from Σ. The PDA
can handle certain strings not in A by crashing, i.e., the drawing does not have an
edge leaving a state corresponding to particular symbols read and popped.
ˆ The PDA must have exactly one accept state.
ˆ The states in the PDA must be labeled q1, q2, q3, . . . , qn, where q1 is the start
state and n is the number of states in the PDA. (It is also acceptable for the states
to be labeled q0, q1, . . . , qn−1, with q0 the start state.)
ˆ All edges in the PDA must correspond to reading a symbol from Σ; i.e., no edge
can correspond to reading ε. There is no restriction on pushing or popping ε on
transitions.
ˆ There is exactly one edge leaving the start state, and that arc has label “$, ε → $”.
Thus, the first thing the PDA does is it reads a $ and pushes a $ on the stack.
ˆ Any edge going into the accept state has label “$, $ → ε”.
ˆ There cannot be two edges corresponding to reading the same symbol a ∈ Σ and
popping the same symbol b ∈ Γ leaving a single state.
2
Confidential
You will not be able to use the algorithm in Lemma 2.21 to convert the CFG
G into a PDA for A since the resulting PDA will not satisfy the last four
properties above. However, those properties ensure that the PDA M is essentially
deterministic, so once you figure out M, it will be easy to implement as a program.
(Implementing a nondeterministic machine is more difficult since the program needs to
check every branch in the tree of computation.)
The drawing of your PDA must include all edges that are ever used in accepting a
string in A. But to simplify your drawing, those edges that will always lead to a string
being rejected should be omitted. Specifically, when processing a string on your PDA, it
might become clear at some point that the string will be rejected before reaching the end
of the input. For example, if the input string is “$ab+*bc$”, then it is clear on reading
the * that the string will not be accepted. Moreover, if an input string ever contains the
substring +*, then the input string will be rejected. Thus, your drawing should omit the
transition corresponding to reading the * in this case, so the PDA drawing will crash at
this point. When these edges are omitted, you should be able to draw your PDA as a
planar graph (i.e., no crossing edges).
4 Program Specifications
You must write your program in C, C++, Java, or Python. All input/output must be
through standard input/output, and your program is to work as follows:
1. Your program asks the user if s/he wants to enter a string. The user then enters
“y” for “yes”, or “n” for “no”.
ˆ If the user enters “n”, then the program terminates.
ˆ If the user enters “y”, then the user is prompted to enter a string over Σ.
2. If the user chooses to input a string, your program then reads in the string. You
may assume that the user will only enter a string over Σ. After reading in the
string, your program prints it. Then your program processes the string on your
PDA in the following manner.
ˆ Your program must begin in the start state of the PDA and print out the
name of that state (q1 or q0).
ˆ After each transition of the PDA, your program must print out the symbol
that was read, the symbol that was popped from the stack, the symbol that
was pushed onto the stack, and the name of the current state of the PDA.
ˆ If the PDA crashes before reaching the end of the input string, your program
should output this fact.
3. After completing the processing of the string on the PDA (possibly by crashing),
your program must indicate if the string is accepted or rejected based on how the
string was processed on the PDA. Your program then must return to step 1.
3
Confidential
5 Test Cases
Test your program on each of the following input strings:
1. $ a 3B$
2. $ ba76+R*3-fF 45n/812$
3. $ba+ c4*7m-f8/h98u$
4. $y33(x23g)$
5. $(((r1+9-fs)*212))*(a2)$
6. $(t0+wk)*bn)/c1$
7. $(((ui+ej*(vk+ci))/pt)$
8. $+g5$
9. $52*(872/(P+kd34E/e3)-FW)+6/(((rw* y4 b d-r57ee*t)/y6+ugf))$
10. $g0*(hs+(df-*ft))$
11. $(tg+(hy-j7))/uk)*ri+(eo/wp$
12. $(tg+(hy-j9))/uk)ri$
13. $wm-(tn*bu)+$
14. $wm-tn(*bu)$
15. $wm-)tn*bu($
You must create an output file containing your program’s output from each test case
in the order above.
6 Deliverables
The due date/time for the assignment is 3/21/2017, 1:00pm NJ local time. You must
submit all of the following through moodle by the due date/time:
1. A Microsoft Word document stating, “I certify that I have not violated the University Policy on Academic Integrity”, followed by your first and last name and
NJIT student ID. If you do not include this pledge, then you will receive a 0 on the
assignment. Anyone caught violating the University Policy on Academic Integrity
will be immediately reported to the dean of students.
2. A drawing of the PDA for A that your program implements. This format of the
file must be either Microsoft Word, pdf, or jpeg (e.g., a photo from your phone’s
camera, but make sure it’s not blurry). The file must be smaller than 5MB in size.
4
Confidential
3. A single file of your source code, of type .c, .cpp, .java, or .py. Only submit
the source code; do not include any class files. You must name your file
p2 17s ucid.ext
where ucid is replaced by your NJIT UCID (which is typically your initials followed
by some digits) and .ext is the appropriate file extension for the programming
language you used, e.g., .java. The first few lines of your source code must be
comments that include your full name and UCID.
4. A single file containing the output from running your program on all of the test
cases, in the order given in Section 5 of this document. The output file must be
either .txt or in Microsoft Word.
The files must not be compressed. You will not receive any credit if you do not
complete all of the above. Late projects will be penalized as follows:
Lateness (Hours) Penalty
0.0 < Lateness ≤ 24 10
24 < Lateness ≤ 48 30
48 < Lateness ≤ 72 60
72 < Lateness 100
where “Hours” includes any partial hours, e.g., 0.0000001 hours late incurs a 10-point
lateness penalty. A project is considered to be late if all of the above are not completed
by the due date/time, and the lateness penalty will continue to accumulate until all of
the above have been completed. Any submissions completed more than 72 hours after
the due date/time will receive no credit.
7 Grading Criteria
The criteria for grading are as follows:
ˆ the correctness of the drawing of your PDA for A (30 points; you will lose points
if your PDA has significantly more states than necessary)
ˆ your program works according to the specifications given in Section 4, matches
your PDA for A, and follows the directions in Section 6 (15 points)
ˆ your program is properly documented with comments (10 points)
ˆ your output is correct for the test cases (45 points).
Your grade will mainly be determined by examining the source code, the drawing of
the PDA, and the output that you turn in; the source code will only be tested if there
are questions about your code.
To receive any credit for this assignment, you must turn in a drawing of the PDA your
program implements and a minimally working program. For a program to be minimally
working, it must
5
Confidential
ˆ compile without syntax errors;
ˆ properly process all strings in A0, where A0 is the set of strings in A that do not
have parentheses; and
ˆ implement the drawing of your PDA for A.
If you do not hand in a minimally working program, then you will receive
a 0 for the assignment and your grade in the course will be lowered by one
step, e.g., from B to C+, or from C to D.
8 Hints
You should do this assignment in steps. Start by developing a PDA to recognize A0.
Once you have this figured out, then enhance your PDA to also accept the rest of the
strings in strings in A.
To develop a PDA for A0 (or A), start by partitioning Σ into subsets, where each
subset contains one type of symbol. For example, one subset contains the symbols that
are operators (+, -, *, /). Then draw a state for each subset, and also add a start state
and an accepting state. If the PDA is currently in a state corresponding to one subset,
then the last symbol read was a symbol from that subset. Then figure out what are the
valid choices for the next type of symbol, and draw a transition from the current state
to each of those states.
6