### Solutions to Selected Grammar Problems

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. G1 is context-free; G2 is context-sensitive.

2. Sa S ba a b b;
Sa S ba a S b ba a a b b b

3. At any point, there is a choice of two rules: if Sa b is chosen, the derivation stops. If the other rule (Sa 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 Sa S b followed by the single application of Sa b, producing the sentence ak+1bk+1. Hence L(G1) = {ak+1bk+1 | k≥0} = { an bn | n≥1}, as claimed.

4. Sa S B Ca a S B C B Ca a a b C B C B Ca a a b B C C B Ca a a b B C B C Ca a a b B B C C Ca a a b b B C C Ca a a b b b C C Ca a a b b b c C Ca a a b b b c C Ca a a b b b c c Ca 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 BB C.

5. G2 has the rules:
Sa S B C
Sa b C
C BB C
b Bb b
b Cb c
c Cc c

Only the first two rules affect the length of the string being derived. As with part (c), when the 2nd rule (Sa 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 Sa b C provides the b. Hence the initial phase of derivation consists of n–1 applications of Sa S B C followed by the single application of Sa b C, possibly interspersed with uses of C BB C. (The rule C BB 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 Bb b serves to convert Bs to bs left to right through the string. The rules b Cb c and c Cc c cannot be used until b Bb 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 an bp 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 Cc c converts C into c, there is not a rule c Bc b to convert B into b. If there were no Bs in the rest of the string, then the string was of the form an bn–1 b Cn, and then the only possible rule applications are a single b Cb c followed by n–1 uses of c Cc c, yielding an bn cn. So all strings derivable are of the form an bn cn. Conversely, to derive an bn cn, apply Sa S B C n–1 times followed by Sa b C and then n(n–1)/2 applications of C BB C to get an b Bn–1 Cn, then apply b Bb b n–1 times followed by b Cb c followed by n–1 uses of c Cc c to get an bn cn.

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

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

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

A φ → C φ (AC 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 BC D E, and for A B CD E F, and for A BC1 C2 ... Cn.

CRICOS Provider Code No. 00098G