# zbMATH — the first resource for mathematics

Direction independent context-sensitive grammars. (English) Zbl 0599.68055
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
Full Text: