Greibachové NF

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Greibachové NF

Příspěvek od Necroman »

Pokud také nerozumíte převodu na GNF, tak doporučuji tento postup, vypadá celkem pohodově:tady
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Greibachové NF

Příspěvek od Him »

Podle slajdu Bartaka jsem si to zkusil a nezda se mi to tak tezke, ale bez vyzkouseni se to spatne pamatuje..

Kód: Vybrat vše

Krok 1] Prepis pravidel podle oznaceni:

A1 ~ E
A2 ~ T
A3 ~ F

A1 -> A1+A2   -- v kroku 2 odstranim levou rekurzi
A1 -> A2

A2 -> A2+A3   -- v kroku 2 odstranim levou rekurzi
A2 -> A3

A3 -> (A1)
A3 -> a


Krok 2] 

A1 -> A2     -- neni v poradku pro treti krok
A1 -> A2Z1   -- neni v poradku pro treti krok
Z1 -> +A2 | +A2Z1

A2 -> A3      -- neni v poradku pro treti krok
A2 -> A3Z2    -- neni v poradku pro treti krok
Z2 -> *A3 | *A3Z2

A3 -> (A1)    -- pro treti krok v poradku
A3 -> a       --        -||-


Krok 3]

A3 -> a
A3 -> (A1)

A2 -> (A1)
A2 -> (A1)Z2
A2 -> a
A2 -> aZ2

A1 -> (A1)
A1 -> a
A1 -> (A1)Z2
A1 -> AZ2

A1 -> (A1)Z1
A1 -> aZ1
A1 -> (A1)Z2Z1
A1 -> AZ2Z1

Z1 -> +A2 | +A2Z1  -- je v poradku pro krok 4
Z2 -> *A3 | *A3Z2  -- je v poradku pro krok 4

Krok 4]

  -- nic neni potreba delat

Krok 5]

  Provede se tak, ze vzdy pro terminal, ktery nam kazi nejake pravidlo vytvorime nove pravidlo:  X -> x  (novy neterminal X pro terminal x)
  
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“