| Abstrakt: | Práca sa zaoberá algoritmami na vypočítanie vzdialeností a podobností slov a
jazykov. Venuje sa editačnej vzdialenosti, $\Delta$-podobnosti a ľubovoľnej
vzdialenosti, ktorá môže byť definovaná a-prekladačom (prekladačová
vzdialenosť). Prezentuje doteraz známe algoritmy na vypočítanie editačnej a
prekladačovej vzdialenosti dvoch regulárnych jazykov. Prináša algoritmy na
vypočítanie editačnej a prekladačovej vzdialenosti regulárneho jazyka od
bezkontextového jazyka a algoritmus na vypočítanie $\Delta$-podobnosti dvoch
regulárnych jazykov.
V práci je dokázané, že pre väčšinu tried Chomského hierarchie jazykov
neexistuje algoritmus, ktorý vypočíta vzdialenosť dvoch jazykov z danej triedy.
|
|---|