17 - Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost) Flashcards

1
Q

Uzavřenost vůči operacím (základní operace - subtituce, morfismus, inverzní morfismus)

A

Substituce – každý symbol věty nahradíme za některou větu substitučního jazyka pro daný symbol (substituční jazyk je stejné třídy jako jazyk) - nahrazení + konkatenace
- σ(ab) = σ(a)σ(b) = {0, 00}{1, 111, 1110} -> σ(ab) = {01, 0111, 01110, 001, 00111, 001110}

Morfismus – speciální případ substituce, kdy substituční jazyk má vždy jen jednu větu (symbol vždy nahrazujeme za jednu a tu samou větu) - je to taková jednoduchá subtituce
- ϕ(a) = 00, ϕ(b) = 01 a ϕ(c) = 10 -> ϕ(abac) = ϕ(a)ϕ(b)ϕ(a)ϕ(c) = 00010010

Inverzní morfismus – je operace opačná k morfismu - tj. každá věta jazyka je nahrazena za symbol tak aby náhrada byla inverzní k nějakému morfismu

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Uzavřenost vůči operacím (základní MNOŽINOVÉ operace - sjednocení, průnik, rozdíl, doplněk, kontaktenace, reverzace, iterace))

A

Sjednocení - jazyk obsahuje řetězce z obou jazyků: L1∪L2 = {x: x∈L1∨x∈L2}
Průnik - jsou přijímány pouze řetězce, které jsou společné pro oba jazyky L1∩L2 = {x: x∈L1∧x∈L2}
Rozdíl - L1−L2 = {x: x∈L1∧x∉L2}
Doplněk - přijímáme všechny řetězce z dané abecedy kromě těch řetězců, které patří do jazyka L: L ̅=Σ^∗−L

Konkatenace - L1L2 = {xy: x∈L1∧y∈L2} - každý s každým (zachovává pořadí)
Reverzace - reverse(L)={reverse(x):x∈L} - 01 -> 10
Iterace - všechny možný kombinace které můžou vznknout (sjednocení iterací)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Uzavřenosti jazyků vůči operacím

A

Ano -> uzavřenost pro všechny

Typ 3 - Regulární - Ano
Typ 2 - deterministické bezkontextové - Ne pro všechno kromě Doplňku, inv. morfismu a průniku s typ 3
Typ 2 - bezkontextové - Ne - Průnik, doplněk
Typ 1 - kontextové - Ano
Typ 0 - rekurzivní (vždy zastaví) - Ne - Substituce, Morfismus
Typ 0 - rekurzivně vyčíslitelné (může cyklit) - Ne - Doplněk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Rozhodnutelnost problémů v jazycích (problémy)

A

• Neprázdnost – obsahuje jazyk alespoň jeden řetezec?
• Prázdnost – jazyk neobsahuje žádný řetezec?
• Konečnost – obsahuje jazyk konečný počet řetezců?
• Náležitost řetezce do jazyka – je daný řetezec řetezcem jazyka?
○ U rekurzivně vyčístelného jazyka může TS cyklit pokud tam řetězec nenáleží.
• Inkluze – je jazyk generovaný jednou gramatikou podmnožinou jazyku generovaného druhou gramatikou?
• Ekvivalence gramatik – generují dvě gramatiky stejné jazyky?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Rozhodnutelnost jazyků

A

Typ 3 - Regulární - Ano - vše
Typ 2 - deterministické bezkontextové - Ne - Inkluze
Typ 2 - bezkontextové - Ne - Inkluze a ekvivalence
Typ 1 - kontextové - částečně - neprázdnost, ANO - náležitost (necyklení), NE zbytek
Typ 0 - rekurzivní (vždy zastaví) - částečně - neprázdnost, ANO - náležitost (necyklení), NE zbytek
Typ 0 - částečně - neprázdnost, náležitost (cyklení), NE zbytek

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Vlastnosti konkrétních jazyků - Typ 3 - Regulární jazyky

A

Pumping lemma - dokážeme že jazyk NENÍ REGULÁRNÍ
- Nechť L je nekonečný regulární jazyk (každý konečný jazyk je totiž regulární). Pak existuje celočíselná konstanta p ≥ 0 taková, že platí:
• w ∈ L ∧ |w| ≥ p ⇒ w = xyz ∧ 0 < |y| ≤ p ∧ xyⁱz ∈ L (i ≥ 0)
- Neformálně: V každé dostatečně dlouhé větě každého regulárního jazyka jsme schopni najít poměrně krátkou sekvenci, kterou je možné vypustit, resp. zopakovat libovolně krát přičemž dostáváme stále věty daného jazyka.

Prefixová ekvivalence ~L - věty s oběma prefixy vždy patří do jazyka - ∀ w ∈ Σ: uw ∈ L ⇔ vw ∈ L
Dva prvky u, v jsou prefixově ekvivalentí (u ~L v) pokud platí:
∀ w ∈ Σ
: uw ∈ L ⇔ vw ∈ L

