Assignment 8: Simplification, Normal Forms, and Properties of CFLs

This assignment evaluates and deepens your understanding of Context-Free Grammar (CFG) simplification, normal forms (Chomsky and Greibach), the CYK parsing algorithm, the CFL Pumping Lemma, and closure/decision properties, synthesizing Michael Sipser (Chapter 2.1 & 2.3) and Peter Linz (Chapters 6 & 8).

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 = (V, T, S, P)\) is in Chomsky Normal Form (CNF), then for any non-empty string \(w \in L(G)\) of length \(n = |w| \ge 1\), every derivation of \(w\) in \(G\) takes exactly \(2n - 1\) steps.

Question 2

The family of Context-Free Languages (CFLs) is closed under intersection, meaning that if \(L_1\) and \(L_2\) are context-free, then \(L_1 \cap L_2\) is guaranteed to be context-free.

Question 3

If \(L\) is a Context-Free Language over \(\Sigma\) and \(R\) is a Regular Language over \(\Sigma\), then the intersection \(L \cap R\) is guaranteed to be a Context-Free Language.

Question 4

In the CFL Pumping Lemma (\(w = uvxyz\)), the bounded condition \(|vxy| \le m\) implies that the pumpable substring \(vxy\) must always reside within the first \(m\) characters at the beginning of the string \(w\).

Section B: Multiple Choice Questions (MCQs)

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

Question 5

Which of the following operations preserve context-freeness (i.e., Context-Free Languages are closed under these operations)? (Select all that apply)

• Options:
  • A) Union (\(L_1 \cup L_2\))
  • B) Concatenation (\(L_1 \cdot L_2\))
  • C) Kleene Star (\(L^*\))
  • D) Complementation (\(\bar{L} = \Sigma^* - L\))

Question 6

Consider the grammar simplification pipeline and normal form transformations. Which of the following statements are correct? (Select all that apply)

• Options:
  • A) A variable \(A\) is called nullable if there exists a derivation \(A \Rightarrow^* \lambda\).
  • B) In Greibach Normal Form (GNF), every production rule is of the form \(A \to a\alpha\), where \(a \in T\) and \(\alpha \in V^*\).
  • C) When converting a CFG to Chomsky Normal Form (CNF), \(\lambda\)-productions and unit productions (\(A \to B\)) must be eliminated before replacing terminal mixtures or breaking long variable chains.
  • D) A variable \(A\) is defined as useful if it is both generating (\(A \Rightarrow^* w \in T^\)) and reachable (\(S \Rightarrow^ xAy\)).

Section C: Analytical, Numerical, & Proof Questions

Provide complete, step-by-step mathematical derivations, dynamic programming tables, and formal proofs.

Question 7 (Grammar Simplification & CNF Conversion)

Simplify the following context-free grammar \(G\) by eliminating useless variables, \(\lambda\)-productions, and unit productions, and then convert the resulting grammar into Chomsky Normal Form (CNF):

\[S \to aA \mid B \mid \lambda\] \[A \to aA \mid \lambda\] \[B \to bB \mid C\] \[C \to c\]

Question 8 (Execution of the CYK Parsing Algorithm)

Let \(G\) be the following grammar in Chomsky Normal Form: \[S \to AB \mid BC\] \[A \to BA \mid a\] \[B \to CC \mid b\] \[C \to AB \mid a\]

Use the Cocke-Younger-Kasami (CYK) dynamic programming algorithm to construct the triangular table \(P\) for the input string \(w = abba\) (length \(n = 4\)). Determine whether \(w \in L(G)\).

Question 9 (CFL Pumping Lemma Formal Proofs)

Rigorously prove using the CFL Pumping Lemma that the following languages are not Context-Free:

1. \(L_1 = {a^n b^n c^n \mid n \ge 0}\)
2. \(L_2 = {w w \mid w \in {a, b}^*}\)

Question 10 (Emptiness Decision Algorithm for CFGs)

Provide a complete, step-by-step formal algorithm to decide whether the language generated by an arbitrary Context-Free Grammar \(G = (V, T, S, P)\) is empty (\(L(G) = \emptyset\)). Prove its correctness and termination.