Assignment 5: Context-Free Languages and Grammars

Section A: True or False Questions

For each question, select True or False and provide a rigorous mathematical justification.

Question 1

If a context-free grammar $G$ is unambiguous, then for every string $w \in L(G)$, there exists exactly one leftmost derivation and exactly one rightmost derivation, and both derivations correspond to the same unique parse tree.

Question 2

The family of regular languages is a proper subset of context-free languages. Consequently, every right-linear grammar is context-free, but not every context-free grammar is regular.

Question 3

If a context-free language $L$ is inherently ambiguous, then there exists at least one unambiguous CFG $G$ such that $L(G) = L$.

Question 4

A linear grammar is a context-free grammar where every production rule has at most one variable on its right-hand side. Every linear grammar is guaranteed to generate a regular language.

Section B: Multiple Choice Questions (MCQs)

Select all options that apply. You must justify your choices mathematically.

Question 5

Let $G = (V, T, S, P)$ be a context-free grammar. Which of the following statements regarding derivations, sentential forms, and parse trees are correct? (Select all that apply)

• Options:
  • A) A sentential form is any string $w \in (V \cup T)^*$ such that $S \Rightarrow^* w$.
  • B) The yield of any partial derivation tree with root $S$ is a sentential form of $G$.
  • C) If a complete derivation tree has only terminals at its leaves, its yield is a sentence in $L(G)$.
  • D) A single parse tree can correspond to multiple distinct leftmost derivations.

Question 6

Consider the grammar $G$ over $\Sigma = \{a, b\}$ with production rules:

Which of the following statements are correct? (Select all that apply)

• Options:
  • A) $G$ is an ambiguous grammar because the string $ab$ has two distinct parse trees.
  • B) $G$ is unambiguous because it generates the regular language $(ab)^*$.
  • C) The leftmost derivation $S \Rightarrow aSb \Rightarrow ab$ and the leftmost derivation $S \Rightarrow abS \Rightarrow ab$ represent different syntactic structures for $ab$.
  • D) $L(G) = \{a^n b^n \mid n \geq 0\}$.

Section C: Analytical, Numerical, & Proof Questions

Provide complete, step-by-step mathematical derivations, parse trees, and formal proofs.

Question 7 (CFG Design and Analysis)

Design a context-free grammar $G$ over $\Sigma = \{a, b\}$ that generates the language:

1. Provide the formal 4-tuple description $G = (V, \Sigma, R, S)$.
2. Show the leftmost derivation for the string $aaab$.
3. Draw the corresponding parse tree for $aaab$.

Question 8 (Leftmost/Rightmost Derivations and Ambiguity)

Consider the expression grammar $G$ over $\Sigma = \{a, b, +, \times\}$ with rules:

For the string $w = a + b \times a$:

1. Show two distinct leftmost derivations.
2. Show their corresponding rightmost derivations.
3. Draw the two distinct parse trees.

Question 9 (The Concept of Inherent Ambiguity)

The context-free language:

is inherently ambiguous.

1. Explain intuitively why any context-free grammar designed to generate $L$ must be ambiguous.
2. Identify a specific subset of strings in $L$ that forces ambiguity, and describe how these strings are parsed under two different syntactic interpretations.

Question 10 (Mathematical Induction Proof on Tree Height)

A context-free grammar $G = (V, T, S, P)$ is in Chomsky Normal Form (CNF) if all production rules are of the form $A \to BC$ or $A \to a$, where $A, B, C \in V$ and $a \in T$.

Prove by mathematical induction on the height $h \geq 1$ of a parse tree that the length of its yield, denoted $|w|$, is at most $2^{h-1}$.