On regularity of context-free languages. (English) Zbl 0553.68044

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.


68Q45 Formal languages and automata


Zbl 0495.68068
Full Text: DOI


[1] Adan, S., Defining relations and algorithmic problems for groups and semigroups, Proc. Stekloe Institute Math., 85 (1966), (English version published by American Math. Soc., 1967). · Zbl 0204.01702
[2] Autebert, J. M.; Beauquier, J.; Boasson, L.; Latteux, M., Very small families of algebraic nonrational languages, (Book, R., Formal Language Theory (1981), Academic Press: Academic Press London-New York)
[3] Autebert, J. M.; Beauquier, J.; Boasson, L.; Nivat, M., Quelques problèmes ouverts en théorie des languages algebraiques, RAIRO Informatique Theorique, 13, 363-379 (1979) · Zbl 0434.68056
[4] Book, R.; Jantzen, M.; Wrathall, C., Monadic Thue systems, Theoret. Comput. Sci., 19, 231-251 (1982) · Zbl 0488.03020
[5] Chomsky, N.; Schutzenberger, M., The algebraic theory of context-free languages, (Braffort; Hirshberg, Computer Programming and Formal Systems (1963), North-Holland: North-Holland Amsterdam), 118-161 · Zbl 0148.00804
[6] Cochet, Y., Church-Rosser congruences on free semigroups, Colloq. Math. Soc. Janos Bolyai: Algebraic theory of semigroups, 20, 51-60 (1976) · Zbl 0408.20054
[7] Cochet, Y.; Nivat, M., Une généralisation des ensembles de Dyek, Israel J. Math., 9, 389-395 (1971) · Zbl 0215.56005
[8] Conway, J. H., Regular Algebra and Finite Machines, ((1971), Chapman & Hall: Chapman & Hall London), 63-64 · Zbl 0231.94041
[9] Ehrenfeucht, A.; Rozenberg, G., On basic properties of DOS systems, Inform. and Control, 47, 137-153 (1980) · Zbl 0469.68076
[10] Ehrenfeucht, A.; Rozenberg, G.; Haussler, D., Conditions enforcing regularity of context-free languages, (Lecture Notes in Computer Science (1982), Springer: Springer Berlin) · Zbl 0495.68068
[11] Erdös, P.; Rado, R., Sets having the divisor property, solution to problem 4358, Amer. Math. Monthly, 59, 255-257 (1952)
[12] Greibach, S.; Hoperoft, J., Scattered context grammars, J. Comput. Systems Sci., 3, 3, 233-247 (1969) · Zbl 0174.02801
[13] Hains, L. H., On free monoids partially ordered by embedding, J. Combin. Theory, 6, 94-98 (1969) · Zbl 0224.20065
[14] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[15] D. Haussler, Insertion languages, Inform. Sci.; D. Haussler, Insertion languages, Inform. Sci. · Zbl 0544.68049
[16] Higman, G., Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 3, 2, 326-336 (1952) · Zbl 0047.03402
[17] Kruskal, J. B., The theory of well-quasi ordering: A frequently discovered concept, J. Combin. Theory (Ser. A), 13, 97-305 (1972) · Zbl 0244.06002
[18] Latteux, M., Cônes rationnelles commutatifs, J. Comput. and Systems Sci., 18, 307-333 (1979) · Zbl 0421.68074
[19] Laver, R., Well-quasi orderings of sets of finite sequences, Math. Proc. Cambridge Philos. Soc., 79, 1-10 (1976) · Zbl 0405.06001
[20] Myhill, J., Finite automata and the representation of events, Wright Air Development Command Tech. Rept. 57-624, 112-137 (1957)
[21] Nash-Williams, C. St. J.A., On well-quasi ordering finite trees, Proc. Cambridge Phil. Soc., 59, 833-835 (1963) · Zbl 0122.25001
[22] Nerode, A., Linear automaton transformations, Proc. Amer. Math. Soc., 9, 541-544 (1958) · Zbl 0089.33403
[23] Post, E. L., Recursive unsolvability of a problem of Thue, J. Symb. Logic, 12, 1-11 (1947) · Zbl 1263.03030
[24] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[25] Thue, A., Probleme über veranderungen von zeichnenreihen nach gegebenen regeln, Skr. Vidensk. Selsk., 1, 10 (1914) · JFM 45.0333.19
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.