Publication Details
Pushdown Automata: Another Extensions and Transformations
pushdown automata, regulated pushdown automata, scattered context grammars,
syntax analysis
Pushdown automata play a key role in the efficient syntax analysis of
context-free languages. The great advantage is also
that the construction of the pushdown automata for the particular language
described by a proper grammar is straightforward. On the other hand, the
efficiency of automata constructed for, for instance, LL(2) languages is not as
good as for LL(1) languages. Moreover, we cannot use pushdown automata for
analysis of context-sensitive languages and thus their power is far below the one
of Turing machine.
This thesis demonstrates a transformation of pushdown automata to achieve
efficient behaviour even for LL(k), k>1, languages. After these introductory
pages, an extension of pushdown automata, which increases
their power to the one of Turing machine is presented. We
propose an extended pushdown automaton together with an algorithm of its
construction, which can be used for the efficient analysis of languages, a power
of which is higher than that for context-free languages.
@misc{BUT192575,
author="Dušan {Kolář}",
title="Pushdown Automata: Another Extensions and Transformations",
year="2005",
pages="76",
publisher="Faculty of Information Technology BUT",
address="Brno",
url="https://www.fit.vut.cz/research/publication/7816/",
note="habilitation thesis"
}