Bachelor's Thesis

Deep Pushdown Automata: Modified Version and Their Applications

Final Thesis 627.36 kB

Author of thesis: Bc. Šimon Motl

Acad. year: 2025/2026

Supervisor: prof. RNDr. Alexandr Meduna, CSc.

Reviewer: Ing. Martin Havel

Abstract:

This thesis deals with the design and formal investigation of novel variants of deep pushdown automata, specifically partially parallel deep pushdown automata. The primary objective is to define these models and explore their properties, with a particular focus on compilers. The theoretical framework thus includes the introduction of a deterministic version of the automaton, which utilizes a lookahead mechanism to ensure computational unambiguity. To verify the theoretical concepts and demonstrate the functionality of the proposed models, a software simulator was developed in the Python programming language. This tool enables the design of automata, step-by-step execution of their computations, and experimental validation, thereby bridging the gap between theory and practice.

Keywords:

formal languages, deep pushdown automaton, partially parallel expansion, determinism, lookahead, syntactic analysis, simulator, Python

Date of defence

15.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaDznamka

Grading

D

Process of defence

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm D.

Topics for thesis defence

  1. V implementaci se odchylujete od teoretického modelu použitím tuple. Navrhněte řešení bližší teoretickému modelu.
  2. Můžete se vyjádřit k výtce oponenta k správnosti důkazů?
  3. Jaká je vyjadrovací síla hlubokých zasobníkových automatů?

Language of thesis

Czech

Faculty

Fakulta informačních technologií

Department

Department of Information Systems

Study programme

Information Technology (BIT)

Composition of Committee

doc. RNDr. Milan Češka, Ph.D. (předseda)
doc. Ing. Jan Kořenek, Ph.D. (místopředseda)
Ing. Zdeněk Materna, Ph.D. (člen)
Ing. Miloš Musil, Ph.D. (člen)
Ing. Martin Hrubý, Ph.D. (člen)

Supervisor’s report
prof. RNDr. Alexandr Meduna, CSc.

Vedoucí zdůvodňuje hodnocení C takto: student získával poznatky ze studijních materiálů průměrným způsobem. Jeho komunikace s vedoucím byla průměrná a nedávala vedoucímu možnost řídit vývoj práce vyčerpávajícím způsobem. Jeho přístup k řešení byl poněkud nesystematický. Je třeba ale uznat, že téma práce je velmi originální a student se jej svým způsobem snažil řešit, což je třeba ocenit. Tato snaha vede vedoucího k hodnocení C/78.

Evaluation criteria Verbal classification
Information about assignment

Tato práce byla vypracována dle uvedeného tématu a postupu. Byla běžně náročná, ale vyžadovala studium cizojazyčné literatury a zavést zcela nové koncepty. Práce překročila zadání mírně.
Work with literature

Při získávání a využívání studijních materiálů k řešení práce byl student běžně aktivní.
Activity during solution, consultations, communication

Student se mnou komunikoval pravidelně osobně i elektronicky.  Pracoval běžným způsobem.
Activity during completion

Práce byla dokončena v mírném předstihu a její finální obsah byl konzultován hrubě.
Publication activity, awards

Není. 
Points proposed by supervisor: 78

Grade proposed by supervisor: C

Reviewer’s report
Ing. Martin Havel

Práce je dobrá jak v textové, tak v implementační části. Z důvodu vyšší obtížnosti zadaní navrhuji hodnocení velmi dobře (B).

Evaluation criteria Verbal classification Points
The difficulty of the assignment

Evaluation level: more difficult assignment

Obtížnost zadání spočívala v nutnosti pochopení pokročilých modelů formálních jazyků, které jsou běžně probírány až v rámci doktorského studia.
Presentation level of the technical report

Logická struktura práce i návaznost kapitol jsou v pořádku. Výtku mám k obrázku 2.1, ve kterém chybí některé zavedené notace. Dále některé důkazy nepovažuji za dostatečně formální ani dostatečně rigorózní.

 80
Formal preparation of a technical report

Po jazykové i typografické stránce je práce v pořádku.

 95
Realisation output

Implementace realizačního výstupu má dobrou kvalitu a kód je řádně komentovaný. Implementace obsahuje několik neefektivních rozhodnutí pro demonstraci.

 70
Usability of results

Práce je výzkumného charakteru. Její využitelnost v praxi nelze určit.
The extent to which the requirements of the assignment have been met

Evaluation level: assignment fulfilled

Zadání splněno ve všech bodech.
Extent of the technical report

Evaluation level: is within the usual extent

Rozsah práce je v obvyklém rozmezí.
Work with literature

Práce obsahuje 23 zdrojů. Zdroje jsou vhodně zvolené a většinou konzistentně vhodně použité.

 75
Topics for thesis defence:
  1. V implementaci se odchylujete od teoretického modelu použitím tuple. Navrhněte řešení bližší teoretickému modelu.
Points proposed by reviewer: 80

Grade proposed by reviewer: B

Responsibility: Mgr. et Mgr. Hana Odstrčilová