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

Tabulka uzavřenosti

Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
Operation Regular DCFL CFL IND CSL recursive RE
Union w \in L_1 \lor w \in L_2\} </math> Yes No Yes Yes Yes Yes Yes
Intersection w \in L_1 \land w \in L_2\}</math> Yes No No No Yes Yes Yes
Complement w \not\in L_1\}</math> Yes Yes No No Yes Yes No
Concatenation w \in L_1 \land z \in L_2\}</math> Yes No Yes Yes Yes Yes Yes
Kleene star w \in L_1 \land z \in L_1^{*}\}</math> Yes No Yes Yes Yes Yes Yes
Homomorphism Yes No Yes Yes No No Yes
e-free Homomorphism Yes No Yes Yes Yes Yes Yes
Substitution Yes No Yes Yes Yes No Yes
Inverse Homomorphism Yes Yes Yes Yes Yes Yes Yes
Reverse w \in L\} </math> Yes No Yes Yes Yes Yes Yes
Intersection with a regular language w \in L_1 \land w \in R\}, R \text{ regular}</math> Yes Yes Yes Yes Yes Yes Yes

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

k jazyk generuje kontextová gramatika context-sensitive grammar (CSG)

Rekurzivně spočetný jazyk

Někdy taky zvané Jazyky rekurzívně vyčíslitelné a jazyky rekurzívní

  • jazyky rekurzívně vyčíslitelné - zastaví pouze pro řětězec jazyku, který je schopen příjmout $ w \in L $
  • jazyky rekurzívní - pro úplný Turingův stroj (pro každý vstup se zastaví)

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
Osobní nástroje