- 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 six 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
*a a a b b b*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
*a a a b b b c c c*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
- 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 α → β 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 β.- Begin this proof by showing that the CS1 rule
*A B*→*C 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 B*→*A*φ 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

Bill Wilson

Phone: 9385 6876

*
*

CRICOS Provider Code No. 00098G