COMP9414/9814 - Exercises on Grammars

1. Define two grammars G₁ and G₂ as follows:

   G₁ has two rules: S → aSb and S → ab (a, b are terminals, S is the unique non-terminal and the start symbol.

   G₂ has five rules: S → aSBC, S → abC, CB → BC, bB → bb, bC → bc, cC → cc (a, b, c are terminals, S, B, C are non-terminals and S is the start symbol.

   1. Classify G₁ and G₂ as unrestricted, context-sensitive, context-free, or regular grammars.>
   2. Derive the string aaabbb using G₁.
   3. Harder: Prove informally that the grammar G₁ generates all and only sentences in the set {aⁿbⁿ | n≥ 1} .
   4. Derive the string aaabbbccc using G₂.
   5. Harder: Prove informally that the grammar G₂ generates all and only sentences in the set {aⁿbⁿcⁿ | n ≥ 1} .

2. Given the grammar rules and lexicon shown below, derive the sentence This is the house that Jack built. Draw the parse tree, labelling your subtrees with the numbers of the grammar rules used to derive them.

   Grammar rules:		and	Lexicon:
   i. S → NP VP	v. NP → NP REL S		this: PRO	that: PRO, REL
   ii. NP → PRON	vi. VP → V		is: V	Jack: NAME
   iii. NP → ART N	vii. VP → V NP		the: ART	built: V
   iv. NP → NAME			house: N

3. It was mentioned in lectures that context-sensitive grammar rules can be defined either by requiring that they are of the form α → β where the length of the string α is less than or equal to the length of the string β (call these CS1 rules), or by requiring that they are of the form λAρ → λaρ, where λ and ρ are arbitrary, possibly null, strings of grammar symbols (call these CS2 rules). The proof of this equivalence consists of showing that rules of the form α → β can be converted into sets of equivalent rules of the form λAρ → λaρ, and the proof proceeds by induction on the length of the string β.
   1. Begin this proof by showing that the CS1 rule AB → CD may be replaced by three CS2 rules. Hint: Introduce a new non-terminal symbol φ (i.e. a symbol not already in the alphabet of the grammar). Notice that AB → Aφ is a CS2 rule.

   2. [For enthusiasts only]: Part (a), above, provides most of the base-step of the inductive proof. Complete this proof by providing the inductive step.

CRICOS Provider Code No. 00098G