Úvod

Vítejte na našech stránkách zabývající se tématikou teoretické informatiky

Najde zde hlavně ukázky a příklady z oblastí:

Úvod, aplikace teorie formálních jazyků, modelovací a rozhodovací síla formálního modelu, operace nad jazyky. Regulární jazyky a jejich vlastnosti, Kleenova věta, Nerodova věta, věta o vkládání (Pumping theorem). Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu. Uzávěrové vlastnosti regulárních jazyků, regulární jazyky jako množinová Booleova algebra, rozhodnutelné problémy regulárních jazyků. Bezkontextové jazyky a jejich vlastnosti. Normální tvary bezkontextových gramatik, jednoznačné a deterministické bezkontextové jazyky, věta o vkládání pro bezkontextové jazyky. Uzávěrové vlastnosti bezkontextových jazyků, uzavřenost vzhledem k substituci, důsledky, rozhodnutelné problémy bezkontextových jazyků. Turingovy stroje (TS), definice TS a jazyka přijímaného TS, rekurzivně vyčíslitelné a rekurzivní jazyky a problémy, TS a funkce, metody konstrukce TS. Modifikace TS, TS s obousměrně nekonečnou páskou, s více páskami, nedeterministický TS, stroj se dvěma zásobníky, stroje s čitači. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů. Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém. Nerozhodnutelné problémy teorie formálních jazyků. Úvod do výpočetní složitosti, Turingovská složitost, třída P a NP problémů.

Dále zde najde i řešené příklady a ukázky z:

Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty. Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost. Bezkontextové gramatiky a jazyky: transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám: nedeterministická syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové automaty.

a mnoho dalšího...