COMP9414: Artificial Intelligence |

- Define two grammars G
_{1}and G_{2}as follows:G

_{1}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.G

_{2}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.- Classify G
_{1}and G_{2}as unrestricted, context-sensitive, context-free, or regular grammars.> - Derive the string
*aaabbb*using G_{1}. *Harder:*Prove informally that the grammar G_{1}generates all and only sentences in the set {a^{n}b^{n}| n>= 1} .- Derive the string
*aaabbbccc*using G_{2}. *Harder:*Prove informally that the grammar G_{2}generates all and only sentences in the set {a^{n}b^{n}c^{n}| n>= 1} .

- Classify G
- 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:**and **Lexicon:**i. S → NP VP v. NP → NP REL S this: PRO that: PRO, REL ii. NP → PRON vi. VP → V is: V Jack: NAME iii. NP → ART N vii. VP → V NP the: ART built: V iv. NP → NAME house: N - It was mentioned in lectures that context-sensitive grammar rules can be
defined
**either**by requiring that they are of the form a → b 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 lAr → lar, 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 a→ b can be converted into sets of equivalent rules of the form lAr → lar, and the proof proceeds by induction on the length of the string b- 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. - [
*For enthusiasts only*]: Part (a), above, provides most of the base-step of the inductive proof. Complete this proof by providing the inductive step.

- Begin this proof by showing that the CS1 rule AB → CD may be replaced
by three CS2 rules. Hint: Introduce

Bill Wilson

Phone: 9385 3986

E-mail: billw at cse.unsw.edu.au

*
Last modified: 26 June 1998
*

CRICOS Provider Code No. 00098G