Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:opakovani_pjp [2009/10/21 22:01]
keymaster created
+++ courses:a4m33pal:opakovani_pjp [2025/01/03 18:28] (aktuální)
@@ Řádek 5: / Řádek 5: @@
 Některé důležité pojmy ze státnicových otázek z EaI - předmět PJP (snad nikomu nebude vadit, že jsem to sem dal :), pokud by to vadilo, tak to smáznu )
-Abecedy a jazyky
+===== Abecedy a jazyky =====
     * abeceda = konečná množina symbolů
     * řetězec (řetěz, slovo) nad abecedou T:
-          o konečná posloupnost symbolů z T
+      * konečná posloupnost symbolů z T
-          o ε je prázdný řetězec
+      * ε je prázdný řetězec
-          o T* je množina všech řetězců nad T (včetně prázdného řetězce)
+      * T* je množina všech řetězců nad T (včetně prázdného řetězce)
     * operace zřetězení
-          o xy je řetězec, který vznikne připojením řetězce y za řetězec x
+      * xy je řetězec, který vznikne připojením řetězce y za řetězec x
-          o je asociativní, není komutativní
+      * je asociativní, není komutativní
-          o ε je jednotkový prvek
+      * ε je jednotkový prvek
-          o |x| je délka řetězce x (počet symbolů)
+      * |x| je délka řetězce x (počet symbolů)
     * formální jazyk L je libovolná podmnožina množiny všech řetězců nad abecedou T: L ⊂ T*
     * operace nad formálními jazyky:
-          o obvyklé množinové operace
+      * obvyklé množinové operace
-          o součin (zřetězení) jazyků L1 · L2 = {xy: x ∈ L1, y ∈ L2}
+      * součin (zřetězení) jazyků L1 · L2 = {xy: x ∈ L1, y ∈ L2}
-          o n-tá mocnina Ln = L · Ln-1, L0 = {ε}, L1 = L
+      * n-tá mocnina Ln = L · Ln-1, L0 = {ε}, L1 = L
-          o iterace L* = ∪Ln pro n = 0 .. ∞
+      * iterace L* = ∪Ln pro n = 0 .. ∞
-          o pozitivní iterace L+ = ∪Ln pro n = 1 .. ∞
+      * pozitivní iterace L+ = ∪Ln pro n = 1 .. ∞
+===== Gramatiky =====
-Gramatiky
     * bezkontextová gramatika G:
-          o G = (N, T, P, S)
+       * G = (N, T, P, S)
-                + N je konečná množina neterminálních symbolů
+           * N je konečná množina neterminálních symbolů
-                + T je konečná množina terminálních symbolů (N ∩ T = ø)
+           * T je konečná množina terminálních symbolů (N ∩ T = ø)
-                + P je konečná množina pravidel zapisovaných ve tvaru A → α, kde A ∈ N, α ∈ (N ∪ T)*
+           * P je konečná množina pravidel zapisovaných ve tvaru A → α, kde A ∈ N, α ∈ (N ∪ T)*
-                + S je počáteční (startovací) symbol gramatiky
+           * S je počáteční (startovací) symbol gramatiky
-          o levou stranou pravidla A → α rozumíme neterminál A, pravou stranou řetězec α
+       * levou stranou pravidla A → α rozumíme neterminál A, pravou stranou řetězec α
-          o několik pravidel se stejnou levou stranou zapisujeme též zkráceně ve tvaru A → α1 | α2 | ... | αn
+       * několik pravidel se stejnou levou stranou zapisujeme též zkráceně ve tvaru A → α1 | α2 | ... | αn
     * regulární gramatika G:
-          o je bezkontextová gramatika, ve které každé pravidlo má tvar A → aB nebo A → a, kde A,B ∈ N, a ∈ T
+       * je bezkontextová gramatika, ve které každé pravidlo má tvar A → aB nebo A → a, kde A,B ∈ N, a ∈ T
-          o vyjímku tvoří pravidlo S → ε v případě, že S se neobjeví na pravé straně žádného pravidla
+       * vyjímku tvoří pravidlo S → ε v případě, že S se neobjeví na pravé straně žádného pravidla
     * přímá derivace
