[UNSW] COMP9414: Artificial Intelligence ["SCSE"]

Exercises on Grammars

  1. Define two grammars G1 and G2 as follows:

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

    G2 has five 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 (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 aaabbb using G1.
    3. Harder: Prove informally that the grammar G1 generates all and only sentences in the set {anbn | n>= 1} .
    4. Derive the string aaabbbccc using G2.
    5. Harder: Prove informally that the grammar G2 generates all and only sentences in the set {anbncn | 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: PROthat: PRO, REL
    ii. NP → PRONvi. VP → Vis: VJack: NAME
    iii. NP → ART Nvii. 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 ab where the length of the string a is less than or equal to the length of the string b (call these CS1 rules), or by requiring that they are of the form lArlar, where l and r 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 ab can be converted into sets of equivalent rules of the form lArlar, and the proof proceeds by induction on the length of the string b

    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 f (i.e. a symbol not already in the alphabet of the grammar). Notice that AB → Af 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 3986
E-mail: billw at cse.unsw.edu.au

Last modified: 26 June 1998

CRICOS Provider Code No. 00098G