On regularity of context-free languages
type: Item
instance of: scholarly article
title: On regularity of context-free languages
zbMATH Open document ID: 0553.68044
DOI: 10.1016/0304-3975(82)90124-4
author: Andrzej Ehrenfeucht
author: Grzegorz Rozenberg
author: David Haussler
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: This paper considers conditions under which a context-free language is regular and conditions which imposed on (productions of) a rewriting system generating a context-free language will guarantee that the generated language is regular. In particular: (1) necessary and sufficient conditions on productions of a unitary grammar are given that guarantee the generated language to be regular (a unitary grammar is a semi-Thue system in which the left-hand of each production is the empty word), and (2) it is proved that commutativity of a linear language implies its regularity. To obtain the former result, we give a generalization of the Myhill-Nerode characterization of the regular languages in terms of well-quasi orders, along with a generalization of Higman's well-quasi order result concerning the subsequence embedding relation on \(\Sigma^*\). In obtaining the latter results, we introduce the class of periodic languages, and demonstrate how they can be used to characterize the commutative regular languages. Here we also utilize the theory of well-quasi orders.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3881893
zbMATH Keywords: iterative pair
zbMATH Keywords: pure squares
zbMATH Keywords: isertion language
zbMATH Keywords: subword complete
zbMATH Keywords: context-free language
zbMATH Keywords: rewriting system
zbMATH Keywords: unitary grammar
zbMATH Keywords: semi-Thue system
zbMATH Keywords: commutativity
zbMATH Keywords: linear language
zbMATH Keywords: periodic languages
zbMATH Keywords: regular languages
zbMATH Keywords: well-quasi orders
MaRDI profile type: Publication
full work available at URL: 0304-3975(82)90124-4
OpenAlex ID: W1989943994
Wikidata QID: Q126298324
cites work: Q5602108
cites work: Q3873564
cites work: Monadic Thue systems
cites work: Q5526125
cites work: Q4195154
cites work: Une généralisation des ensembles de Dyck
cites work: Q5639639
cites work: On basic properties of DOS systems and languages
cites work: Q3959450
cites work: Scattered context grammars
cites work: On free monoids partially ordered by embedding
cites work: Q4198075
cites work: Insertion languages
cites work: Ordering by Divisibility in Abstract Algebras
cites work: The theory of well-quasi-ordering: a frequently discovered concept
cites work: Cônes rationnels commutatifs
cites work: Well-quasi-orderings and sets of finite sequences
cites work: Q5734436
cites work: Linear Automaton Transformations
cites work: Recursive Unsolvability of a problem of Thue
cites work: Q5678435
description: scientific article; zbMATH DE number 3881893