## 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