12 - Vlastnosti formálních jazyků
pátek 13. května 2016
10:12
Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost).
Uzavřenost jazyků vůči operacím
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)
Definice:
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)
Definice:
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 morfismus
Ostatní operace jsou obvyklé množinové operace.
Sjednocení - jazyk obsahuje řetězce z obou jazyků: 𝐿1∪𝐿2 = {𝑥: 𝑥∈𝐿1∨𝑥∈𝐿2}
Uvažujme jazyky L1= {0, 1, 00, 01}, L2= {00, 01, 10, 11} | L1∪L2 = {0, 1, 00, 01, 10, 11}
Průnik - jsou přijímány pouze řetězce, které jsou společné pro oba jazyky 𝐿1∩𝐿2 = {𝑥: 𝑥∈𝐿1∧𝑥∈𝐿2}
Uvažujme jazyky L1= {0, 1, 00, 01}, L2= {00, 01, 10, 11} | L1∩L2 = {00, 01}
Rozdíl - 𝐿1−𝐿2 = {𝑥: 𝑥∈𝐿1∧𝑥∉𝐿2}
Uvažujme jazyky L1= {0, 1, 00, 01}, L2= {00, 01, 10, 11} | L1−L2 = {0, 1}
Doplněk - přijímáme všechny řetězce z dané abecedy kromě těch řetězců, které patří do jazyka L: 𝑳=𝚺∗−𝑳
Konkatenace - 𝐿1𝐿2 = 𝑥𝑦: 𝑥∈𝐿1∧𝑦∈𝐿2
Reverzace - 𝑟𝑒𝑣𝑒𝑟𝑠𝑒𝐿=𝑟𝑒𝑣𝑒𝑟𝑠𝑒𝑥:𝑥∈𝐿
Iterace - 
Jazyk
Průnik
Průnik s typem 3
Konkatenace
Iterace
Doplněk
Substituce
Reverze
Morfismus
Inv. morfismus
Typ 3
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Typ 2 - deterministické
Ne
Ne
Ano
Ne
Ne
Ano
Ne
Ne
Ne
Ano
Typ 2
Ano
Ne
Ano
Ano
Ano
Ne
Ano
Ano
Ano
Ano
Typ 1
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Ano
Typ 0 - rekurzivní
Ano
Ano
Ano
Ano
Ano
Ano
Ne
Ano
Ne
Ano
Typ 0
Ano
Ano
Ano
Ano
Ano
Ne
Ano
Ano
Ano
Ano
Rozhodnutelnost problémů v jazycích
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 rekzivně 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 gramtikou?
Ekvivalence gramatik – generují dvě gramatiky stejné jazyky?
Jazyk
Neprázdnost
Konečnost
Náležitost
Inkluze
Ekvivalence
Typ 3
Ano
Ano
Ano
Ano
Ano
Ano
Typ 2 - deterministické
Ano
Ano
Ano
Ano
Ne
Ano
Typ 2
Ano
Ano
Ano
Ano
Ne
Ne
Typ 1
částečně
Ne
Ne
Ano
Ne
Ne
Typ 0 - rekurzivní
částečně
Ne
Ne
Ano
Ne
Ne
Typ 0
částečně
Ne
Ne
částečně
Ne
Ne
Typ 3 - tady rozhodneme všechny možné problémy
Typ 1 a typ 0 (rekurzivní) - jsou na tom stejně.
U typu 0 nemůžeme s určitostí rozhodnout nic, jelikož TS se nám může zacyklit.
Vlastnosti jazyků
Typ 3 – Regulární jazyky
Pumping lemma
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.
Není to podmínka dostačující ale nutná! Nestačí to jako důkaz že jazyk je regulární. Ale dá se tím dokázat že regulární není.
Prefixová ekvivalence ~L
Dva prvky u, v jsou prefixově ekvivalentí (u ~L v) pokud platí:
∀ w ∈ Σ*: uw ∈ L ⇔ vw ∈ L
Tj. pokud lze oba řetězce přidat jako prefix jakémukoli řetězci jazyka a vzniklá slova buď obě budou nebo obě nebudou v jazyce L
Index ekvivalence je počet tříd rozkladu podle ekvivalence
Myhill-Nerodova věta
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.
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í).
Uzavřenost
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
Rozhodnutelnost
Neprázdnost – ano – DKA: L(M) ≠ ∅ ⇔ ∃ q ∈ Q: (q ∈ F ∧ q je dostupný z q₀)
Náležitost – ano – DKA: w ∈ L ⇔ (q₀, w) ⊢* (q, ε) ∧ q ∈ F
Ekvivalence – ano – pro každý jazyk sestavíme KA, kde množiny Q₁ a Q₂ neobsahují stejný stav. Sestrojíme KA, kde nové množiny vzniknou sjednocením původních dvou a počateční stav bude počáteční stav prvního automatu. Vypočítáme relaci nerozlišitelnosti stavů z Q₁ ∪ Q₂. Potom L(G₁) = L(G₂) ⇔ q₀¹ ≡ q₀²
Po lopatě - když automaty zminimalizuji a porovnám, tak budou mít stejnou strukturu.
Typ 2 – Bezkontextové jazyky
Pumping lemma
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ý.
Uzavřenost
Substituce jazyků
Sjednocení – plyne ze substituce Lₘ, Lₙ do jazyka {m, n}
Konkatenace – plyne ze substituce Lₘ, Lₙ do jazyka {mn}
Iterace – plyne ze substituce Lₘ do jazyka {m}*
Pozitivní iterace – plyne ze substituce Lₘ do jazyka {m}⁺
Morfismus
Inverzní morfismus
Průnik s regulárními jazyky – ZA přijímající průnik na konečném řízení, zásobníkové operace zůstavají
Neuzavřenost
Doplněk – deMorganových zákonů a uzavřenosti vůči sjednocení
Rozhodnutelnost
Neprázdnost jazyka – ano – algoritmus určující množinu neterminálů generujících terminální řetězce
Příslušnost řetězce do jazyka – ano – průnik NZA s KA přijímajícím řetězec w
Konečnost jazyka – ano – Pumping lemma
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
Deterministické bezkontextové jazyky
Uzavřenost
Průnik s regulárními jazyky - podobně jako u NZA
Doplněk - podobně jako u DKA záměna koncových a nekoncových stavů, jen je potřeba ještě řešit eps přechody
Neuzavřenost
Průnik – stejně jako BKG
Sjednocení – screenshot níže
Konkatenace – screenshot níže, jazyky aᵐbᵐcⁿ a aᵐbⁿcⁿ – DZA nemuže odhadnout, zda má kontrolovat první nebo druhou rovnost
Iterace - screenshot níže
Typ 1 – Kontextové jazyky
Uzavřenost
Průnik
Konkatenace
Iterace
Doplněk
Rozhodnutelnost
Členství věty – ano – rekurzivnost
Inkluze jazyků – ne
Typ 0 – Rekurzivně vyčíslitelné jazyky
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í.
Uzavřenost
Průnik
Konkatenace
Iterace
Neuzavřenost
Doplněk – nelze poží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.
Notes
2. Otazka (TIN) (Vlastnosti formálních jazyků):
Kdo me primarne zkousel: Ceska
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Tuhle otázku jsem se moc neučil, za 2 dny učení tinu si proste nepamatuju uzavřenosti a rozhodnutelnosti jazyků nazpamět. Dost jsem vařil z vody a kecal blbosti. Chtěl vědět základní problémy rozhodnutelnosti jazyků: Neprázdnost Prázdnost Konečnost a Náležitost řetezce do jazyka. Tohle jsem se tak nějak ale neučil, takže jsem nechápal na co se ptá. Pak když mi to v podstatě řekl, tak už jsem něco věděl. Svůj výkon jsem završil tím, že na otázku "kdy jsou gramatiky ekvivalentní" jsem řekl, že je přijímá stejny automat. Něco málo jsem řekl, ale za svůj výkon jsem se pekelně styděl, hlavně když chvíli po zkoušení mi odpověď na většinu jeho otázek docvakla. Tinu jsem při učení moc času nevěnoval, spolíhal jsem na to, že napíšu nějakou definici přechodu nebo složitosti a bude to, tyhle hlubší vlastnosti a vztahy jazyků už nemám pod kůží, navíc jsem nějak neměl svůj den, moc mi to nemyslelo. Mohli mě na tom klidně vyrazit. Celkově za D.
From <[link]> 
2. Otazka (předmět) (okruh): Vlastnosti formálních jazyků
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Hned se ujal slova a říká že o tomto bychom se mohli bavit celý den a že mám říct co to je uzávěrová vlastnost trošku jsem mlel voloviny a tak mě opravil a říká co je to když se řekne že sjednocení je uzaverova vlastnost regularnich jazyku. tak jsem mu to řekl, zekdyz sjednotime dva egularni jazyky dostaneme zase regularni a a pak se ptal vuci cemu nejsou uzavreny L0 ale L1 jo... doplnek a pak se ptal vuci cemu nejsou uzavreny L2 ale L3 jsou... prunik a doplnek a to mu stacilo...
From <[link]> 
1. Otazka (předmět) (okruh): 12. Vlastnosti formálních jazyků
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Profesor Meduna se ptal nejdřív obecně, co je uzavřenost, potom chtěl slyšet nějaké uzávěrové vlastnosti jazyků typu 3. Zeptal se, jestli znám důkaz uzavřenosti sjednocení. Řekl jsem, že se to nějak dokazuje přes 2 KA, ale že bych musel chvíli přemýšlet jak, tak řekl, že půjdeme dále. Pak se zeptal, jak se to s uzavřeností BKJ k sjednocení a doplňku. Napsal jsem důkazy, proč to není uzavřené. Nakonec se zeptal, jaká je důležitá neuzávěrová vlastnost typu 0 (doplněk u rekurzivně vyčíslitelných) a to mu stačilo.
Obecně mě moc nenechal mluvit a ptal se docela konkrétně, na hodně povrchové znalosti. Když jsem chtěl zacházet do větších detailů, zarazil mě.
From <[link]> 
1. Otazka (předmět) (okruh): 12. TIN - Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost).
Kdo me primarne zkousel: Meduna Alexander, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Prof. Meduna zhodnotil otazku ako rozsiahlu, preto sa zacal pytat co je jazyk a co znamena ze je trieda jazykov je uzavreta voci nejakej operacii a ako dokazeme ze trieda jazykov nie je uzavreta voci nejakej relacii. Nasledne sa pytal, voci akym operaciam su uzavrete regularne jazyky, ci su bezkontextove jazyky uzavrete voci konkatenacii a voci ktorej operacii nie su uzavrete jazyky L0. Na dokazy nebol cas. -> A
From <[link]> 
2. Otazka (předmět) (okruh):
Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost).
Kdo me primarne zkousel: prof. Češka 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Oproti prvni otazce tady to bylo tezce rizene, nenechal me odbehnout k zadne definici (pumping lemma, Postuv korespondencni problem) i kdyz jsme se o tom bavili. Vse chtel na obecne: princip a vyznam. Obcas jsem nake otazce neporozumel, ale zkousel jako pravy profik a kdyz videl ze nevim otazku preformuloval na to, aby se dalo odpovedet ANO/NE coz uz hlava v te chvilce zvladla vyhodnotit. Celou dobu me otazkou vedl tak abych ji zodpovedel.
Znamka: C
From <[link]> 
1. Otazka (okruh): 12. Vlastnosti formalnich jazyku(typicke vlastnosti a jejich rozhodnutelnosti)
Kdo me primarne zkousel: jen Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Ze zacatku jsem zacal mluvit mimo tema o nerozhodnutelnosti, takze jsme se opravdu chvilku bavili o HP. Pak uz to Meduna prebral pevne do svych rukou, kdy mluvil a ja jen doplnoval jake maji dane tridy vlastnosti. Naprosto v pohode.
From <[link]> 
1. Otazka (okruh):
12. Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost).
Kdo me primarne zkousel:
prof. Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Tuto otazku som celkom vedel, celkom mi sadla...len som mal nenormalny stres...a v tej chvili som nevedel povedat suvislu vetu...sme zacali dost z obecna co ma trosku dostalo do pomykova...lebo som vedel tie vlastnosti, ale formalne som ich nevedel nejak definovat...chcel odo mna, aby som to napisal na tabulu a nakoniec to ostalo len pri jednom napisanom L na tabulu a vsetko sme si vyrozpravali...chcel vediet, co su to uzaverove vlastnosti, ake su pre regularne jazyky a ake pre rekurzivne vycislitelne jazyky...podstatne bolo, ze jazyky typu 0 su neuzavrene voci doplnku a to mu stacilo..Vojnar prikyvoval a usmieval sa
From <[link]> 