In some of these solutions, helps to know that L(G), the language generated by the grammar G, means the set of all strings of terminals that can be derived from the start symbol S using the grammar rules of the grammar G.

1. 1. G₁ is context-free; G₂ is context-sensitive.

   2. S ⇒ a S b ⇒ a a b b;
      S ⇒ a S b ⇒ a a S b b ⇒ a a a b b b

   3. At any point, there is a choice of two rules: if S → a b is chosen, the derivation stops. If the other rule (S → a S b) is chosen, the derivation does not stop, as the RHS of that rule includes the non-terminal S. There is only ever one S in a sentential form (the number of non-terminals can only increase if a rule with ≥ 2 non-terminals in its RHS is applied). Thus any complete derivation consists of k ≥ 0 applications of S → a S b followed by the single application of S → a b, producing the sentence a^k+1b^k+1. Hence L(G₁) = {a^k+1b^k+1 | k≥0} = { aⁿ bⁿ | n≥1}, as claimed.

   4. S ⇒ a S B C ⇒ a a S B C B C ⇒ a a a b C B C B C ⇒ a a a b B C C B C ⇒ a a a b B C B C C ⇒ a a a b B B C C C ⇒ a a a b b B C C C ⇒ a a a b b b C C C ⇒ a a a b b b c C C ⇒ a a a b b b c C C ⇒ a a a b b b c c C ⇒ a a a b b b c c c

      Other orders of derivation are possible, e.g. b B → b b could have been used immediately after the first application of C B → B C.

   5. G₂ has the rules:

      S → a S B C
      S → a b C
      C B → B C
      b B → b b
      b C → b c
      c C → c c

      Only the first two rules affect the length of the string being derived. As with part (c), when the 2nd rule (S → a b C) is applied, string growth stops (and then neither of the first two rules can be used again). The last three rules cannot be used until the single use of S → a b C provides the b. Hence the initial phase of derivation consists of n–1 applications of S → a S B C followed by the single application of S → a b C, possibly interspersed with uses of C B → B C. (The rule C B → B C simply serves to move the Bs left and the Cs right.) At this point, the string contains n as, one b and n–1 Bs, and n Cs. The remaining rules do not change the number of Bs+bs, nor the number of Cs+cs. The rule b B → b b serves to convert Bs to bs left to right through the string. The rules b C → b c and c C → c c cannot be used until b B → b b has been used enough times to get a b adjacent to a C in the derived string. For this to happen, the string must be of the form aⁿ b^p b C followed by a string of Bs and Cs (possibly 0 Bs, definitely n Cs). If there are in fact any Bs in the rest of the string, then the derivation will block, since while the rule c C → c c converts C into c, there is not a rule c B → c b to convert B into b. If there were no Bs in the rest of the string, then the string was of the form aⁿ b^n–1 b Cⁿ, and then the only possible rule applications are a single b C → b c followed by n–1 uses of c C → c c, yielding aⁿ bⁿ cⁿ. So all strings derivable are of the form aⁿ bⁿ cⁿ. Conversely, to derive aⁿ bⁿ cⁿ, apply S → a S B C n–1 times followed by S → a b C and then n(n–1)/2 applications of C B → B C to get aⁿ b B^n–1 Cⁿ, then apply b B → b b n–1 times followed by b C → b c followed by n–1 uses of c C → c c to get aⁿ bⁿ cⁿ.

2. S ⇒
   NP VP ⇒
   PRO VP ⇒
   This VP ⇒
   This V NP ⇒
   This is NP ⇒
   This is NP REL S ⇒
   This is ART N REL S ⇒
   This is the N REL S ⇒
   This is the house REL S ⇒
   This is the house that S ⇒
   This is the house that NP VP ⇒
   This is the house that NAME VP ⇒
   This is the house that Jack VP ⇒
   This is the house that Jack V ⇒
   This is the house that Jack built
   

   

3. 1. Introduce a new non-terminal symbol φ (i.e. a symbol not already in the alphabet of the grammar). A B → C D may now be replaced by the three type 2) rules, to be used one after the other:

      A B → A φ (B → φ in the left context A and right context ε)

      A φ → C φ (A → C in the left context ε and right context φ)

      C φ → C D (φ → D in the left context C and right context ε)

      Remember that ε is the empty string, so that in full, the first rule is A B ε → A φ ε, since A B ε = A B, and A φ ε = A φ.

      No solution is provided for the inductive step. You could start by figuring out how to extend the argument above to work for A B → C D E, and for A B C → D E F, and for A B → C₁ C₂ ... C_n.