Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Statnice - spolocne > AAG > Flashcards

AAG Flashcards

1
Q

Přehled Chomského hierarchie formálních jazykú a gramatik - klasifikace gramatik

A

G= (N,Σ, P, S). Říkáme, že G je:

  1. Neomezená(typu 0), jestliže odpovídá obecné definici gramatiky.
  2. 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.
  3. Bezkontextová(typu 2), jestliže každé pravidlo má tvar A→α, kde A∈N, α∈(N∪Σ)∗.
  4. 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Přehled Chomského hierarchie formálních jazykú a gramatik - klasifikace jazykú

A

Řekneme že, jazyk (podmnožiny formálnych jazykov)

  1. je rekurzivně spočetný(typu 0), pokud ∃ neomezená gramatika, která ho generuje.
    • rozpoznatelné Turingovým strojem
  2. je kontextový(typu 1), pokud ∃ kontextová gramatika, která ho generuje.
    • rozpoznatelné lineárně omezeným Turingovým strojem
  3. je bezkontextový(typu 2), pokud ∃ bezkontextová gramatika, která hogeneruje.
    • rozpoznatelné zásobníkovým automatem
  4. je regulární(typu 3), pokud ∃ regulární gramatika, která ho generuje.
    • rozpoznatelné konečným automatem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Turingovy stroje

A

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í:

  1. Načtení vstupního symbolu a načtení odpovídající akce z přechodové tabulky.
  2. Přepsání stavu na magnetické pásce (volitelná akce).
  3. Posun po magnetické pásce (právě) o jedno pole doleva nebo doprava (volitelná akce).
  4. Změna stavu podle přechodové tabulky.

Nedeterministicky (K-paskovy) TS prijima prave rekurzivne spocetne jazyky k >= 1 a maji stejnou vypocetni silu.

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

Lineárne obmedzený TS

A

TS je lineárne obmedzený, pokiaľ nemôže prekročiť dĺžku k-násobku vstupného slova pre nejaké k ≥1

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

Univerzálny TS

A

TS je univerzálny, práve keď príjma všetky dvojice (kód(R); α) takové, že TS R príjma slovo α

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

Každý jazyk príjmaný k-páskovým TS, k≥1, je…

A

rekurzívne spočetný

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

Turingúv stroj R rozhoduje jazyk L nad abecedou Σ, keď …

A

sa výpočet pre každé slovo zastaví a L(R) = L

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

Jazyk L je rekurzivní, pokud …

A

existuje TS, ktorý ho rozhoduje

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

L(R) je …

A

jazyk slov přijímaných TSR

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

Pro každou nezkracující gramatiku G existuje …

A

ekvivalentní kontextová gramatika

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

Pro každou gramatiku G, existuje TS R takový,

A

…že L(G) =L(R)

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

Pro každou nezkracujíci gramatiku G, existuje lineárne obmedzený TS R takový,

A

…že L(G) =L(R)

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

L je rekurzivní, právě když

A

L a L s pruhom jsou rekurzivně spočetné

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

Church-Turingova teze

A

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.

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

Třída P (polynomiální problémy)

A

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, …

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

Třída NP (Nedeterministicky polynomiální)

A

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.

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

Třída NP-úplný

A

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.

18
Q

Třída NP-hard

A

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)

19
Q

Halting problem

A

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ý.

20
Q

Každý konečný jazyk je …

A

regulární (obsahuje konečný počet vět)

21
Q

Deterministický konečný automat

A 
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ú
22
Q

Nedeterministický konečný automat

A

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ú

23
Q

Konfigurace konečného automatu

A

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.

24
Q

Ku každému nedeterministickému konečnému automatu, M existuje …

A

ekvivaletný deterministický konečný automat M’

25
Q

Determinizace konečného automatu

A
  1. zbaviť sa epsilon prechodov
  2. ak viac počiatočných zlúčiť do spoločného
  3. 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

26
Q

Minimalizace konečného automatu

A
  1. Zbaviť sa nedosiahnuteľných a zbytočných (ktoré nevedú do konečného) stavov, determinizovať
  2. rozdeliť na 2 skupiny výstupná a ostatné
27
Q

Doplnok KA

A

Podmienky: úplne určený,DKA

Vymeniť koncové a nekoncove

28
Q

Zreťazenie

A

Odstrániť koncové stavy z prvého KA a napojiť na štart druhého KA

29
Q

Iterace

A

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

30
Q

Prienik a zjednotenie

A
  1. počiatočné zlúčiť do spoločného
  2. 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

31
Q

KA -> RG

A

prepísať do usporiadanej štvorice

32
Q

RV -> KA

A

metoda sousedú

33
Q

RV -> RG

A

metoda derivací

34
Q

Bezkontextový jazyk

A

Jazyk L je bezkontextový (typu 2), pokud existuje bezkontextová gramatika, která ho generuje.
• Jsou rozpoznatelné zásobníkovým automatem

35
Q

Bezkontextová gramatika

A

.Bezkontextová(typu 2), jestliže každé pravidlo má tvar A→α, kde A∈N, α∈(N∪Σ)∗.

36
Q

Vlasní bezkontextová gramatika je …

A

bez cyklov, bez epsilon prechodov a nemá zbytočné stavy

37
Q

Zásobníkový automat

A

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ů.

38
Q

Lavá (pravá) derivácia

A

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ě.

39
Q

Ľavý (pravý) rozklad

A

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⇒∗α

40
Q

Syntaktická analýza - skora dolú

A

proces nalezení levého rozkladu dané vety v dané gramatice - expanze, srovnání

vrchol zásobníku vlavo

41
Q

Syntaktická analýza - zdola nahoru

A

proces nalezení pravého rozkladu dané vety v dané gramatice - presun, redukcia, prijatie

vrchol zásobníku vpravo

Statnice - spolocne (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions