It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity point of view. In particular, we give optimal upper bounds for the number of states of nondeterministic and deterministic finite automata equivalent to unary context-free grammars in Chomsky normal form. These bounds are functions of the number of variables of the given grammars. We also give upper bounds for the number of states of finite automata simulating unary pushdown automata. As a main consequence, we are able to prove a log log n lower bound for the workspace used by one-way auxiliary pushdown automata in order to accept nonregular unary languages. The notion of space we consider is the so-called weak space concept.

Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds / G. Pighizzini, J. Shallit, M.W. Wang. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 65:2(2003), pp. 393-414. [10.1006/jcss.2002.1855]

Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds

G. Pighizzini
Primo
;
2003

Abstract

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity point of view. In particular, we give optimal upper bounds for the number of states of nondeterministic and deterministic finite automata equivalent to unary context-free grammars in Chomsky normal form. These bounds are functions of the number of variables of the given grammars. We also give upper bounds for the number of states of finite automata simulating unary pushdown automata. As a main consequence, we are able to prove a log log n lower bound for the workspace used by one-way auxiliary pushdown automata in order to accept nonregular unary languages. The notion of space we consider is the so-called weak space concept.
formal languages ; context-free grammars ; pushdown automata ; descriptional complexity ; space complexity
Settore INF/01 - Informatica
2003
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/35131
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 30
social impact