Prefix grammars: An alternative characterization of the regular languages
type: Item
instance of: scholarly article
title: Prefix grammars: An alternative characterization of the regular languages
zbMATH Open document ID: 0813.68125
DOI: 10.1016/0020-0190(94)00074-3
author: Michael Frazier
author: C. David jun. Page
published in: Information Processing Letters
publication date: 1994-09-05T00:00:00Z
review text: A prefix grammar \(G\) describes a language \(L_ G\) by (1) explicitly specifying a finite subset of the strings of \(L_ G\), and (2) specifying productions that rewrite prefixes of strings in \(L_ G\), to yield other strings in \(L_ G\). Suffix grammars can be defined in the obvious manner analogous to prefix grammars. This paper shows that prefix grammars generate exactly the regular languages.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 633514
zbMATH Keywords: suffix grammars
zbMATH Keywords: prefix grammars
zbMATH Keywords: regular languages
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00074-3
OpenAlex ID: W2003192754
cites work: Learning regular sets from queries and counterexamples
cites work: When won't membership queries help?
cites work: Prediction-preserving reducibility
Recommended article: Q4226191
Recommended article: Complexity results for prefix grammars
Recommended article: Prefix-free regular languages and pattern matching
Recommended article: Q4964027
Recommended article: Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages
Recommended article: On the regular structure of prefix rewriting
Recommended article: Q4027621
Recommended article: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
Recommended article: Complexity of proper prefix-convex regular languages
description: scientific article; zbMATH DE number 633514