COMP4141 Assignment 2 2022 Term 1
Due: Monday, 21st March, 12:00 (AEDST)
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose
should be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted at a high level, but the work submitted
must be your own in line with the University’s plagiarism policy.
For the problems below, let bin : {0, 1} → N be the function that treats a word of {0, 1} as the
binary representation of a non-negative integer, with the last symbol being the least-significant. So
bin(110) = bin(00110) = 6 and bin(e) = 0.
Formally, we could define: b : {0, 1} →N as:
b(e) = 0
b(0w) = 2b(w)
b(1w) = 1+ 2b(w)
Then define bin(w) = b(rev(w)), where rev is as defined in Assignment 1.
Problem 1 10 marks
Let Σ = {0, 1}3, so each element of Σ is a triple of symbols that are either 0 or 1. Let f , s, t : Σ → {0, 1}
be the functions that take a word from Σ and return the word of {0, 1} that is defined by considering
only the symbols in the first, second, or third (respectively) component. So if w =
(
0
0
0
) (
1
1
0
) (
1
0
1
) (
0
1
0
)
,
then f (w) = 0110, s(w) = 0101 and t(w) = 0010.
Show that the following language is regular:
{w ∈ Σ : bin( f (w)) + bin(s(w)) = bin(t(w))}.
Problem 2 10 marks
Let Σ = {0, #}. Show that the following language over Σ is context-free, but not regular:
{0i#0j#0i+j : i, j ≥ 0}
Problem 3 10 marks
Let Σ = {0, 1, #}. Show that the following language over Σ is not context-free:
{x#y#z : x, y, z ∈ {0, 1} and bin(x) + bin(y) = bin(z)}
1
Problem 4 10 marks
Let Σ = {0, 1, #}. Is the following language regular; context-free but not regular; or not context-free
Justify your answer
{x#y : x, y ∈ {0, 1} and bin(x) + 1 = bin(rev(y))}
Problem 5 10 marks
For languages A and B over Σ, define the language A÷ B as follows:
A÷ B = {w ∈ Σ : there exists x ∈ B such that wx ∈ A}
Show that if A is context-free and B is regular, then A÷ B is context-free.
Problem 6 50 marks
Consider the following grammar for representing simple calculations in Polish notation, given by G =
(V,Σ,R, E) where
V = {E, M, N, I}
Σ = {+, , , 0, 1, 2, x, y}
R consists of the rules:
E → +EE | EE | E | K | I
K → 0 | 1 | 2
I → x | y
(a) Is G ambiguous Justify your answer. (6 marks)
(b) Give a grammar in Chomsky Normal Form that is equivalent to G. (6 marks)
(c) Are the following words in the language generated by G Justify your answer.
(i) ++ 1y 20 (4 marks)
(ii) +1 xx (4 marks)
(iii) 0 210 (4 marks)
(d) Give a recursive definition for ParseG, the set of parse trees of words in L(G) (6 marks)
(e) For symbols X and Y we define Z[X,Y] = {a+ bX + cY + dX2 + eXY + . . . : a, b, c, d, e, . . . ∈ Z}. For
example, 3 + 2X + 5Y + 10XY ∈ Z[X,Y]. Recursively define a function eval : ParseG → Z[X,Y] that
calculates the value of the expression represented by the given parse tree (under the assumption that
eval(x) = X and eval(y) = Y). For example, if T were the parse tree of +11, then eval(T) = 2 because
1+ 1 = 2. Likewise eval(+ x21) = (X 2) + 1 = 2X+ 1. (8 marks)
Simplification
Partial marks can be obtained by defining a function eval : ParseG → Z that calculates the
expression represented by the given parse tree under the assumption that eval(x) = 5 and
eval(y) = 7. So eval(+ x21) = (x 2) + 1 = 15
2
(f) Explain how you could modify the CYK algorithm, or provide your own algorithm, to compute
eval(w) (if possible) for a word w ∈ Σ . (4 marks)
(g) Demonstrate how your algorithm computes:
(i) eval(+ +x12x) (4 marks)
(ii) eval( 1+ x 2 y) (4 marks)
3
