AAG Flashcards
Přehled Chomského hierarchie formálních jazykú a gramatik - klasifikace gramatik
G= (N,Σ, P, S). Říkáme, že G je:
- Neomezená(typu 0), jestliže odpovídá obecné definici gramatiky.
- Kontextová(typu 1), jestliže každé pravidlo z P má tvar γAδ→γαδ,kde γ, δ∈(N∪Σ)∗, α∈(N∪Σ)+, A∈N, nebo tvar S→ε v případě, že S se nevyskytuje na pravé straně žádného pravidla.
- Bezkontextová(typu 2), jestliže každé pravidlo má tvar A→α, kde A∈N, α∈(N∪Σ)∗.
- Regulární(typu 3), jestliže každé pravidlo má tvar A→aB nebo A→a, kdeA, B∈N, a∈Σ, nebo tvar S→ε v případě, že S se nevyskytuje napravé straně žádného pravidla.
Přehled Chomského hierarchie formálních jazykú a gramatik - klasifikace jazykú
Řekneme že, jazyk (podmnožiny formálnych jazykov)
- je rekurzivně spočetný(typu 0), pokud ∃ neomezená gramatika, která ho generuje.
- rozpoznatelné Turingovým strojem
- je kontextový(typu 1), pokud ∃ kontextová gramatika, která ho generuje.
- rozpoznatelné lineárně omezeným Turingovým strojem
- je bezkontextový(typu 2), pokud ∃ bezkontextová gramatika, která hogeneruje.
- rozpoznatelné zásobníkovým automatem
- je regulární(typu 3), pokud ∃ regulární gramatika, která ho generuje.
- rozpoznatelné konečným automatem
Turingovy stroje
Deterministický/Nedeterministicky Turingův stroj (TS) je úspořadáná sedmice R = (Q, T, G, δ, q0, B, F), kde:
• Q - konečná množina vnitřních stavů
• T - konečná vstupní abeceda
• G - konečná pracovní abeceda (T ⊆ G)
• δ - zobrazení z (Q \ F) × G → P(Q × G × {−1, 0, 1})
• q0∈Q - počáteční stav (který je tam z výroby)
• B - prázdný symbol (Blank, B ∈ G \ T )
• F ⊆ Q - množina koncových stavů
TS může zapisovat na vstupní pásku a libovolně se po ní pohybovat.
Operace prováděné TS jsou opakovaně prováděny v tomto pořadí:
- Načtení vstupního symbolu a načtení odpovídající akce z přechodové tabulky.
- Přepsání stavu na magnetické pásce (volitelná akce).
- Posun po magnetické pásce (právě) o jedno pole doleva nebo doprava (volitelná akce).
- Změna stavu podle přechodové tabulky.
Nedeterministicky (K-paskovy) TS prijima prave rekurzivne spocetne jazyky k >= 1 a maji stejnou vypocetni silu.
Lineárne obmedzený TS
TS je lineárne obmedzený, pokiaľ nemôže prekročiť dĺžku k-násobku vstupného slova pre nejaké k ≥1
Univerzálny TS
TS je univerzálny, práve keď príjma všetky dvojice (kód(R); α) takové, že TS R príjma slovo α
Každý jazyk príjmaný k-páskovým TS, k≥1, je…
rekurzívne spočetný
Turingúv stroj R rozhoduje jazyk L nad abecedou Σ, keď …
sa výpočet pre každé slovo zastaví a L(R) = L
Jazyk L je rekurzivní, pokud …
existuje TS, ktorý ho rozhoduje
L(R) je …
jazyk slov přijímaných TSR
Pro každou nezkracující gramatiku G existuje …
ekvivalentní kontextová gramatika
Pro každou gramatiku G, existuje TS R takový,
…že L(G) =L(R)
Pro každou nezkracujíci gramatiku G, existuje lineárne obmedzený TS R takový,
…že L(G) =L(R)
L je rekurzivní, právě když
L a L s pruhom jsou rekurzivně spočetné
Church-Turingova teze
Každý jazyk, který lze nějakým způsobem popsat konečným výrazem,jerekurzivně spočetný.Ke každému algoritmu existuje ekvivalentní Turingův stroj.
Třída P (polynomiální problémy)
Problémy, jejichž složitost roste polynomiálně. To znamená O(n^k), kde n je počet prvků v problému. Problém lze řešit v polynomiálním čase na deterministickém TS. Takové problémy jsou řazení objektů v poli, vyhledávání podřetězce v textu, …
Třída NP (Nedeterministicky polynomiální)
Množina problémů, která lze řešit v polynomiálním čase na nedeterministickém TS. Jsou to například známý problém obchodního cestujcího, rozklad čísla na prvočinitele, izomorfismus grafů. Nalezené řešení složitosti NP je možné v max. polynomiálním čase ověřit.
Třída NP-úplný
Podmnožina NP problémů, které splňují předpoklad, že odhadnuté řešení může být ověřeno v polynomiálním čase. Navíc NP problém je úplný, pokud všechny ostatní NP problémy na něj mohou být převedeny v polynomiálním čase. Proto vzbuzují naději, že všechny NP problémy jsou řešitelné v polynomiální čase. Pokud se najde algoritmus pro polynomiální vyřešení jednoho úplného problému, pak jsou vyřešeny všechny NP.
Třída NP-hard
NP-těžké (NP-hard) problémy jsou takové problémy, na které jsou polynomiálně redukovatelné všechny ostatní
problémy z NP. (Alespoň tak těžké, jako nejtěžší roblémy v NP.) (Nejsou jen podmnožinou NP)
Halting problem
Je možné postavit stroj, který pro daný stroj a dané vstupy vyhodnotí, zda program zastaví? Turing dokázal, že to nelze, protože pokud předpokládáme, že existuje takový program, pak náčrt H+ z obrázku představuje paradox a proto musí být předpoklad špatný.
Každý konečný jazyk je …
regulární (obsahuje konečný počet vět)
Deterministický konečný automat
Deterministický konečný automat M je pětice M= (Q,Σ, δ, q0, F), kde: - Q je konečná množina vnitřních stavú, - Σ je konečná vstupní abeceda, - δ je zobrazení z Q×Σ do Q, - q0∈Q je počáteční stav, - F⊆Q je množina koncových stavú
Nedeterministický konečný automat
Deterministický konečný automat M je pětice
M= (Q,Σ, δ, q0, F), kde:
- Q je konečná množina vnitřních stavú,
- Σ je konečná vstupní abeceda,
- δ je zobrazení z Q×Σ do množiny všech podmnožin Q
- q0∈Q je počáteční stav,
- F⊆Q je množina koncových stavú
Konfigurace konečného automatu
Necht’ M= (Q,Σ, δ, q0, F) je konečný automat. Dvojici (q,w)∈Q×Σ∗ nazveme konfigurací konečného automatu M. Konfiguraci (q0, w) nazveme počáteční konfigurací konečného automatu M, konfiguraci (q, ε), kde q∈F, nazveme koncovou konfigurací konečného automatu M.
Ku každému nedeterministickému konečnému automatu, M existuje …
ekvivaletný deterministický konečný automat M’
Determinizace konečného automatu
- zbaviť sa epsilon prechodov
- ak viac počiatočných zlúčiť do spoločného
- zásobníkovým spôsobom vytvárať “nové” stavy a sledovať kam sa z nich dostanem
Vstupy sa zjednocujú
Výstupy sú, kde je aspoň jeden pôvodný výstupný
Epsilon prechody - epsiolón closure - stav sám, jeho epsilon prechody a epsilón prechody jeho epsilón prechodov
Minimalizace konečného automatu
- Zbaviť sa nedosiahnuteľných a zbytočných (ktoré nevedú do konečného) stavov, determinizovať
- rozdeliť na 2 skupiny výstupná a ostatné
Doplnok KA
Podmienky: úplne určený,DKA
Vymeniť koncové a nekoncove
Zreťazenie
Odstrániť koncové stavy z prvého KA a napojiť na štart druhého KA
Iterace
pridať nový počiatočný stav, ktorý je aj koncový a epsilon prechod do pôvodného, z koncových epsilon prechody do pôvodného
Prienik a zjednotenie
- počiatočné zlúčiť do spoločného
- zásobníkovým spôsobom vytvárať “nové” stavy a sledovať kam sa z nich dostanem
Vstupné - zjednotené vstupné
Výstup prienik - výstup v prieniku pôvodných výstupných
Výstup zjednotenie - výstup ktorýkoľvek výstupný z pôvodných
KA -> RG
prepísať do usporiadanej štvorice
RV -> KA
metoda sousedú
RV -> RG
metoda derivací
Bezkontextový jazyk
Jazyk L je bezkontextový (typu 2), pokud existuje bezkontextová gramatika, která ho generuje.
• Jsou rozpoznatelné zásobníkovým automatem
Bezkontextová gramatika
.Bezkontextová(typu 2), jestliže každé pravidlo má tvar A→α, kde A∈N, α∈(N∪Σ)∗.
Vlasní bezkontextová gramatika je …
bez cyklov, bez epsilon prechodov a nemá zbytočné stavy
Zásobníkový automat
Konfigurácia: (vnútorný stav,nespracovaná časť,obsah zásobníku)
Príjma koncovými stavmi a prázdnym zásobníkom
Zásobníkový automatje sedmiceR= (Q,Σ, G, δ, q0, Z0, F), kde:
- Q je konečná množina vnitřních stavů,
- Σ je konečná vstupní abeceda,
- G je konečná abeceda zásobníku,
- δ je zobrazení z konečné podmnožiny Q×(Σ∪{ε})×G∗ do množiny konečných podmnožin Q×G∗,
- q0∈Q je počáteční stav,
- Z0∈G je počáteční symbol v zásobníku,
- F⊆Q je množina koncových stavů.
Lavá (pravá) derivácia
Derivace S⇒∗α, α∈(N∪Σ)∗ se nazývá levá derivace (pravá derivace), jestliže při každém kroku byl nahrazován neterminální symbol nejvíce vlevo (vpravo) ve větné formě.
Ľavý (pravý) rozklad
Je dána G= (N,Σ, P, S). Předpokládejme, že pravidla v P jsou očíslována 1,2, . . . ,|P|. Rozkladem větné formy α v G je posloupnost čísel pravidel použitých v derivaci S⇒∗α. Levým rozkladem větné formy α v G je pak posloupnost čísel pravidel použitých v levé derivaci S⇒∗α.Pravým rozkladem větné formy α v G je pak obrácená posloupnost čísel pravidel použitých v pravé derivaci S⇒∗α
Syntaktická analýza - skora dolú
proces nalezení levého rozkladu dané vety v dané gramatice - expanze, srovnání
vrchol zásobníku vlavo
Syntaktická analýza - zdola nahoru
proces nalezení pravého rozkladu dané vety v dané gramatice - presun, redukcia, prijatie
vrchol zásobníku vpravo
