S -> NP Aux VP -> NP VP -> Aux NP VP NP -> Det Adjs N PPs -> NPR VP -> V NP PPs -> V PPs Adjs -> Adjs Adj -> epsilon PPs -> PPs PP -> epsilonAn ATN that can't be written as a context free grammar is:

(S/ (PUSH NP/ T (SETR NP *) (TO S/NP))) (S/NP (PUSH VP/ T (SETR VP *) (TO S/NP-VP))) (S/NP-VP T (POP (BUILDQ (S + +) NP VP) (EQ (THIRD (GETR NP)) (THIRD (GETR VP))))) (NP/ (CAT N T (SETR NUMBER (GETP NUMBER)) (SETR N *) (TO NP/POP))) (NP/POP (POP (BUILDQ (NP + +) N NUMBER) T)) (VP/ (CAT V T (SETR NUMBER (GETP NUMBER)) (SETR V *) (TO VP/V))) (VP/V (PUSH NP/ T (SETR VNP *) (TO VP/V-POP)) (POP (BUILDQ (VP + +) V NUMBER) T)) (VP/V-POP (POP (BUILDQ (VP + + +) V NUMBER VNP) T))

- An asterisk (*) means the root of the current word, except in a PUSH-arc, where it is the structure that has been pushed.
- GETP gets an attribute of the current word from the dictionary.
- SETR assigns a value to a local register. When a PUSH is performed a new environment with local registers is created.
- GETR returns the value of a local register.

97-05-13, 09:45:50 MEST