CENG Abstract Machines Take Home Exam 2 Solution

Objectives

To familiarize with Context Free Languages, grammars for CFL and Pushdown Automata, parse trees and derivations, closure properties of CFL, Pumping Lemma for CFL, Chomsky Normal Form and Cocke-Younger-Kasami Algorithm for parsing, Deterministic PDA.


Speci cations

You must adhere to the notation conventions adopted in the textbook.

Your solution should be delivered as a .tex le based on your modi cation of the provided tem-plate le. For convenience, a simple code for drawing a tree is included in the following. On the left-hand side you can see the code segment, and generated tree is placed on the right. You can also use the automata template given in THE1.


% preamble

\usepackage{tikz}

\usepackage{tikz-qtree}

    • document

    • use qtree

\Tree [.S [.NP $$\LaTeX$$ ] [.VP [.V is ] [.NP fun ] ] ]

    • or tikz-qtree with possible tikz options \begin{tikzpicture}[scale=1]

\Tree [.S [.NP $$\LaTeX$$ ] [.VP [.V is ] [.NP fun ] ] ]

\end{tikzpicture}


S



NP    VP


LATEX    V    NP


is    fun

The questions and submission regulations are included in subsequent sections. While design-ing your solutions to the tasks, explicitly state any assumptions you make and pay particular attention to the notation you use. Your proofs must be sound and complete. Grading will be heavily a ected by the formalization of your solutions.



1

1    Context-Free Grammars    (10 pts)

    a) Give the rules of the Context-Free Grammars to recognize strings in the given languages where = fa; bg and S is the start symbol.

L(G) = fw j
w 2
; jwj  3;
(2/10 pts)

the  rst and the second from the last symbols of w are the sameg

L(G) = fw j
w 2
;
the length of w is oddg
(2/10 pts)
L(G) = fw j
w 2
;
n(w; a) = 2 n(w; b)g where n(w; x) is the number of x symbols in w (3/10 pts)

b)  Find the set of strings recognized by the CFG rules given below:    (3/10 pts)

S ! X j Y

    • ! aXb j A j B A ! aA j a

B ! Bb j b Y ! CbaC
C ! CC j a j b j "



2    Parse Trees and Derivations    (20 pts)

Given the CFG below, provide parse trees for given sentences in a and b.


    • !NPVP
VP
!VNP|VNPPP

PP
!PNP

NP
!N|DN|NPPP

V
! wrote | built | constructed

D
! a | an | the | my

N
! John | Mary | Jane | man | book | automata | pen | class

P
! in | on | by | with

a)
Jane constructed automata with a pen
(4/20 pts)
b)
my book in the man built a Jane by a pen
(4/20 pts)

Given the CFG below, answer c, d and e


    • ! E

    • !E+T|E-T|T T !T*I|T/I|I

I !0|1|2|3|4|6|7|8|9





2

c)
Provide the left-most derivation of 7 - 4 * 3 step-by-step and plot the  nal parse
(4/20 pts)
tree matching that derivation

d)  Provide the right-most derivation of 7 - 4 * 3 step-by-step and plot the  nal parse
(4/20 pts)
tree matching that derivation

e)
Are the derivations in c and d in the same similarity class?
(4/20 pts)



3
Pushdown Automata









(30 pts)
a)  Find the language recognized by the PDA given below





(5/30 pts)





y; x ! "

z; " ! "











q2

";#!"


q4



























";"!"














q0
";"!#

q1
































";"!"
















x; " ! x
";"!"




";#!"









q3




q5


q6























y; " ! "

z; x ! "






where the transition ((qi;  ;  ); (qj ;  )) is represented as:
qi
;  !

qj














b)
Design a PDA to recognize language L = fxnym+nxm j n; m   0; n; m 2 Ng
(5/30 pts)
c)
Design a PDA to recognize language L = fxnym j n < m   2n; n; m 2 N+g

(10/30 pts)

Do not use multi-symbol push/pop operations in your transitions.

Simulate the PDA on strings xxy (with only one rejecting derivation) and xxyyyy (accepting deriva-tion) with transition tables.


d) Given two languages L0 and L as L0 = fw j w 2 L; jw j = 4n + 2 f or n 2 Ng (10/30 pts) If L is a CFL, show that L0 is also a CFL by constructing an automaton for L0 in terms of another automaton that recognizes L.



3

4    Closure Properties    (20 pts)

Let L1 and L2 be context-free languages which are not regular, and let L3 be a regular language. De-termine whether the following languages are necessarily CFLs or not. If they need to be context-free, explain your reasoning. If not, give one example where the language is a CFL and a counter example where the language is not a CFL.


a)  L4 = L1 \ (L2 n L3)    (10/20 pts)


b)  L5 = (L1 \ L3)*    (10/20 pts)



5
Pumping Theorem
(20 pts)
a)
Show that L = fanmnti j n   i   2ng is not a Context Free Language
(10/20 pts)
using Pumping Theorem for CFLs.

b)
Show that L = fanb2nan j n 2 N+g is not a Context Free Language
(10/20 pts)
using Pumping Theorem for CFLs.







































4

6    CNF and CYK    (not graded)

    a) Convert the given context-free grammar to Chomsky Normal Form.

S ! XSX j xY

X ! Y j S

    • ! z j "


    b) Use the grammar below to parse the given sentence using Cocke{Younger{Kasami algorithm. Plot the parse trees.


S!NPVP

S!X1VP

X1 ! Aux NP

S ! book j include j prefer S ! Verb NP S!X2PP

S ! Verb PP

S!VPPP

NP ! I j she j me j Houston NP ! Det Nom
Nom ! book j ight j meal j money Nom ! Nom Noun Nom ! Nom PP


VP ! book j include j prefer

VP ! Verb NP

VP!X2PP

X2 ! Verb NP

VP ! Verb PP

VP!VPPP

PP ! Prep NP

Det ! that j this j the j a

Noun ! book j    ight j meal j money

Verb ! book j include j prefer

Aux ! does

Prep ! from j to j on j near j through


book the    ight through Houston



7    Deterministic Pushdown Automata    (not graded)

Provide a DPDA to recognize the given languages, the DPDA must read its entire input and nish with an empty stack.

    a) a bc [ anbnc


    b) (aa) c [ anbnc













5

Submission

Late Submission: You have 2 days in total for late submission of all take-home exams. All submissions will be graded as normal during this period. No further late submissions are ac-cepted.

You should submit your solutions as a single le named the2-e1234567.tex. Please use the template provided on COW with appropriate modi cations. THE should compile and produce a PDF le with a single command:

pdflatex the2-e1234567.tex

You do not need to submit solutions for not-graded questions. Yet solving them is advisable for studying for the midterm.


Regulations

    1. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.

    2. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and pos-sible updates on a daily basis.


References

Various LATEX examples on drawing and mathematical symbols:

https://en.wikibooks.org/wiki/LaTeX/Mathematics https://en.wikibooks.org/wiki/LaTeX/Linguistics https://www.texample.net/tikz/examples/

https://www1.essex.ac.uk/linguistics/external/clmt/latex4ling/
























6