TIN

Z Varhoo
Přejít na: navigace, hledání

Obsah

Regulární jazyky

Uzávěrové vlastnosti regulárních jazyků:

  • Sjednocení
  • Průnik
  • Konkatenace
  • Komplement
  • Substituce
  • Morfismus
  • Iterace
  • Pozitivní iterace
  • Rozdíl
  • Zrcadlení

Rozhodnutelné problémy:

  • Příslušnost jazyka
  • Prázdnost
  • Ekvivalence
  • Inkluze
  • Universita
  • Konečnost

Bezkontextové jazyky

a k jazyku patřičná gramatika: context-free grammar (CFG)

Uzávěrové vlastnosti bezkontextové jazyky

  • Sjednocení
  • Konkatenace
  • Substituce
  • Morfismus
  • Iteraci
  • Pozitivní iteraci
  • Zrcadlení

Kontextové jazyky

Rekurzivně spočetný

Jazyky mimo typ 0

Mezi tyto jazyky patří například co-HP, co-MP

  • Problém zastavení (halt problem)
  • Problém náležitosti (membership problem)
  • Postův korespondenční problém
  • SAT problem
Citováno z „http://wiki.varhoo.cz/index.php?title=TIN&oldid=2540“
Osobní nástroje