Pushdown Automata Free of Explicit Nondeterminism and an Infinite Hierarchy of Context-free Languages

Article type: Research Article

Authors: Bedregal, Benjamín René Callejas

Affiliations: Federal University of Rio Grande do Norte, Department of Informatics and Applied Mathematics, Laboratory of Logic and Computational Intelligence, Brazil. E-mail: [email protected]

Abstract: By explicit nondeterminism degree of a pushdown automata we mean the maximal number of choices in the transitions of the automata. In this paper we will prove that each pushdown automaton has an equivalent pushdown automaton with degree 1 of explicit nondeterminism, which implies that λ-moves in pda are sufficient to simulate nondeterminism. Moreover, from this normal form (i.e. pda with degree 1 of explicit nondeterminism) we can measure the amount of (implicit) nondeterminism. This measure will be used to determine a countable infinite hierarchy of contextfree language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages.

Keywords: Pushdown automata, amount of nondeterminism, λ-moves, hierarchy, implicit and explicit nondeterminism

Journal: Fundamenta Informaticae, vol. 81, no. 4, pp. 367-377, 2007