|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 6 van 7 gevonden artikelen
| Titel: |
Pushdown Automata Free of Explicit Nondeterminism and an Infinite Hierarchy of Context-free Languages |
| Auteur: |
Bedregal, Benjamín René Callejas |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 81 (2008) nr. 4 pagina's 367-377 |
| Jaar: |
2008-01-07 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 6 van 7 gevonden artikelen
| << vorige | volgende >> |