Non-Self-Embedding Grammars and Descriptional Complexity

• Autorzy: Pighizzini Giovanni , Prigioniero Luca

Identyfikatory

DOI

10.3233/FI-2021-2036

• Języki publikacji: EN

Abstrakty

EN

Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s.

Słowa kluczowe

EN

context-free grammars; descriptional complexity; bounded languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 103--122
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Pighizzini Giovanni

• Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy

autor

Prigioniero Luca

• Dipartimento di Informatica, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy

Bibliografia

• [1] Aho AV, Lam MS, Sethi R, Ullman JD. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006. ISBN: 0321486811.
• [2] Chomsky N. On Certain Formal Properties of Grammars. Information and Control, 1959. 2(2):137-167. doi:10.1016/S0019-9958(59)90362-6.
• [3] Chomsky N. A Note on Phrase Structure Grammars. Information and Control, 1959. 2(4):393-395. doi:10.1016/S0019-9958(59)80017-6.
• [4] Anselmo M, Giammarresi D, Varricchio S. Finite Automata and Non-self-Embedding Grammars. In: Champarnaud J, Maurel D (eds.), Implementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers, volume 2608 of Lecture Notes in Computer Science. Springer 2002 pp. 47-56. ISBN: 3-540-40391-4. doi:10.1007/3-540-44977-9_4.
• [5] Meyer AR, Fischer MJ. Economy of Description by Automata, Grammars, and Formal Systems. In: 12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971. IEEE Computer Society, 1971 pp. 188-191. doi:10.1109/SWAT.1971.11.
• [6] Pighizzini G, Shallit J, Wang M. Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. J. Comput. Syst. Sci., 2002. 65(2):393-414. doi:10.1006/jcss.2002.1855.
• [7] Ginsburg S, Rice HG. Two Families of Languages Related to ALGOL. J. ACM, 1962. 9(3):350-371. doi:10.1145/321127.321132.
• [8] Andrei S, Cavadini SV, Chin W. A New Algorithm for Regularizing One-Letter Context-Free Grammars. Theor. Comput. Sci., 2003. 306(1-3):113-122. doi:10.1016/S0304-3975(03)00215-9.
• [9] Kelemenová A. Complexity of Normal Form Grammars. Theor. Comput. Sci., 1984. 28:299-314. doi:10.1016/0304-3975(83)90026-9.
• [10] Harrison MA. Introduction to Formal Language Theory. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1978. ISBN: 0201029553.
• [11] Herrmann A, Kutrib M, Malcher A, Wendlandt M. Descriptional Complexity of Bounded Regular Languages. Journal of Automata, Languages and Combinatorics, 2017. 22(1-3):93-121. doi:10.25596/jalc-2017-093.
• [12] Chrobak M. Finite Automata and Unary Languages. Theor. Comput. Sci., 1986. 47(3):149-158. doi:10.1016/ 0304-3975(86)90142-8.
• [13] Geffert V. Magic Numbers in the State Hierarchy of Finite Automata. Inf. Comput., 2007. 205(11):1652-1670. doi:10.1016/j.ic.2007.07.001.
• [14] Pighizzini G. Investigations on Automata and Languages Over a Unary Alphabet. Int. J. Found. Comput. Sci., 2015. 26(7):827-850. doi:10.1142/S012905411540002X.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).