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... 

To stále ještě nekončí:

  • Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus. 

  • Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma. 
    Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky

  • Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty.

  • Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy

Na závěr je zde ještě pár vychytávek pro nejtvrdší drsňáky a to přímo od pana Kozena!

Důkazy, důkazy, důkazy... 



Pokud máte vypočítaný příklad, se kterým se chcete pochlubit, můžete mi ho poslat a já ho sem vložím.

Nedávno přidané dokumenty

  • konecny_automat.jpg   103 kB – 3. 11. 2017 7:01, nesporfilip (v.1)
  • konečný automat.doc   280 kB – 3. 11. 2017 6:54, nesporfilip (v.1)
  • Problem neprazdnosti jazyka 2.JPG   1082 kB – 29. 12. 2010 12:07, nesporfilip (v.1)
    ‎Důkaz, že problém neprázdnosti jazyka TS není rozhodnutelný (část 2/2)‎
  • Problem neprazdnosti jazyka 1.JPG   1136 kB – 29. 12. 2010 12:07, nesporfilip (v.1)
    ‎Důkaz, že problém neprázdnosti jazyka TS není rozhodnutelný (část 1/2)‎
  • Uzavrenost vuci substituci jazyku.JPG   1105 kB – 29. 12. 2010 12:01, nesporfilip (v.1)
    ‎Uzavřenost L0 vůči substituci jazyků‎
Zobrazuje se 5 souborů ze stránky Stahování vyřešených příkladů.