Detekcia chýb pomocou susednosti a editačnej vzdialenosti vstupom riadených zásobníkových automatov
Autor: Matúš Piroh
Vedúci práce: RNDr. Zuzana Bednárová, PhD.
Konzultant: Mgr. Alexander Szabari, PhD.
Ciele práce:
- Preskúmať a popísať model vstupom riadeného zásobníkového automatu a pojem susednosti a editačnej vzdialenosti.
- Analyzovať a spracovať existujúce konštrukcie vstupom riadených zásobníkových automatov z gramatík v špeciálnych formách.
- Implementovať túto konštrukciu a použiť ju na detekciu chýb v dokumentoch (napr. XML).
- Rozšíriť zostrojený algoritmus o hľadanie editačnej vzdialenosti daného vstupu od daného jazyka určeného gramatikou.
Dokončené úlohy
- Naštudovať literatúru o input-driven automatoch
- Analyzovať konštrukcie týchto automatov
- Zostrojiť algoritmus na získanie input-driven automatu z gramatiky
- Analyzovať a navrhnúť špeciálny tvar gramatiky
Nasledujúce úlohy
- Vytvorenie jednoduchého editora pre gramatiky
- Implementácia algoritmu na získanie input-driven automatu
- Simulácia tohto programu na dokumentoch (napr. XML)
- Rozširenie programu o hľadanie chýb (editačnej vzdialenosti)
Zdroje:
- A. Okhotin, K. Salomaa: Edit Distance Neighbourhoods of Input-Driven Pushdown Automata. In: CSR 2017, LNCS 10304, pp. 260-272 (2017)
- R. Alur, P. Madhusudan: Visibly pushdown languages. In: ACM Symposium on Theory od Computing, STOC 2004, Chicago, USA 13-16 June 2004, pp. 202-211 (2004)
- J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to automata theory, languages, and computation - international edition (2. ed). Addison-Wesley (2003)