Permalink
Switch branches/tags
Nothing to show
Find file Copy path
36ac5e6 Jun 13, 2018
2 contributors

Users who have contributed to this file

@Krejdom @BorysekOndrej
325 lines (207 sloc) 12.5 KB

IB102 Automaty, gramatiky a složitost

Gramatika

G = (N, Σ, P, S)

N je konečná množina neterminálů

Σ je konečná množina terminálů, přičemž N ∩ Σ = {}

P je konečná množina pravidel ve tvaru (Σ ∪ N)* N (Σ ∪ N)* → (Σ ∪ N)*

S ∈ N je počáteční neterminál

DFA Deterministický konečný automat

A = (Q, Σ, δ, q0, F)

Q je neprázdná konečná množina stavů

Σ je konečná vstupní abeceda

δ: Q × Σ → Q je parciální přechodová funkce

q0 ∈ Q je iniciální stav

F ⊆ Q je konečná množina akceptujících stavů

Rozšířená přechodová funkce

δ^: Q × Σ* → Q je definována induktivně:

δ^(q,ε) = q pro každý stav q ∈ Q

δ^(q,wa) = δ(δ^(q,w)a) ... je-li δ^(q,w) i δ(δ^(q,w)a) definováno; ⊥ ... jinak

Slovo w je akceptováno automatem M právě když (δ^(q0,w) ∈ F.

Slovo w není akceptováno automatem M právě když (δ^(q0,w) ∉ F.

Jazyk přijímaný automatem M je L(M) = {w ∈ Σ* | (δ^(q0,w) ∈ F}.

Pumping lemma pro regulární jazyky

Nechť n ∈ N je libovolné a dále pevné.

Uvažujme slovo w = ... ∈ L, |w| = ... >= n.

Pro každé x, y, z splňující: w = xyz, |xy|<=n a y ≠ ε platí:

...všechna možná rozdělení (s podmínkami!)...

Pro i = ... platí ... tedy w ∉ L, protože ...

Z Pumping lemmatu pro regulární jazyky plyne, že L není regulární.

RE Regulární výraz

RE(Σ) je množina:

ε, {} a a pro každé a ∈ Σ jsou regulární výrazy nad Σ.

Jsou-li E, F regulární výrazy nad Σ, pak také (E.F), (E + F) a (E*) jsou regulární výrazy nad Σ.

Regulární přechodový graf

M = (Q, Σ, δ, I, F)

Q je neprázdná konečná množina stavů

Σ je konečná vstupní abeceda

δ: Q × Q → RE(Σ) je parciální přechodová funkce

I ⊆ Q je množina počátečních stavů

F ⊆ Q je množina akceptujících stavů

CFG Bezkontextová gramatika

G = (N, Σ, P, S)

N je konečná množina neterminálů

Σ je konečná množina terminálů, přičemž N ∩ Σ = {}

P ⊆ N × (Σ ∪ N)* je konečná množina pravidel

S ∈ N je počáteční neterminál

levá derivace -- při odvozování vždy přepisujeme nejlevější neterminál

nejednoznačná gramatika -- existuje slovo z jejího jazyka, která má alespoň 2 derivační stromy

vnitřně víceznačná bezkontextový jazyk -- každá bezkontextová gramatika, která jej generuje je víceznačná

Kanonické tvary bezkontextových gramatik

Redukovaná bezkontextová gramatika

  • neobsahuje žádné nepoužitelné symboly, tedy:
    • nenormované symboly -- nelze z nich vytvořit žádné slovo
    • nedosažitelné symboly -- nelze jich dosáhnout

Gramatika bez ε-pravidel

  • neobsahují žádné ε-pravidlo nebo
  • obsahují právě jedno ε-pravidlo a to: S → ε, přičemž S není na pravé straně žádného pravidla

Gramatika bez jednoduchých pravidel

jednoduché pravidlo -- A → B, kde A,B ∈ N

Vlastní bezkontextová gramatika

  • bez nepoužitelných symbolů
  • bez ε-pravidel
  • necyklická -- neterminál se nesmí po určitém počtu kroků přepsat sám na sebe

CNF Chomského normální forma

  • bez ε-pravidel
  • každé pravidlo ve tvaru:
    • A → BC, kde B,C ∈ N
    • A → a, kde a ∈ Σ
    • S → ε

Algoritmus transformace do CNF: Gramatiku převedeme na vlastní a bez jednoduchých pravidel.

Gramatika bez levé rekurze

nelevorekurzivní gramatika -- gramatika bez levorekurzivních neterminálů

  • necyklická
  • bez ε-pravidel

Greibachové normální forma

  • bez ε-pravidel
  • každé pravidlo ve tvaru:
    • A → aα, kde a ∈ Σ a α ∈ N*
    • S → ε

Pumping lemma pro bezkontextové jazyky

Nechť n ∈ N je libovolné a dále pevné.

Uvažujme slovo w = ... ∈ L, |w| = ... > n.

Pro každé u, v, x, y, z splňující: w = uvxyz, |vxy|<=n a vy ≠ ε platí:

...všechna možná rozdělení (s podmínkami!)...

Pro i = ... platí ... tedy w ∉ L, protože ...

Z Pumping lemmatu pro bezkontextové jazyky plyne, že L není bezkontextový.

PDA Zásobníkový automat

M = (Q, Σ, Γ, δ, q0, Z0, F)

Q je konečná množina stavů

Σ je konečná množina vstupní abecedy

Γ je konečná množina zásobníkové abecedy

δ: Q × (Σ ∪ {ε}) × Γ → Pfin(Q × Γ*) je parciální přechodová funkce (Pfin(Q × Γ*) je označení množiny všech konečných podmnožin Q × Γ*)

q0 ∈ Q je iniciální stav

Z0 ∈ Γ je počáteční symbol v zásobníku

F ⊆ Q je konečná množina koncových stavů

Nedeterministická syntaktická analýza zdola nahoru

Syntaktický analyzátor zdola nahoru

Čteme epsiolon a ze zásobníku pravou stranu pravidla, přesunu se do stejného stavu a na zásobník zapíši levou stranu pravidla. Následně čtu terminály, ze zásobníku epsilon, zůstávám opět ve stejném stavu a na zásobník zapíši přečtený terminál. Přečtení dna zásobníku: Čtu epsilon, na zásobníku ⊥S, přejdu do akceptujícího stavu a na zásobník zapíši epsilon.

`R = ({q, r}, Σ, N ∪ Σ ∪ {⊥}, δ, q, ⊥, {r})

Analýza zdola nahoru

(q, slovo, ⊥) ... postupně načítám slovo na zásobník (ujídám ho zleva) a přitom se snažím obsah zásobníku zprava redukovat pomocí pravidel tak, aby na něm zůstalo jen ⊥S, pomocí kterého se pak přepnu do akceptujícího stavu.

Nedeterministická syntaktická analýza shora dolů

Syntaktický analyzátor shora dolů

Čteme epsilon a ze zásobníku neterminál z levé strany pravidla, zůstaneme ve stejném stavu a na zásobník zapíšeme pravou stranu pravidla (těch je více, takže je analyzátor nedeterministický). Dále čteme terminál tentýž i ze zásobníku, zůstaneme ve stejném stavu a na zásobník dáme epsilon. Akceptujeme prázdným zásobníkem.

`M = ({q}, Σ, N ∪ Σ, δ, q, S, {})

Analýza shora dolů

Čteme epsilony a na zásobníku postupně zleva vytváříme struktury odpovídající pravým stranám pravidel. Pokud je vlevo na zásobníku terminál, přečteme ho a odstraníme. Takto postupujeme, dokud nemáme prázdný zásobník, čteme epsilon.

DPDA Deterministický zásobníkový automat

M = (Q, Σ, Γ, δ, q0, Z0, F)

  • pro všechna q ∈ Q a Z ∈ Γ platí: kdykoliv δ(q,ε,Z) ≠ {}, pak δ(q,a,Z) = {}, pro všechna a ∈ Σ
  • pro žádné q ∈ Q, Z ∈ Γ a a ∈ Σ ∪ {ε} neobsahuje δ(q,a,Z) více než jeden prvek

Rozšířený zásobníkový automat

δ: Q × (Σ ∪ {ε}) × Γ* → Pfin(Q × Γ*) je parciální přechodová funkce (Pfin(Q × Γ*) je označení množiny všech konečných podmnožin Q × Γ*)

Ke každému rozšířenému PDA existuje ekvivalentní PDA

TM Turingův stroj

M = (Q, Σ, Γ, ▻, ⌊⌋, δ, q0, qacc, qrej)

Q je konečná množina stavů

Σ je konečná množina vstupní abecedy

Γ je konečná množina pracovní abecedy, Σ ⊆ Γ

▻ ∈ Γ ∖ Σ je levá koncová značka

⌊⌋ ∈ Γ ∖ Σ je prázdné políčko

δ: (Q ∖ {qacc, qrej}) × Γ → Q × Γ × {L,R} je totální přechodová funkce

q0 ∈ Q je iniciální stav

qacc ∈ Q je akceptující stav

qrej ∈ Q je zamítající stav

navíc pro každé q ∈ Q existuje p ∈ Q takový, že δ(q,▻) = (p,▻,R) (tj. nelze přepsat přepsat ani posunout čtecí hlavu za okraj pásky)

(úplný TM rozhoduje jazyk, jiný akceptuje, rozpoznává, přijímá...)

Konfigurace TM

(q,z,n)

q je stav

z je obsah pásky

n značí pozici hlavy na pásce

počáteční konfigurace pro vstup w ∈ Σ je (q0, ▻w⌊⌋⌊⌋⌊⌋..., 0)

akceptující konfigurace je (qacc, z, n)

zamítající konfigurace je (qrej, z, n)

Výpočet TM

  • stroj akceptuje slowo w právě když výpočet M na w je konečný a jeho poslední konfigurace je akceptující
  • stroj zamítá slowo w právě když výpočet M na w je konečný a jeho poslední konfigurace je zamítající
  • stroj cyklí pro vstup w právě když výpočet M na w je nekonečný

k-páskový Turingův stroj

δ: (Q ∖ {qacc, qrej}) × Γ^k → Q × Γ^k × {L,R}^k je totální přechodová funkce

Nedeterministický Turingův stroj

δ: (Q ∖ {qacc, qrej}) × Γ → 2^(Q × Γ × {L,R}) je totální přechodová funkce

Pro každý nedeterministický TM existuje ekvivalentní deterministický TM.

Chomského hierarchie gramatik

  • frázové gramatiky -- bez omezení
  • kontextové gramatiky -- α → β, |α| <= |β| (výjimka: S → ε, S není na pravé straně žádného pravidla)
  • bezkontextové gramatiky -- A → α, |α| <= 1 (výjimka: S → ε, S není na pravé straně žádného pravidla)
  • regulární gramatiky -- A → aB nebo A → a (výjimka: S → ε, S není na pravé straně žádného pravidla)

Chomského hierarchie jazyků

  • rekurzivně spočetné jazyky -- generované frázovou gramatikou, rozpoznatelné TM, částečně rozhodnutelný
  • rekurzivní jazyky -- rozhodované úplným TM, rozhodnutelný
  • kontextové jazyky -- generované kontextovou gramatikou, rozpoznávány ohraničeným TM
  • bezkontextové jazyky -- generované bezkontextovou gramatikou, zásobníkovým automatem
  • deterministické bezkontextové jazyky -- generované deterministickým zásobníkovým automatem
  • regulární jazyky -- generované regulární gramatikou, konečným automatem

Uzávěrové vlastnosti

∩REG co- . * + ^n R
regulární
bezkontextové × ×
deterministické bezkontextové × ×
rekurzivní
rekurzivně spočetné ×

Jazyk L je rekurzivní, právě když jsou jazyky L a co-L rekurzivně spočetné.

Vyučované algoritmy a postupy

  • Synchronní paralelní kompozice automatů
  • Transformace automatu na automat akceptující jeho doplněk
  • Algoritmus pro eliminaci nedosažitelných stavů DFA
  • Eliminace ekvivalentních stavů
  • Algoritmus konstrukce minimálního automatu
  • Převod automatu do kanonického tvaru
  • Algoritmus transformace NFA na ekvivalentní DFA
  • Převod regulárního přechodového grafu na NFA
  • Převod DFA na RE
  • Převod regulární gramatiky na konečný automat
  • Převod konečného automatu na regulární gramatiku
  • Nalezení nenormovaných symbolů: Napočítáme množiny N0, N1, N2,... které obsahují neterminály, ze kterých odvodíme slovo v n-tém kroku. Postupně nabalujeme další, dokud se dvě poslední množiny nerovnají. Zbytek neterminálů odstraníme.
  • Nalezení nedosažitelných symbolů: Napočítáme množiny V0, V1, V2,... které obsahují neterminály i terminály (!), které jsou dosažitelné po n odvozeních. V0 = {S}. Postupně nabalujeme další, dokud se dvě poslední množiny nerovnají. Zbytek neterminálů a terminálů odstraníme.
  • Algoritmus pro odstranění ε-pravidel
  • Algoritmus pro odstranění jednoduchých pravidel
  • Algoritmus transformace do CNF
  • Algoritmus odstranění levé rekurze

Problémy

HALT (problém zastavení) -- nerozhodnutelný ACC (problém akceptování) -- nerozhodnutelný NONEMPTY (problém neprázdnosti) -- není rozhodnutelný PCP (Postův korespondenční systém) -- není rozhodnutelný

Redukce

M-redukce

A <=m B:

  • B je rekurzivní -> A je rekurzivní
  • B je rekurzivně spočetný -> A je rekurzivně spočetný
  • A není rekurzivní -> B není rekurzivní
  • A není rekurzivně spočetný -> B není rekurzivně spočetný

Polynomiální redukce

A <=p B

  • B ∈ P -> A ∈ P
  • B ∈ NP -> A ∈ NP
  • A není v P -> B není v P
  • A není v NP -> B není v NP

Časová a prostorová složitost

P ⊆ NP ⊆ NPSPACE = PSPACE ⊆ EXPTIME ⊆ NEXPTIME

PATH (problém, zda v orientovaném grafu existuje cesta z u do v) ∈ P

HAMPATH (problém, zda v orientovaném grafu existuje Hamiltonovská cesta) ∈ NP

SAT -- NP úplný (tj. NP těžký a SAT ∈ NP)

3SAT -- NP úplný

TQBF -- PSPACE-úplný