On permutative grammars generating context-free languages
type: Item
instance of: scholarly article
title: On permutative grammars generating context-free languages
zbMATH Open document ID: 0582.68045
DOI: 10.1007/BF01936139
published in: BIT
publication date: 1985-01-01T00:00:00Z
review text: A grammar is said to be permutative if it has permutation productions of the form AB\(\to BA\) in addition to context-free productions. Szilard languages and label languages are studied as examples of languages generable by permutative grammars. Particularly, sufficient conditions for a permutative grammar to generate a context-free language are studied.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3932415
zbMATH Keywords: Szilard languages
zbMATH Keywords: label languages
author: Erkki Mäkinen
MaRDI profile type: Publication
cites work: A general class of noncontext free grammars generating context free languages
cites work: Non-context-free grammars generating context-free languages
cites work: On the structure of context-sensitive grammars
cites work: Q4198075
cites work: A normal form theorem for label grammars
cites work: Associate languages and derivational complexity of formal grammars and languages
description: scientific article; zbMATH DE number 3932415