-          o x ⇒ y (x přímo derivuje y), jestliže x = αAβ, y = αχβ, A ∈ N, α, β, χ ∈ (N ∪ T)* a v P existuje pravidlo A → χ
+       * x ⇒ y (x přímo derivuje y), jestliže x = αAβ, y = αχβ, A ∈ N, α, β, χ ∈ (N ∪ T)* a v P existuje pravidlo A → χ
-          o k-tá mocnina relace ⇒ se označuje ⇒k
+       * k-tá mocnina relace ⇒ se označuje ⇒k
-          o tranzitivní uzávěr relace ⇒ se označuje ⇒+
+       * tranzitivní uzávěr relace ⇒ se označuje ⇒+
-          o reflexivně tranzitivní uzávěr relace ⇒ se označuje ⇒*
+       * reflexivně tranzitivní uzávěr relace ⇒ se označuje ⇒*
     * derivací řetězce β z řetězce α délky k v gramatice G = (N, T, P, S) se nazývá posloupnost řetězců α0, α1, ..., αk takových, že α = α0, αi-1 ⇒ αi pro 1 ≤ i ≤ k a αk = β
     * větnou formou v gramatice G = (N, T, P, S) se nazývá řetězec α, pro který platí S ⇒* α, α ∈ (N ∪ T)*. Větná forma neobsahující neterminální symboly se nazývá věta generovaná gramatikou G
@@ Řádek 50: / Řádek 49: @@
     * gramatiky G1 a G2 jsou ekvivalentní, když generují stejný jazyk: L(G1) = L(G2)
+===== Derivační stromy =====
-Derivační stromy
     * derivační strom v gramatice G = (N, T, P, S) má tyto vlastnosti:
-          o uzly derivačního stromu jsou ohodnoceny terminálními a neterminálními symboly
+      * uzly derivačního stromu jsou ohodnoceny terminálními a neterminálními symboly
-          o kořen stromu je ohodnocem počátečním symbolem gramatiky
+      * kořen stromu je ohodnocem počátečním symbolem gramatiky
-          o jestliže má uzel alespoň jednoho následníka, pak je ohodnocen neterminálním symbolem
+      * jestliže má uzel alespoň jednoho následníka, pak je ohodnocen neterminálním symbolem
-          o jestliže n1, n2, ..., nk jsou bezprostřední následnovníci uzlu n, který je ohodnocen symbolem A, a tyto uzly jsou ohodnoceny symboly A1, A2, ..., Ak, pak A → A1A2...Ak je pravidlo v P
+      * jestliže n1, n2, ..., nk jsou bezprostřední následnovníci uzlu n, který je ohodnocen symbolem A, a tyto uzly jsou ohodnoceny symboly A1, A2, ..., Ak, pak A → A1A2...Ak je pravidlo v P
-          o listy derivačního stromu tvoří zleva doprava větnou formu nebo větu v gramatice G
+      * listy derivačního stromu tvoří zleva doprava větnou formu nebo větu v gramatice G
     * gramatika G je jednoznačná, pokud pro každou větu existuje právě jeden derivační strom
     * věta w se nazývá víceznačná, jestliže pro ni existují alespoň dva různé derivační stromy
@@ Řádek 65: / Řádek 63: @@
 napr. věta: a+a+a (pro tuto větu lze vyvořit 2 derivační stromy -> tato gramatika je víceznačná) soubor: derivacnistrom.jpg
+===== Konečný automat =====
-Konečný automat
 (deterministický) Konečný automat (DKA, DFA) je pětice A = (Q, T, δ, q0, F), kde
@@ Řádek 77: / Řádek 74: @@
     * konečný automat je dán:
-          o konečnou množinou vnitřních stavů Q
+      * konečnou množinou vnitřních stavů Q
-          o konečnou vstupní abecedou T
+      * konečnou vstupní abecedou T
-          o přechodovou funkcí δ, což je zobrazení:
+      * přechodovou funkcí δ, což je zobrazení:
-                + z Q × T do Q pro deterministický konečný automat
+          * z Q × T do Q pro deterministický konečný automat
-                + z Q × T do 2Q pro nedeterministický konečný automat
+          * z Q × T do 2Q pro nedeterministický konečný automat
-          o počátečním stavem q0
+      * počátečním stavem q0
-          o množinou koncových stavů F ⊆ Q
+      * množinou koncových stavů F ⊆ Q
     * přechodový diagram konečného automatu:
