Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teoretickej informatiky - Karina Chudá (26.11.2021)

v piatok 26.11.2021 o 11:00 hod. v miestnosti M/213


22. 11. 2021 17.20 hod.
Od: Rastislav Královič

Prednášajúci: Karina Chudá

Názov: Užitočnosť informácie vo formalizme gramatík

Termín: 26.11.2021, 11:00 hod., M/213


Abstrakt:
Dodatočná informácia je považovaná za užitočnú, ak umožňuje zjednodušiť riešenie problému. V doterajšom výskume je problém reprezentovaný jazykom riešený automatom. Ak je o vstupnom slove známa dodatočná informácia daná automatom, môže slovo akceptovať jednoduchší automat. Mierou zložitosti je počet stavov automatu. Vo formalizme bezkontextových gramatík je riešením problému reprezentovaného jazykom gramatika. Dodatočná informácia daná gramatikou udáva, že niektoré časti výsledného slova sú už vygenerované, stačí teda vygenerovať len zvyšné časti slova jednoduchšou gramatikou. Mierou zložitosti je počet neterminálov gramatiky. Prezentujeme výsledky pre dva spôsoby kombinovania práce dvoch gramatík do výsledného slova, pre kombinovanie pomocou substitúcie a pre kombinovanie pomocou novo zavedenej operácie riadeného shuffle.

web: https://beda.dcs.fmph.uniba.sk/seminar