Solutions to Selected Grammar Problems

    1. G1 is context-free; G2 is context-sensitive.

    2. S ⇒ aSb⇒ aabb; S ⇒ aSb ⇒ aaSbb⇒ aaabbb

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

    4. S ⇒ aSBC ⇒ aaSBCBC ⇒ aaabCBCBC ⇒ aaabBCCBC ⇒ aaabBCBCC ⇒ aaabBBCCC
      ⇒ aaabbBCCC ⇒ aaabbbCCC ⇒ aaabbbcCC ⇒ aaabbbcCC ⇒ aaabbbccC ⇒ aaabbbccc

      Other orders of derivation are possible, e.g. bB→ bb could have been used immediately after the first application of CB→ BC.

    5. G2 has the rules: S → aSBC, S → abC, CB → BC, bB → bb, bC → bc, cC → cc.

      Only the first two rules affect the length of the string being derived. As with part (c), when the 2nd rule (S → abC) 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 → abC provides the b. Hence the initial phase of derivation consists of n-1 applications of S → aSBC followed by the single application of S → abC, possibly interspersed with uses of CB → BC. (The rule CB → BC simply serves to move the B's left and the C's right.) At this point, the string contains n a's, one b and n-1 B's, and n C's. The remaining rules do not change the number of B's+b's, nor the number of C's+c's. The rule bB → bb serves to convert B's to b's left to right through the string. The rules bC → bc and cC → cc cannot be used until bB → bb 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 anbpbC followed by a string of B's and C's (possibly 0 B's, definitely n C's). If there are in fact any B's in the rest of the string, then the derivation will block, since while the rule cC → cc converts C into c, there is not a rule cB → cb to convert B into b. If there were no B's in the rest of the string, then the string was of the form anbn-1bCn, and then the only possible rule applications are a single bC → bc followed by n-1 uses of cC → cc, yielding anbncn. So all strings derivable are of the form anbncn. Conversely, to derive anbncn, apply S → aSBC n-1 times followed by S → abC and then n(n-1)/2 applications of CB → BC to get anbBn-1Cn, then apply bB → bb n-1 times followed by bC → bc followed by n-1 uses of cC → cc to get anbncn.

  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). AB → CD may now be replaced by the three type 2) rules

      AB → Aφ (B → φ in the left context A)

      Aφ → Cφ (A → C in the right contextφ)

      Cφ → CD (φ → D in the left context C)

CRICOS Provider Code No. 00098G