-          o orientovaný graf, ve které jsou uzly ohodnoceny stavy a hrany vstupními symboly
+      * orientovaný graf, ve které jsou uzly ohodnoceny stavy a hrany vstupními symboly
-          o z uzlu q vede hrana ohodnocená symbolem a do uzlu p, jestliže
+      * z uzlu q vede hrana ohodnocená symbolem a do uzlu p, jestliže
-                + p = δ(q, a) pro deterministický automat
+         * p = δ(q, a) pro deterministický automat
-                + p ∈ δ(q, a) pro nedeterministický automat
+         * p ∈ δ(q, a) pro nedeterministický automat
-          o počáteční stav označíme šipkou START
+      * počáteční stav označíme šipkou START
-          o uzly ohodnocené koncovými stavy označíme dvojitým kroužkem
+      * uzly ohodnocené koncovými stavy označíme dvojitým kroužkem
+===== Vztah mezi nimi =====
-Vztah mezi nimi
 Regulární gramatika generuje věty regulárního jazyka, konečný automat tyto věty přijímá (rozpoznává) - je formálním modelem procedury, jejímž vstupem je posloupnost symbolů a výstupem je odpověď, zda je vstup větou daného jazyka.
@@ Řádek 99: / Řádek 95: @@
     * k regulární gramatice lze vytvořit (nedeterministický) konečný automat
     * nedeterministický automat lze převést na deterministický
 Pozn:
@@ Řádek 107: / Řádek 102: @@
 Lexikální analyzátor je aplikací konečného automatu. Používá se jako první blok překladače, který čte vstupní text (program) a přemění jej na tok lexikálních elementů (tokens). Při tom vynechává nevýznamné mezery, konce řádků a komentáře. Jeho výstupem není boolská hodnota přijato/nepřijato, ale (většinou) hodnota typu integer nebo enum, která udává jaký lexikální element byl načten. Přikladem lexikálního elementu je číslo, identifikátor, if, =, := a pod. Základní rozdíly mezi konečným automatem (KA) a lexikálním analyzátorem (LA) jsou:
