Prefix grammars: An alternative characterization of the regular languages. (English) Zbl 0813.68125

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.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Angluin, D., Learning regular sets from queries and counterexamples, Inform. and comput., 75, 87-106, (1987) · Zbl 0636.68112
[2] Angluin, D.; Kharitonov, M., When won’t membership queries help?, (), 444-454 · Zbl 0827.68039
[3] Frazier, M.; Page, C.D., Learnability of recursive, non-determinate theories: some basic results andtechniques, Proc. 3rd internat. workshop on inductive logic programming, Ljubljana, Slovenia, 103-126, (1993)
[4] Kearns, M.; Valiant, L., Cryptographic limitations on learning Boolean formulae and finite automata, (), 433-444
[5] Pitt, L.; Warmuth, M., Prediction-preserving reducibility, J. comput. system sci., 41, 430-467, (1990) · Zbl 0722.68094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.