future: Testing of CFG, PDA, LBA, GRA-1
V budoucnu (v některé z dalších prací) bychom chtěli mít možnost testovat i některé nerozhodnutelné příklady:
- konstrukce bezkontextových gramatik a PDA/DPDA
- konstrukce gramatik typu 1 (kontextových) a lineárně ohraničených turingových strojů (LBA)
V těchto případech bychom chtěli mít možnost ověřovat úkoly dvojfázově:
- automatické testy (přes odpovědníky?) dělají základní ověření -- snaží se najít protipříklady, testují náhodně či slovy nějaké omezené délky
- pokud projdou, následuje manuální kontrola opravujícím
obsahem práce jsou následující:
- formalismy pro popis gramatik typu 1 (na základně formalismů pro popis regulárních a bezkontextových gramatik)
- formalismy pro popis (D)PDA a LBA
- algoritmy pro ověřování příslušnosti slova do jazyka dané gramatiky/automatu
- napojení na evaluátor
- evaluace proti jazyku popsanému orákulem (tj. predikátem např. v Pythonu)
Zdroje
- random words from CFGs: https://ir.canterbury.ac.nz/bitstream/handle/10092/11231/tr_9710.pdf?sequence=1&isAllowed=y
- CFG comparison: https://dl.acm.org/doi/abs/10.1145/2814270.2814304
- PDA vs CFG: https://core.ac.uk/download/pdf/82151663.pdf
Edited by Vladimír Štill