The family of languages satisfying Bar-Hillel’s lemma. (English) Zbl 0387.68053


68Q45 Formal languages and automata
Full Text: EuDML


[1] 1. Y. BAR-HILLEL, M. PERLES and E. SHAMIR, On Formal Properties of Simple Phrase Structure Grammars, Zeitschr. Phonetik, Sprachwiss., Kommunikationsforsch., Vol. 14, 1961, p. 143-172. Zbl0106.34501 MR151376 · Zbl 0106.34501
[2] 2. S. GINSBURG, The Mathematical Theory of Context-free Languages, McGraw-Hill, New York, 1966. Zbl0184.28401 MR211815 · Zbl 0184.28401
[3] 3. J. E. HOPCROFT and J. D. ULLMAN, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. Zbl0196.01701 MR237243 · Zbl 0196.01701
[4] 4. D. F. MARTIN, Formal Languages and their Related Automata, in Computer Science, A. F. CARDENAS, L. PRESSER and M. MARIN, eds., Wiley-Interscience, New York, London, 1972, p. 409-460.
[5] 5. A. SALOMAA, Formal Languages, Academic Press, New York, London, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
[6] 6. S. GINSBURG and S. GREIBACH, Abstract Families of Languages, Mem. Amer. Math. Soc., Vol. 87, 1969, p. 1-32. Zbl0194.31402 MR297491 · Zbl 0194.31402
[7] 7. W. S. BRAINERD and L. H. LANDWEBER, Theory of Computation, Wiley-Interscience, New York, London, 1974. Zbl0274.68001 MR400760 · Zbl 0274.68001
[8] 8. S. HORVÁTH, BHFL: the Family of Languages Satisfying Bar-Hillel’s Lemma, 2nd Hungarian Computer Science Conf., Budapest, June 27-July 2, preprints, Vol. I, p. 479-483.
[9] 9. C. CĨSLARU and G. PĂUN, Classes of Languages with the Bar-Hillel, Perles and Shamir’s Property, Bull. Math. Soc. Sc. Math. R. S. Roum., Bucharest, Vol. 18, No. 3-4, 1974 (received: July, 1975; appeared: 1976) p. 273-278. Zbl0328.68070 MR421160 · Zbl 0328.68070
[10] 10. V. COARDOS, O clasă de limbaje neidependente de context care verifică conditia lui Bar-Hillel, Stud. cerc. mat., Bucharest, Vol. 27, No. 4, 1975, p. 407-411. Zbl0324.68047 MR483740 · Zbl 0324.68047
[11] 11. G. PĂUN, Asupra proprietătii lui Bar-Hillel, Perles si Shamir, Stud. cerc. mat., Bucharest, Vol. 28, No. 3, 1976, p. 303-309. Zbl0337.68052 MR443456 · Zbl 0337.68052
[12] 12. T. KLØVE, Pumping languages, Internat. J. Comp. Math., R. RUSTIN, éd., Gordon and Breach Sc. Publishers, London, New York, Paris; Vol. 6, No. 2, 1977, p. 115-125. Zbl0358.68123 MR468348 · Zbl 0358.68123
[13] 13. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity, Math. Syst. Theory, Vol. 2, No. 3, 1968, p. 191-194. Zbl0175.27802 MR233645 · Zbl 0175.27802
[14] 14. A. V. AHO and J. D. ULLMAN, The Theory of Parsing, Translation, and Compiling, Vol. I, ”Parsing”, Prentice-Hall, 1971, 2nd printing: 1972, section 2.6. MR408321 · Zbl 0217.53803
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.