TIN 12. Vlastnosti formálních jazyků

Card Set Information

Author:
hrbi
ID:
222566
Filename:
TIN 12. Vlastnosti formálních jazyků
Updated:
2013-06-06 09:19:43
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Strukturální vlastnosti RJ
    • každý konečný jazyk je regulární
    • Pumping lemma pro RJ
    • Myhill-Nerodova věta
  2. Pumping lemma pro RJ
    • L ∈ L3
    • ∃p > 0:
    • ∀w ∈ L, |w| ≥ p:
    • w = xyz ∧ 0 < |y| ∧ |xy| ≤ p ∧ xyiz ∈ L, i ≥ 0
    • používá se k důkazu, že daný jazyk není RJ
  3. Myhill-Nerodova věta
    • prefixová ekvivalence: u ~L v ⇔ ∀w ∈ Σ*: uw ∈ L ⇒ vw ∈ L
    • index ekvivalence ~L: počet tříd rozkladu Σ*/~L
    • MH věta: počet stavů minimálního DKA přijímajícího L je roven indexu ~L
  4. Uzávěrové vlastnosti RJ
    • třída RJ je uzavřena vůči: ∪, ∩, ·, *, ', R, substituce, morfismus, inv. morfismus
    • třída RJ tvoří Booleovu algebru (L3, ∪, ∩, ', Σ*, Ø)
  5. Rozhodnutelné problémy RJ
    • neprázdnost L ≠ Ø
    • náležitost w ∈ L
    • ekvivalence L(G1) = L(G2)
    • konečnost jazyka
  6. Pumping lemma pro BKJ
    • L ∈ L2
    • ∃p > 0:
    • ∀z ∈ L, |z| ≥ p:
    • z = uvwxy ∧ vx ≠ ε ∧ |vwx| ≤ p ∧ uviwxiy ∈ L, i ≥ 0
    • používá se k důkazu, že daný jazyk není BKJ
  7. Substituce jazyků
    • Σ = {a1, ..., an} abeceda
    • L ⊆ Σ*
    • pro každý symbol ai ∈ Σ mám jazyk Lai
    • 1. vezmu všechny řetězce z L
    • 2. pro každý řetězec vytvořím nové řetězce nahrazením znaku ai všemi možnými řetězci z Lai
    • je to dobré k ukázání uzávěrových vlastností
  8. Morfismus jazyků
    • zvláštní případ substituce, kdy každý substituovaný jazyk má pouze jeden řetězec
    • morfismus nad slovy - zobrazení h: Σ* → Δ*
    • ∀w = a1a2...an ∈ Σ*: h(w) = h(a1)h(a2)...h(an)
    • morfismus jazyka h(L) = {h(w) | w ∈ L}
  9. Inverzní morfismus jazyků
    • h: Σ* → Δ* morfismus
    • h-1: Δ* → Σ* inverzní morfismus nad slovy
    • h-1(w) = {x ∈ Σ* | h(x) = w}
    • inverzní morfismus jazyků h-1(L) = {x ∈ Σ* | h(x) ∈ L}
  10. Uzávěrové vlastnosti BKJ
    • třída BKJ je uzavřena vůči: ∪, ·, *, R, substituce, morfismus, inv. morfismus
    • třída BKJ není uzavřena vůči: ∩, '
    • navíc: ∩ s RJ,
  11. Neuzavřenost BKJ vůči průniku
    • L1 = {ambmcn}
    • L2 = {anbmcm}
    • L1 ∩ L2 = {ambmcm}
  12. Neuzavřenost BKJ vůči doplňku
    z De Morganových z. plyne uzavřenost vůči průniku → spor
  13. Rozhodnutelné problémy BKJ
    • neprázdnost L ≠ Ø
    • náležitost w ∈ L
  14. Nerozhodnutelné problémy BKJ
    • ekvivalence L(G1) = L(G2)
    • inkluze L(G1) ⊆ L(G2)
    • univerzalita L(G) =? Σ*
    • jazyk nějakého DZA
  15. Uzávěrové vlastnosti DBKJ
    • třída DBKJ je uzavřena vůči: průniku s RJ, doplňku
    • třída DBKJ není uzavřena vůči: průniku, sjednocení, konkatenaci, iteraci

What would you like to do?

Home > Flashcards > Print Preview