Matematické Fórum

↑ honzapeklo:

Komu a za jakým účelem bychom to měli detailně popisovat?

Nevím, nakolik je to detailně - ale srozumitelné to je:

http://www1.osu.cz/home/habibal/dizerta … /popis.pdf

https://akela.mendelu.cz/~xhaluza/tpj/l … tiky_I.pdf

Můžeš sem umisťovat své návrhy, pokud máš zájem konzultovat.

↑ Galat:

Zdravím :-)

použijí odkaz kolegy Kondra: http://is.muni.cz/elportal/estud/fi/js0 … maty_I.pdf - od str. 36 originálu (na závěr kapitoly je algoritmus a výsledek odstranění)

↑ honzapeklo:Koukám že se někdo inspiroval Jamesem Joycem :) Ale dobře, nebavme se o stylistice ...

Řekněme, že máme automat se stavy 1,2,3,4, z 1 do 2 vede ε-přechod, z 2 se načtením symbolu a dostaneme do 3 a z 3 vede ε-přechod do 4. Ty ε-přechody umožňují automatu, aby když je ve stavu 1 a chystá se načíst symbol a, udělal nejdříve ε-přechod do 2, pak načetl a a přesunul se tak do 3 a následně se ε-přechodem přesunul do 4. Automat má tedy možnost se načtením a-čka přesunout z 1 do 3 nebo 4. Abychom mohli odstranit ε-přechody, musíme do automatu přidat přechody 1,3 a 1,4. Tím jsme vyřešili to, že se automat bez ε-přechodů bude chovat stejně jao zadaný, pokud bude začínat ve stavu 1 a načte symbol a. To samé musíme provést pro všechny stavy a symboly. Algoritmus tedy lze popsat takto:

A)Pro každý stav q a každý symbol s
  1) sestavíme množinu A stavů, do kterých se z q dostaneme libovolným počtem ε-přechodů
  2) sestavíme množinu B stavů, do kterých se dostaneme naštením symbolu s z některého stavu v A
  3) sestavíme množinu C stavů, do kterých se dostaneme libovolným počtem ε-přechodů z některého stavu v B
  4) přidáme přechody z q do všech stavů v C
B) Upravíme množinu přijímajících stavů: pokud je možné z počátečního stavu se libovolným počtem ε-přechodů přesunout do přijímajícího, nastavíme počáteční jako přijímající. U stavů  kromě počátečního není nutné provádět změnu: přijímající v novém automatu mohou být pouze ty stavy q', ze kterých se v původním automatu do přijímajícího dalo přesunout libovolným počtem ε-přechodů. Díky předchozí změně  přechodové funkce ale platí, že pokud vede do takového stavu q' přechod symbolem s' ze stavu q'', pak vede přechod z q'' symbolem s' přímo do stavu přijímajícího.
C) Odstraníme ε-přechody