Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Bedregal B.R.C.

Fundamenta Informaticae

2007

Vol. 81, nr 4

367-377

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 l-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 context-free language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages.