Please enable JavaScript.

Coggle requires JavaScript to display documents.

12. Formální jazyky II (Bezkontextové jazyky (CFG (čtveřice (N, Σ, P, S),…

- - - - rozdíl od PDA - čte 0-n vrchních symbolů
  - - - Σ - kon. množ. terminálů, N ∩ Σ = nic, N U Σ = V
      - P - kon. množ. pravidel, P z VNV x V*
      - N - nepr. kon. množ. neterminálů
      - S z N - poč. neterminál
    - - S -> SS | (S) | e
    - - Chomského NF (CNF)
        
        bez e-pravidel
        
        každé pravidlo: A -> BC (B, C - net.) | A -> a (a - term.) | S -> e
        
        každý CFL jde generovat CFG v CNF
        
        postup
        
        X -> ABC ==> X -> A<BC>, <BC> -> BC
        
        X -> aC ==> X -> <a>C, <a> -> a
      - Greibachova NF
    - - CFG bez e-pravidel
        
        S -> e OK
      - CFG bez jednoduchých pravidel
        
        jednoduchá pr: A -> B
      - redukované CFG
        
        neobsahuje nepoužitelné symboly (typu I, II)
      - CFG bez levé rekurze
- - - - NPDA je značně silnější než PDA
    - - přijímaný jazyk L(M)
        
        právě všechna slova, pod kterými dojde automat z poč. stavu do některého z koncových (přijímá stavem) nebo všemi slovy, kde PDA vyprázdní zásobník (přij. práz. zás.)
        
        ekvivalentní, jde převádět
      - převody - ekvivalence
    - - může z vrcholu vybrat více než 1 symbol/žádný
      - δ: Q x Σe x Γ -> 2^(Q x Γ)
      - ke každému existuje ekviv. PDA
    - - ani při čtení ani pro e-krok neexistuje více než 1 varianta pokračování
- - - - přidám S, k pravidlům přidám přechod S -> S1S2
    - - S, S -> SS1 | e
    - - sjednotím stavy, přidám nové S, S -> S1, S -> S2
    - - S, S -> SS1 | S1
- - - - pravidla - čtecí (δ(q, x, x) = {(q, e)}) + nečtecí (δ(q, e, Q) = {(q, přechod)})
      - libovolný der. strom slova
      - sestrojíme PDA, který provádí synt. analýzu (+ akceptace)
      - podle stromu apl. pravidla PDA (q, slovo, S) |-- (q, slovo, novystav) |-- (q, bez pismena, bez pismena) |--... |-- (q, e, e)
      - PDA slovo akceptume --> gramatika ho generuje
  - - - pravidla - čtecí (δ(q, x, e) = {(q, x)}) + nečtecí (δ(q, e, přechod) = {(q, Q)})
      - lib. derivační strom
      - sestrojíme PDA provádějící synt. snalýzu (+ akceptace)
      - podle stromu aplikujeme pravidla PDA (q, slovo, _) |-- postupně načítám dorpava, měním podle přechodů, ...|-- (r, e e) - akc. koncovým stavem
      - PDA slovo akceptume --> gramatika ho generuje