×

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
PDF BibTeX XML Cite
Full Text: DOI