On some constructions of grammars for linear languages. (English) Zbl 0598.68051
This paper explains generalized linear grammars, that is, infinitely many linear productions are allowed. The author then demonstrates that for restricted versions of these grammars (and languages), it is possible to give general constructions that given a language produce a grammar that generates it. These results are, therefore, a contribution to the theory of grammatical inference.
Reviewer: D.Wood
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
linearly grammatizable languages; syntactic categories; generalized linear grammars; linear productions; grammatical inferenceReferences:
| [1] | Chomsky N., IRE-Transactions on Information Theory 2 (3) pp 113– (1956) · Zbl 0156.25401 · doi:10.1109/TIT.1956.1056813 |
| [2] | Chomsky N., Information and Control 2 (3) pp 137– (1959) · Zbl 0088.10801 · doi:10.1016/S0019-9958(59)90362-6 |
| [3] | Chomsky N., Handbook of Mathematical Psychology (1963) · Zbl 0156.25303 |
| [4] | Dobrušin R.L., Bjulletenn Ob’edinenija po problemam masinnogo perevoda 5 pp 19– (1957) |
| [5] | Gonsales R.C., Syntactic Pattern Recognition: An Introduction (1978) |
| [6] | Hopcroft J.E., Formal Languages and Their Relation to Automata (1969) · Zbl 0196.01701 |
| [7] | Kříž B., Zobecnènè gramatické kategorie (Generalized grammatical categories) (1980) |
| [8] | Kříž B., Archivum Mathematicum Brno 17 pp 151– (1981) |
| [9] | Kunze J., Kommunikat 20 pp 415– (1967) |
| [10] | Marcus S., Rev. Math. Pures et Appl 7 (1968) pp 91– (1962) |
| [11] | Marcus S., Z. Phonetik Sprachwiss. Kommunikat 18 (1968) pp 301– (1965) |
| [12] | Marcus S., Algebraic Linguistics; Analytical Models (1967) · Zbl 0174.02402 |
| [13] | Marcus S., Rev. Roum. Math. Pures et Appl 14 pp 1525– (1969) |
| [14] | Nasu M., Information and Control 15 pp 250– (1969) · Zbl 0188.03501 · doi:10.1016/S0019-9958(69)90449-5 |
| [15] | Novotný, P. 1973. Constructions of grammars for formal languages. Proceedings of Symposium and Summer School. September3-81973, High Tatras. pp.125–133. |
| [16] | Novotný M., Prague Studies in Math. Linguistics 7 pp 151– (1981) · doi:10.1075/llsee.9.12nov |
| [17] | Novotný M., Czech. Math. J 32 (107) pp 529– (1982) |
| [18] | Novotný M., Prague Studies in Math. Linguistics 8 pp 123– (1983) · Zbl 0546.68058 · doi:10.1075/llsee.17.13nov |
| [19] | Novotný M., Submitted to Prague Studies in Math. Linguistics 9 (1984) · Zbl 0188.03101 |
| [20] | Ostravský J. Effective construction of grammars for languages of two particular classes Submitted to Fundamenta Informaticae 1984 |
| [21] | Paun G., Gramatici contextuale (Contextual grammars) (1982) |
| [22] | Paz A., Introduction to Probabilistic Automata (1971) |
| [23] | Revzin V. I., Modeli jazyka. Izd. (1962) |
| [24] | Revzin V.I., Metod modelirovanija i tipologija slavjanskich jazykov (1967) |
| [25] | Salomaa A., Formal Languages (1973) |
| [26] | Semeniuk-Polkowska M., Intern. J. Computer Math 14 pp 239– (1983) · Zbl 0542.68058 · doi:10.1080/00207168308803389 |
| [27] | Szász G., Introduction to Lattice Theory (1963) |
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.
