Direction independent context-sensitive grammars. (English) Zbl 0599.68055

Kleijn, H. C. M.; Penttonen, M.; Rozenberg, G.; Salomaa, K.

Inf. Control 63, 113-117 (1984).

A direction independent variant of the standard normal form for context- sensitive grammars is given: the context-free productions are of the form \(A\to a\) or \(A\to BC\) and the context-sensitive productions are of the form AB\(\to AC\) or BA\(\to CA\), where AB\(\to AC\) is a production if and only if BA\(\to CA\) is a production. The equivalence of these grammars with the context-sensitive grammars is proved.

MSC:

68Q45

Formal languages and automata