Description
Objectives
To familiarize with context-free languages, grammars for CFLs, parse trees and derivations, pushdown automata, CFL and PDA equivalence, closure properties of CFLs, pumping theorem for CFLs, Chomsky normal form, and Cocke-Younger-Kasami algorithm for parsing, Deterministic PDA.
Speci cations
You must adhere to the notation used in the textbook.
Your solution should be delivered as a .tex le based on your modi cation of the provided template 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 THE2.
-
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 designing 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 (26 pts)
a. Formally construct CFGs that generate each of the following languages. (16 pts)
-
fai baj bai+j 2 fa; bg j i; j 2 Ng
-
fw 2 fa; bg j the rst, last and middle character of w are the same, jwj > 3 and is oddg.
-
fai bj ck 2 fa; b; cg j i; j; k 0 and i 6= j or j 6= kg
-
fw1cw2c : : : cwkccwjR 2 fa; b; cg j k 1; 1 j k; wi 2 fa; bg+ for i = 1; : : : ; kg
b. Consider the CFG G = (V; ; R; S), where (10 pts)
-
= fa; b; S; A; Bg; = fa; bg;
R = fS ! aB j bA;
-
! a j aS j BAA; B ! b j bS j ABBg:
Prove that L(G) is the set of all nonempty strings in fa; bg that have equal numbers of occurrences of a and b.
2 Parse Trees and Derivations (10 pts)
Consider the CFG G = (V; ; R; S) where
-
-
= fa; b; S; A; Bg, = fa; bg, R = fS ! Ab j aaB; A ! a j Aa; B ! bg.
-
a. Find a string s 2 L(G) that has two leftmost derivations. Give these derivations and corresponding
parse trees. (4 pts)
b. Find an equivalent unambiguous context-free grammar. (3 pts)
-
Give the unique leftmost derivation and parse tree for the string s from a. with respect to the
grammar de ned in b. (3 pts)
2
3 Pushdown Automata (23 pts)
a. Find the language generated by the PDA given below (5 pts)
q2
a; e ! e a; e ! x
|
start |
q0 |
e; e ! # |
q1 |
e; e ! e |
q3 |
e; # ! e |
q6 |
|||||||
|
b; e ! e |
b; x ! e |
|||||||||||||
|
q4 |
q5 |
|||||||||||||
|
b; e ! e |
||||||||||||||
|
where the transition ((qi; ; ); (qj; )) is represented as: |
qi |
; ! |
qj |
|||||||||||
-
Design a PDA that generates the complement of the language fww 2 fa; bg j w 2 fa; bg g. (8 pts)
c.
|
(i) |
Design a PDA M that generates the language |
. |
(5 pts) |
|||||||||
|
f |
ai bj ck |
2 f |
a; b; c |
j |
i; j; k |
0; and i = j or j = k |
g |
|||||
|
g |
6 |
|||||||||||
|
(ii) |
Show that aabcc 2 L(M) and bac 62L(M) by tracing M on these strings. |
(5 pts) |
||||||||||
4 PDA and CFGs (8 pts)
a. Consider the CFG G = (V; ; R; E), where (4 pts)
V = fa; +; ; (; ); E; T; F g;
= fa; +; ; (; )g;
R = fE ! E + T j T;
T ! T F j F;
F ! (E) j ag:
Convert G to an equivalent PDA using Lemma 3.4.1.
b. Show that if M = (K; ; ; ; s; F ) is a PDA, then there is another PDA M0 = (K0; ; ; 0; s; F )
such that L(M0) = L(M) and for all ((qi; u; ); (qj; )) 2 0, j j + j j 1. (4 pts)
3
5 Closure Properties and Pumping Theorem (29 pts)
-
Use closure properties for CFLs to prove that the following languages are context-free.
|
(i) |
fam bm+n an 2 fa; bg j m; n 2 Ng |
(5 pts) |
|
(ii) |
fa; bg L, where L = fbabaabaaab : : : ban 1ban 2 fa; bg j n 1g |
(8 pts) |
-
Use Pumping Theorem for CFLs to show that following languages are not context-free.
|
(i) fambn 2 fa; bg j m; n 2 N and m n2g |
(8 |
pts) |
|
(ii) fwww 2 fa; bg j w 2 fa; bg g |
(8 |
pts) |
|
6 |
Closure Properties |
(4 pts) |
||
|
(T/F) |
If L is a CFL, L is not a CFL since CFLs are not closed under complementation. |
|||
|
(T/F) There exists CFLs L1 and L2 such that L1 \ L2 is a CFL. |
||||
|
(T/F) |
If L1 is a CFL and L2 is a regular language, L1 |
L2 is a CFL. |
||
|
(T/F) Every subset of a CFL is a CFL. |
||||
7 CNF and CYK (not graded)
-
Consider the CFG G = (fa; b; c; S; A; B; Cg; fa; b; cg; R; S), where
R = fS ! aAB j bBA
A ! BS j C
B ! bA
-
! c j eg:
Convert G into an equivalent CFG in Chomsky normal form.
-
Using CYK decide whether the following strings belong to L(G).
-
-
w1 = babcb
-
-
-
w2 = acbbab
-
8 Deterministic Pushdown Automata (not graded)
Construct a DPDA that generates the given languages.
-
fanbm 2 fa; bg j n; m 2 N and m n + 2g
-
fw 2 fa; bg j w starts and ends with the same symbol and have the same number of as and bs g
-
fanbman 2 fa; bg j m; n 2 Ng
4
Submission
You should submit your THE2 as a PDF le with the identi er the2.pdf on odtuclass. Please use the template provided on odtuclass with appropriate modi cations.
Soft-copies should be uploaded strictly by the deadline.
Late Submission: You have two days in total for late submission with penalties of 20 points and 50 points reduction in your grade for the rst and second day, respectively. No further submissions are accepted.
Regulations
-
Cheating: This take-home exam has to be completed and submitted individually. Teaming up, sharing solutions anywhere other parties might access and using work belonging to others as part or in whole are considered cheating. We have zero tolerance policy for cheating. People involved in cheating will be punished in accordance with the university regulations
-
Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr) for discussions and possible updates on a daily basis. You are advised to initiate discussions on COW so that most parties will bene t.
5
