zbMATH — the first resource for mathematics

Descriptional complexity measures of context-free languages. (English) Zbl 0535.68039
The paper defines some variants of the measure Prod, of syntactic complexity of context-free languages [J. Gruska, Inf. Control 14, 152-179 (1969; Zbl 0174.289)], namely one counts only the production rules containing at least one terminal symbol, containing only terminals (or no terminals or a terminal in the left end of the right hand member) etc. It is proved that all these measures induce infinite hierarchies without gaps on the family of context-free languages and that the decision problems usual in this frame [J. Gruska, Descriptional complexity of context-free languages, Proc. Math. Found. Comput. Sci. ’73, High Tatras, 71-83 (1973)] are undecidable for them.
Reviewer: C.Calude
68Q45 Formal languages and automata
Full Text: EuDML
[1] S. Ginsburg: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York 1966. · Zbl 0184.28401
[2] J. Gruska: Some classifications of context-free languages. Information and Control 14 (1969), 2, 152-179. · Zbl 0174.28901 · doi:10.1016/S0019-9958(69)90055-2
[3] J. Gruska: Complexity and unambiguity of context-free grammars and languages. Information and Control 18 (1971), 5, 502-519. · Zbl 0238.68022 · doi:10.1016/S0019-9958(71)90519-5
[4] J. Gruska: Descriptional complexity of context-free languages. Proceedings MFCS’ 73, High Tatras, 71-83.
[5] A. Salomaa: Formal Languages. Academic Press, New York and London 1973. · Zbl 0262.68025
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.