Pravá kongurence (výsledek pravé konkatenace zachovává vlastnosti - pro každé u,v,w∈Σ∗ platí u∼v⇒uw∼vw)
ekvivalence je pravou kongruencí pokud platí, že za dva ekvivalentní prvky lze připojit nějaký symbol abecedy a prvky budou stále ekvivalentní
- Nechť Σ je abeceda a ∼ je ekvivalence na Σ∗. Ekvivalence ∼ je pravou kongruencí (je zprava invariantní), pokud
pro každé u,v,w∈Σ∗ platí u∼v⇒uw∼vw

Myhill-Nerodova věta
1. Nechť L je jazyk nad Σ, pak následující tvrzení jsou ekvivalntní:
○ L je jazyk přijímaný deterministickým konečným automatem.
○ L je sjednocení některých tříd rozkladu určeného pravou kongruencí na Σ* s konečným indexem.
○ Relace ~L má konečný index.
2. Počet stavů libovolného minimálního deterministického konečného automatu přijímajícího L je roven indexu ~L (takový DKA existuje právě tehdy, když ~L je konečný)

Každý konečný jazyk je regulární (opak neplatí).

důkaz ekvivalence - automaty zminimalizuje a porovnám, budou mít stejnou strukturu

• Sjednocení, konkatenace, iterace – plyne z definice regulárních množin a ekvivalence regulárních množin a regulárních jazyků
	○ Tyto operace umím dělat s konečnýmy stavovými automaty a vždy mi vyjde konečný automat :-) 

• Komplement – KA, množina koncových stavů = Q\F
	○ Stačí prohodit koncové a nekoncové stavy

• Průnik – deMorganovy zákony - komplement
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Vlastnosti konkrétních jazyků - Typ 2 - Bezkontextové jazyky

A
Typ 2 – Bezkontextové jazyky
Pumping lemma (můžeme dokázat že daný jazyk není bezkontextový)
Pokud je jazyk L bezkontextový, existuje číslo p > 0 tak, že každé slovo w z L, pro které platí |w| ≥ p, lze zapsat ve tvaru
w = uvxyz, |vy| > 0, |vxy| ≤ p, a uvⁱxyⁱz patří do L pro každé i ≥ 0.

Problém, zda daný bezkontextový jazyk je deterministický bezkontextový jazyk, není obecně rozhodnutelný.
Problém, zda daná gramatika je nebo není víceznačná, je nerozhodnutelný.

Neuzavřenost
• Průnik – jazyky aᵐbᵐcⁿ a aᵐbⁿcⁿ jsou oba bezkontextové, průnik je jazyk aⁿbⁿcⁿ, což není bezkontextový
• Doplněk – deMorganových zákonů a uzavřenosti vůči sjednocení
Rozhodnutelnost
• Ekvivalence jazyků – ne – redukce z nerozhodnutelného Postova korespondenčního problému
• Inkluze jazyků – ne – redukce z nerozhodnutelného Postova korespondenčního problému

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Vlastnosti konkrétních jazyků - Typ 2 - Deterministické Bezkontextové jazyky

A
Deterministické bezkontextové jazyky
Uzavřenost
	• Průnik s regulárními jazyky
	• Doplněk
Neuzavřenost
	• Průnik – stejně jako BKG
	• Sjednocení – stejně jako BKG
	• Konkatenace – jazyky aᵐbᵐcⁿ a aᵐbⁿcⁿ – DZA nemuže odhadnout, zda má kontrolovat první nebo druhou rovnost
Iterace
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Vlastnosti konkrétních jazyků - Typ 1 - Kontextové jazyky

A
Typ 1 – Kontextové jazyky
Uzavřenost - vše
	• Sjednocení
	• Průnik
	• Konkatenace
	• Iterace
	• Doplněk
Rozhodnutelnost
	• Členství věty – ano – rekurzivnost
	• Inkluze jazyků – ne
prázdnost jazyka - ne (redukce z Postova problému přiřazení)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Vlastnosti konkrétních jazyků - Typ 0 - Rekurzivně vyčíslitelné jazyky

A

Riceova věta
• Každá netriviální vlastnost rekurzivně vyčíslitelných jazyků je nerozhodnutelná.
• Každá netriviální nemonotónní vlastnost rekurzivně vyčíslitelných jazyků není ani částečně rozhodnutelná.

* Triviální vlastnost – je vždy pro všechny množiny pravdivá nebo nepravdivá
* Monotónní vlastnost – pokud monotónní vlastnost platí v podmnožině tak platí i v nadmnožině

Jsou-li jazyky L i ¬L1 rekurzivně vyčíslitelné jsou oba rekurzivní.

Neuzavřenost
• Doplněk – nelze použít postup jako u úplného TS, cyklení zůstane
Rozhodnutelnost
• Náležitost jazyka – částečně – úplný TS, který bude simulovat TS nad daným řetězcem w

Rekurzivní jazyky
Uzavřenost
Doplněk – TS vždy zastaví, při nepřijetí řetězce přejde do stavu REJECT. Doplněk dostaneme záměnou stavu REJECT s původním koncovým stavem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly