Definition 7.2.6: if G = (V, _, P, S) is a phrase structure grammar, and ____(V__)*•V•(V__)*, a production _____ is called invertible, and ______is its inverse.
Lemma 7.2.1: if G = (V, _, P, S) is a phrase structure grammar and __P is invertible with inverse _-1, then for all x,y_(V__)*, x _ y via _ if and only if y _ x via _-1.
Theorem 7.2.2: each LBA language is context-sensitive.
Previous slide | Next slide | Back to first slide | View graphic version |