-. KA přečte celý zadaný vstupní řetězec a na jeho konci rozhodne (svým stavem), zda řetězec patří do daného jazyku. LA přečte pouze část řetězce (tj. LA je volán pro zadaný řetězec opakovaně nějakou vyšší vrstvou překladače) a vrací jaký jeden načtený lexikální element nalezl, případně chybu, pokud nenalezl (nerozpoznal) žádný.
+  - KA přečte celý zadaný vstupní řetězec a na jeho konci rozhodne (svým stavem), zda řetězec patří do daného jazyku. LA přečte pouze část řetězce (tj. LA je volán pro zadaný řetězec opakovaně nějakou vyšší vrstvou překladače) a vrací jaký jeden načtený lexikální element nalezl, případně chybu, pokud nenalezl (nerozpoznal) žádný.
+  - KA končí poté, co přečte celý svůj vstup. LA naproti tomu skončí čtení vstupu, pokud již nemůže provést žádný další přechod. Pokud byl LA v okamžiku, kdy již nemohl provést následující přechod v koncovém stavu, vrací "nalezen lexikalni element xxx" (kde xxx zaleží na tom, ve kterém z koncových stavů se LA nacházel), pokud v koncovém stavu nebyl, vrací chybu (nerozpoznaný žádný lexikální element, obvykle se to projeví chybou překladače "syntax error" nebo "unrecognized statement").
+  - LA přeskakuje komentáře a nevýznamné mezery.
+  - LA může provádět sémantické akce, počítat hodnoty atributů. Příkladem je lexikální element cislo, který míva atribut hodnota.
+  - LA může být spojen s preprocesorem, rozpoznávat bloky podmíněného překladu (#ifdef ... #endif ) a expandovat makra.
-. KA končí poté, co přečte celý svůj vstup. LA naproti tomu skončí čtení vstupu, pokud již nemůže provést žádný další přechod. Pokud byl LA v okamžiku, kdy již nemohl provést následující přechod v koncovém stavu, vrací "nalezen lexikalni element xxx" (kde xxx zaleží na tom, ve kterém z koncových stavů se LA nacházel), pokud v koncovém stavu nebyl, vrací chybu (nerozpoznaný žádný lexikální element, obvykle se to projeví chybou překladače "syntax error" nebo "unrecognized statement").
+Podobně jako KA, i LA můžeme realizovat pomocí tabulky přechodů nebo řídící struktury.
-. LA přeskakuje komentáře a nevýznamné mezery.
+===== Vytvoření konečného automatu z regulární gramatiky =====
-. LA může provádět sémantické akce, počítat hodnoty atributů. Příkladem je lexikální element cislo, který míva atribut hodnota.
-. LA může být spojen s preprocesorem, rozpoznávat bloky podmíněného překladu (#ifdef ... #endif ) a expandovat makra.
-Podobně jako KA, i LA můžeme realizovat pomocí tabulky přechodů nebo řídící struktury.
-[editovat]
-Vytvoření konečného automatu z regulární gramatiky
     * vstup = pravá regulární gramatika G = (N, T, P, S)
     * výstup = nedeterministický konečný automat M = (Q, T, δ, q0, F), pro který platí L(M) = L(G)
-. množina stavů Q = N ∪ {K}, K ∉ N
+   - množina stavů Q = N ∪ {K}, K ∉ N
-. vstupní abeceda automatu M je rovna množině terminálních symbolů T gramatiky G
+   - vstupní abeceda automatu M je rovna množině terminálních symbolů T gramatiky G
-. zobrazení δ sestrojíme takto:
+   - zobrazení δ sestrojíme takto:
-. je-li v P pravidlo A → aB, pak δ(A, a) obsahuje B
+         - je-li v P pravidlo A → aB, pak δ(A, a) obsahuje B
-. je-li v P pravidlo A → a, pak δ(A, a) obsahuje K
+         - je-li v P pravidlo A → a, pak δ(A, a) obsahuje K
-. q0 = S
+   - q0 = S
-. jestliže je v P pravidlo S → ε, pak F = {S, K}, jinak F = {K}
+   - jestliže je v P pravidlo S → ε, pak F = {S, K}, jinak F = {K}
-Převod nedeterministického konečného automatu na deterministický
+=====  Převod nedeterministického konečného automatu na deterministický =====
     * vstup = nedeterministický konečný automat M = (Q, T, δ, q0, F)
     * výstup = ekvivalentní deterministický konečný automat M' = (Q', T, δ', q0', F')
-. definujeme Q' = {{q0}}, stav {q0} považujeme za neoznačený
+   - definujeme Q' = {{q0}}, stav {q0} považujeme za neoznačený
-. jestliže v Q' jsou již všechny stavy označeny, pokračujeme krokem 4
+   - jestliže v Q' jsou již všechny stavy označeny, pokračujeme krokem 4
-. vybereme z Q' neoznačený stav q' a provedeme tyto operace:
+   - vybereme z Q' neoznačený stav q' a provedeme tyto operace:
-. definujeme přechodovou funkci δ'(q', a) pro všechna a ∈ T takto: δ'(q', a) = ∪δ(p, a) pro každý stav p ∈ q'
+         - definujeme přechodovou funkci δ'(q', a) pro všechna a ∈ T takto: δ'(q', a) = ∪δ(p, a) pro každý stav p ∈ q'
-. přidáme do Q' každý stav δ'(q', a), který v ní ještě není, a stav q' označíme
+         - přidáme do Q' každý stav δ'(q', a), který v ní ještě není, a stav q' označíme
-. pokračujeme krokem 2
+         - pokračujeme krokem 2
-. počáteční stav q0' je {q0}
+   - počáteční stav q0' je {q0}
-. množina koncových stavů F' je tvořena všemi stavy q', které obsahují alespoň jeden koncový stav q ∈ F
+   - množina koncových stavů F' je tvořena všemi stavy q', které obsahují alespoň jeden koncový stav q ∈ F

courses/a4m33pal/opakovani_pjp.1256155309.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru