Publication detail

Pushdown Automata: Another Extensions and Transformations

KOLÁŘ, D.

Original Title

Pushdown Automata: Another Extensions and Transformations

Type

habilitation thesis

Language

English

Original Abstract

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.

Keywords

pushdown automata, regulated pushdown automata, scattered context grammars, syntax analysis

Authors

KOLÁŘ, D.

Released

11. 7. 2005

Publisher

Faculty of Information Technology BUT

Location

Brno

Pages count

76

URL

https://www.fit.vut.cz/research/publication/7816/

BibTex

@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"
}

Documents

habilitace_Kolar.pdf