TIN 15. Transformace a normální formy bezkontextových gramatik.

Card Set Information

Author:
hrbi
ID:
222655
Filename:
TIN 15. Transformace a normální formy bezkontextových gramatik.
Updated:
2013-06-06 05:50:21
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Bezkontextová gramatika
    • G = (N, Σ, P, S)
    • P: A → α, A ∈ N, α ∈ (N ∪ Σ)*
  2. Derivační strom
    • G = (N, Σ, P, S)
    • S ⇒ v0 ⇒ v1 ⇒ ... ⇒ vk ⇒ δ, δ ∈ (N ∪ Σ)*
    • vrcholově ohodnocený strom s těmito vlastnostmi:
    • 1. vrcholy jsou ohodnoceny symboly z (N ∪ Σ)
    • 2. kořen je ohodnocen symbolem S
    • 3. přímé derivaci, kde i-1 ⇒ vi, i-1 = μAλ, i = μαλ, A → α ∈ P, α = X1X2...Xn, odpovídá n hran (A, Xj) z uzlu A v pořadí (A, X1), (A, X2), ..., (A, Xn) zleva doprava
    • 4. ohodnocení vrcholových uzlů vytváří zleva doprava větnou formu δ
  3. Levá (pravá) derivace
    • G = (N, Σ, P, S)
    • derivace větné formy S ⇒ v0 ⇒ v1 ⇒ ... ⇒ vk ⇒ δ, δ ∈ (N ∪ Σ)*
    • jestliže byl v každém řetězci v0, v1, ..., vk přepsán nejlevější (nejpravější) neterminál, jedná se o levou (pravou) derivaci
  4. Fráze větné formy
    • G = (N, Σ, P, S)
    • λ = αβγ je větná forma, β je fráze větné formy vzhledem k neterminálu A ⇔
    • S ⇒* αAγ ∧ A ⇒+ β
    • jednoduchá fráze větné formy: S ⇒* αAγ ∧ A ⇒ β
    • l-fráze: nejlevější jednoduchá fráze
  5. Víceznačnost gramatik
    • věta w je víceznačná, pokud existuje více různých derivačních stromů, jejichž koncové uzly tvoří w
    • gramatika je víceznačná, pokud generuje alespoň jednu víceznačnou větu, jinak je jednoznačná
    • jazyk s inherentní víceznačností - nelze generovat jednoznačnou gramatikou
    • problém víceznačnosti je nerozhodnutelný
    • příklad: E → E+E | E-E | E*E | E/E | (E) | i
  6. Ekvivalentní gramatiky
    generují stejný jazyk
  7. Nedostupný symbol
    • G = (N, Σ, P, S)
    • symbol X ∈ (N ∪ Σ) je nedostupý v G, pokud v G neexistuje derivace S ⇒* αXβ
    • nejde vůbec derivovat z S
    • výpočet množiny V dostupných symbolů
    • 1. začnu z počátečního neterminálu S
    • 2. přidám do množiny V všechny neterminály na pravé straně nějakých pravidel, která mají na levé straně už nalezený neterminál z V, ...
  8. Zbytečný symbol
    • G = (N, Σ, P, S)
    • symbol X ∈ (N ∪ Σ) je zbytečný v G, pokud v G neexistuje derivace S ⇒* αXβ ⇒* zxy
    • negeneruje větu
    • výpočet množiny Nt generující terminální řetězce:
    • 1. najdu pravidla, která mají na pravé straně pouze terminály, neterminály na levé straně pravidel přidám do Nt
    • 2. najdu pravidla, která mají na pravé straně pouze terminály nebo neterminály z Nt, ...
  9. Odstranění zbytečných a nedostupných symbolů
    • 1. vyhodím zbytečné symboly, upravím pravidla
    • 2. vyhodím nedostupné symboly, upravím pravidla
  10. Odstranění ε-pravidel
    • 1. nalezení neterminálů, které generují ε, Nε = {A | A ⇒+ ε}
    • 2. pravidla tvaru A → αBβDγ, kde B, D ∈ Nε nahradím mrakem pravidel: A → αBβDγ | αβDγ | αBβγ | αβγ
    • 3. odstraním ε-pravidla
    • 4. pokud S ∈ Nε, pak přidám nový neterminál S' a pravidlo S' → S | ε
  11. Jednoduché pravidlo
    A → B
  12. Odstranění jednoduchých pravidel
    • 1. najdu pro každý neterminál A všechny neterminály, které jej derivují (NA = {B | A ⇒* B})
    • 2. přidám všechny pravé strany pravidel, které mají na levé straně některý neterminál z NA k pravidlům A → ...
    • 3. odstraním jednoduchá pravidla
  13. Cyklus
    G obsahuje cyklus, jestliže A ⇒+ A
  14. Vlastní gramatika
    • gramatika bez zbytečných a nedostupných symbolů, ε-pravidel a cyklů
    • převod:
    • 1. odstranění zbytečných a nedostupných symbolů
    • 2. odstranění ε-pravidel
    • 3. odstranění jednoduchých pravidel
  15. Levá rekurze
    A → Aα
  16. Odstranění levé rekurze
    • A → Aα | β
    • se transformuje na
    • A → β | βA'
    • A' → α | αA'
  17. Odstranění nepřímé levé rekurze
    • nejdřív aplikuju A → Bα, B → β | γ ... A → βα | γα (nahrazení neterminálu pravými stranami pravidel)
    • pak odstraním levou rekurzi
  18. Chomského normální forma
    • G = (N, Σ, P, S)
    • A → BC
    • A → α
    • S → ε, S není na pravé straně
    • převod:
    • 1. ponecháme pravidla tvaru CNF
    • 2. A → BCDEF... transformujeme na A → B', kde B' je buď terminál nebo nový neterminál
    • 3. A → BC transformuje na A → B'C', B' a C' jsou neterminály (pokud B, C už byly neterminály, pak se ponechají)
    • 4. pro nové neterminály tvaru zavedeme pravidla → C'
    • 5. doplníme pravidla pro nové neterminály A' → a, pokud to mají být terminály
  19. Greibachové normální forma
    • G = (N, Σ, P, S)
    • A → aα, a ∈ Σ, α ∈ N*
    • S → ε, S není na pravé straně
    • převod:
    • 1. odstranění levé rekurze a ε-pravidel
    • 2. nalezení lineárního uspořádání ≺ na N (A ≺ B ⇔ ∃A → Bα ∈ P)
    • 3. aplikace substitucí v pořadí opačném k ≺ tak, aby byla pravidla ve tvaru A → aβ, β ∈ (N ∪ Σ)*
    • 4. převod pravidel tvaru A → aβ na A → aα, α ∈ N*

What would you like to do?

Home > Flashcards > Print Preview