COMP9414/9814 - Exercises on Grammars

  1. Define two grammars G1 and G2 as follows:

    G1 has two rules: Sa S b and Sa b (a, b are terminals, S is the unique non-terminal and the start symbol.)

    G2 has six rules:

    Sa S B C
    Sa b C
    C BB C
    b Bb b
    b Cb c
    c Cc c
    (a, b, c are terminals, S, B, C are non-terminals and S is the start symbol.)

    1. Classify G1 and G2 as unrestricted, context-sensitive, context-free, or regular grammars.
    2. Derive the string a a a b b b using G1.
    3. Harder: Prove informally that the grammar G1 generates all and only sentences in the set {an bn | n ≥ 1} .
    4. Derive the string a a a b b b c c c using G2.
    5. Harder: Prove informally that the grammar G2 generates all and only sentences in the set {an bn cn | 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:   andLexicon:
    i. S → NP VPv. NP → NP REL Sthis: PRO   that: PRO, REL
    ii. NP → PRONvi. VP → Vis: VJack: NAME
    iii. NP → ART N     vii. VP → V NPthe: ARTbuilt: 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 ρ → λ α ρ, 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 ρ → λ α ρ, and the proof proceeds by induction on the length of the string β.

    1. Begin this proof by showing that the CS1 rule A BC D 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 A BA φ 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.


Page maintained by:
Bill Wilson
Phone: 9385 6876

CRICOS Provider Code No. 00098G