Sale!

# CENG 280 Homework 5 Solved

Original price was: \$40.00.Current price is: \$35.00.

Category:

5/5 - (1 vote)

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