Seminár z teoretickej informatiky - Karina Chudá (26.11.2021)
v piatok 26.11.2021 o 11:00 hod. v miestnosti M/213
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