Description
Question 1 (20 points)
G1 = {V, Σ, R, S} where V = {0, 1, S, A, B}, Σ = {0, 1} and R is;
S → A|B
A → 0A1|ϵ
B → 1B0|ϵ
a) (10 points) What does G1 represent? Answer with one sentence.
b) (10 points) Is G1 ambiguous? If yes, why?
Question 2 (30 points)
G2 = {V, Σ, R, S} where V = {a, b, S, A, B}, Σ = {a, b} and R is;
S → AB
A → aA|a|ϵ
B → bB|b|ϵ
a) (10 points) Show that G2 is ambiguous.
b) (10 points) Give an unambiguous grammar for L(G2).
c) (10 points) Give the leftmost derivation of the string abbb from the grammar you have constructed
for part b and draw the corresponding parse tree.
Question 3 (50 points)
a) (30 points) Show that the following languages are deterministic context-free.
i) L1 = {camb
n
| m ̸= n} ∪ {damb
2m | m ≥ 0}
ii) L2 = {a
mcbn
| m ̸= n} ∪ {a
mdb2m | m ≥ 0}
1
b) (20 points) Consider the following classes of languages:
i) Regular
ii) Context-free
iii) The class of the complements of context-free languages
iv) Deterministic context-free
Give a Venn diagram of these classes, so that inclusions, intersections, etc. of classes are reflected accurately.
Specifications
• Deadline: The deadline for this homework is strict and no late submissions will be accepted.
Submission deadlines are not subject to postponement.
• Grading: “sufficiently reasonable” solutions will get full credit for the subject question,
even if it is partially incorrect. Rough criteria for a solution to be sufficiently reasonable are being
the student’s original answer and at least partially relying on a correct approach/method even if the
application is not totally correct.
• Cheating: Any type of cheating or extensive collaboration is strictly prohibited. In case of cheating,
the cheater’s all homeworks will be graded zero (0); further, university regulations about cheating
will be applied.
• Updates: Follow the course page on ODTUClass for any updates and clarifications. Please ask your
questions on ODTUClass instead of e-mailing if they do not contain some part of the solution. Otherwise, you can send an email to “mduymus@ceng.metu.edu.tr” and/or “mferhata@ceng.metu.edu.tr”.
Submission
Submissions will be done via ODTUClass. You are expected to submit a single searchable/vectorized
PDF file named “HW5_yourStudentID.pdf (e.g. HW5_1234567)”. Submissions violating the naming
convention will be penalized. Also write your name and student ID number to the top of your solution
sheets. A grade reduction will be applied to the solution sheets without a name and ID on them.
2
