Detail předmětu

Regulované gramatiky a automaty

FIT-RGDAk. rok: 2020/2021

Předmět diskutuje regulované přepisování jako jedno z ústředních témat teoretické informatiky posledních let. Zaměřuje se na nejmodernější výzkum v oblasti regulovaných gramatik a automatů včetně jejich praktického využití. Získání a porozumění prezentovaných poznatků je ověřeno zpracováním vlastní tvůrčí tématické práce studenta.

Okruhy otázek k SDZ

  • Regulované automaty a gramatiky: základní idea.
  • Gramatiky s regulovaným užitím pravidel.
  • Kontextově založené regulované gramatiky.
  • Gramatiky s algebraicky založenou regulací.
  • Redukce regulovaných gramatik.
  • Paralelní verze regulovaných gramatik.
  • Regulované konečné automaty.
  • Regulované zásobníkové automaty.
  • Hluboké zásobníkové automaty.
  • Skákající automaty.
  • Výsledky učení předmětu

    Podrobný přehled o poznatcích současné teoretické informatice v oblasti regulovaného přepisování a schopnost je využít ve vlastním výzkumu.

    Prerekvizity

    formalni jazyky

    Doporučená nebo povinná literatura

    copies of lectures
    kopie přednášek (EN)
    ROZENBERG Grzegorz and SALOMAA Arto. Handbook of Formal Languages (https://www.springer.com/gp/book/9783642638633), Volumes 1-3. Springer, 1997
    ROZENBERG Grzegorz a SALOMAA Arto. Handbook of Formal Languages (https://www.springer.com/gp/book/9783642638633), Volumes 1-3. Springer, 1997 (EN)
    MEDUNA Alexander a ZEMEK Petr. Regulated Grammars and Automata (http://www.fit.vutbr.cz/~meduna/pubs.php?id=10498). New York: Springer US, 2014. ISBN 978-1-4939-0368-9 (EN)
    MEDUNA Alexander and ZEMEK Petr. Regulated Grammars and Automata (http://www.fit.vutbr.cz/~meduna/pubs.php.en?id=10498). New York: Springer US, 2014. ISBN 978-1-4939-0368-9
    MEDUNA Alexander and SOUKUP Ondřej. Modern Language Models and Computation: Theory with Applications (https://www.fit.vut.cz/research/publication/11483/.en). New York: Springer US, 2017. ISBN 978-3-319-63099-1
    MEDUNA Alexander a SOUKUP Ondřej. Modern Language Models and Computation: Theory with Applications (https://www.fit.vut.cz/research/publication/11483/). New York: Springer US, 2017. ISBN 978-3-319-63099-1 (EN)
    mnoho nejnovějších článků, vědeckých zpráv a knih (EN)
    many very recent papers, scientific reports, and books

    Jazyk výuky

    čeština, angličtina

    Cíl

    Předat studentům podrobný přehled modelů a výsledků týkajících se regulovaného přepisování v rámci teoretické informatiky. Zdokonalit a utvrdit schopnost tvůrčím způsobem
    využívat získaných poznatků z moderní teoretické informatiky ve vlastním
    výzkumu.

    Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

    1. Vypracování dvou referátů během semestru:

    • Každý celkem 20 bodů, z toho 15 písemná část a 5 ústní část (prezentace).
    • Téma referátů musí být vztaženo k látce předmětu a schváleno garantem předmětu (prof. Meduna).
    • Po prezentaci bude možno stávající verzi referátu vylepšit a znovu odevzdat. Tato verze pak bude hodnocena.

    2. Ústní zkouška se skládá ze dvou otázek, každá za 30 bodů.

    Zařazení předmětu ve studijních plánech

    • Program VTI-DR-4 doktorský

      obor DVI4 , libovolný ročník, zimní semestr, 0 kreditů, volitelný

    • Program VTI-DR-4 doktorský

      obor DVI4 , libovolný ročník, zimní semestr, 0 kreditů, volitelný

    Typ (způsob) výuky

     

    Přednáška

    39 hod., nepovinná

    Vyučující / Lektor

    Osnova

    1. Regulované formální modely: úvod a principy.
    2. Regulace gramatik založená na kontextu a na pravidlech.
    3. Regulované gramatiky: transformace, normální formy, vymazávání, omezené derivace.
    4. Rozšíření jazyků generovaných regulovanými gramatikami.
    5. Regulace gramatik založená na algebraických omezeních.
    6. Částečně a úplně paralelní regulované gramatiky.
    7. Regulované gramatické systémy.
    8. Multigenerativní gramatické systémy.
    9. Regulované automaty: principy.
    10. Automaty regulované řídicím jazykem.
    11. Skákající konečné automaty.
    12. Hluboké zásobníkové automaty.
    13. Aplikační perspektivy; shrnutí.

    Konzultace v kombinovaném studiu

    26 hod., nepovinná

    Vyučující / Lektor

    Projekt

    13 hod., povinná

    Vyučující / Lektor

    Osnova

    Dvě tematická práce o regulovaném přepisování.

    eLearning