Detail publikačního výsledku

Pushdown Automata: Another Extensions and Transformations

KOLÁŘ, D.

Originální název

Pushdown Automata: Another Extensions and Transformations

Anglický název

Pushdown Automata: Another Extensions and Transformations

Druh

Habilitační práce

Originální abstrakt

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) languagesis not as good as for LL(1) languages. Moreover, we cannot use pushdownautomata for analysis of context-sensitive languages and thus theirpower is far below the one of Turing machine.
This thesis demonstrates a transformation of pushdown automata toachieve efficient behaviour even for LL(k), k>1, languages. Afterthese introductory pages, an extension of pushdown automata, whichincreases
their power to the one of Turing machine is presented. We
propose an extended pushdown automaton together with an algorithm ofits construction, which can be used for the efficient analysis oflanguages, a power of which is higher than that for context-freelanguages.

Anglický abstrakt

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) languagesis not as good as for LL(1) languages. Moreover, we cannot use pushdownautomata for analysis of context-sensitive languages and thus theirpower is far below the one of Turing machine.
This thesis demonstrates a transformation of pushdown automata toachieve efficient behaviour even for LL(k), k>1, languages. Afterthese introductory pages, an extension of pushdown automata, whichincreases
their power to the one of Turing machine is presented. We
propose an extended pushdown automaton together with an algorithm ofits construction, which can be used for the efficient analysis oflanguages, a power of which is higher than that for context-freelanguages.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

KOLÁŘ, D.

Vydáno

11.07.2005

Nakladatel

Faculty of Information Technology BUT

Místo

Brno

Strany počet

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

Dokumenty

habilitace_Kolar