Seminár Ústavu informatiky

Prednáška

Dvojhlavé konečnostavové automatov a lineárne gramatiky

Mgr. Alexander Szabari, PhD.
Ústav informatiky, PF UPJŠ

24. mája 2017 (streda) o 12:45
SJ2S07 (3.16T), PF UPJŠ

Abstrakt

Dvojhlavé konečnostavové automaty sú omnoho silnejšie ako jednohlavé, dokážu rozpoznať aj jeden z kontextových jazykov. Na druhej strane lineárne jazyky sú podmnožinou bezkontextových jazykov. Sú dvojhlavé automaty až také silné že rozpoznajú lineárne jazyky ?