Jan Černý

Úkol 02 - 21. 10. 2022

Zadání

Navrhněte bezkontextovou gramatiku pro následující bezkontextové jazyky:

  1. (0,4 bodu) Navrhněte konečný automat pro následující regulární jazyk:
  2. (0,5 bodu) Pro následující konečný automat vytvořte ekvivalentní minimální deterministický konečný automat . Popište svůj postup a pokud má více kroků, ukažte všechny mezivýsledky.
    , kde :
  1. (0,1 bodu) Všimněte si, že je NKA s -přechody a více počátečními stavy. Takový automat nebyl na přednášce oficiálně zaveden. Má však stejnou výpočetní sílu jako ostatní typy konečných automatů (tj. též rozpoznává právě třídu regulárních jazyků). Zdůvodněte proč.

Řešení

Úkol 1

  • Regulární jazyk generuje řetězce ve tvaru , kde a mají délku přesně 2 znaky a zároveň a nejsou stejné
  • Pokud obsahuje méně než 2 symboly (tedy 0 nebo 1), musí být nebo , a naopak
  • Mezi nimi (řetězec ) může být libovolný (i nulový) počet symbolů
  • Přípustné jsou tedy jen tyto kombinace:
Začátek () Střed () Konec ()
  • , kde :

../../Attachments/fsm-eliska02-svg.svg

Poznámka
  • Moje pojmenování stavů je asi poněkud nestardardní, proto bych ho rád vysvětlil
  • Názvy a jsem si značil, že po příchodu do tohoto stavu začíná řetězec symbolem nebo , podtržítko tedy značí zbytek řetězce
  • Názvy a jsem si značil, že po odchodu z tohoto stavu má řetězec končit symboly , nebo
  • Názvy a jsem si značil, že po odchodu z tohoto stavu má řetězec končit symbolem nebo

Úkol 2

Postup:

  1. Odstraním -přechody s pomocí -closure
  2. Vznikne mi NKA s více počátečními stavy
  3. Převedu determinizací na DKA (zároveň se tím zbavím nedosažitelných a neužitečných stavů)
  4. Minimalizuji hledáním ekvivalentních stavů

1. Odstranění -přechodů

  • Vytvořím si sloupeček -closure
-closure
  • Pomocí něj doplním přechody do automatu již bez -přechodů

2. Převod na DKA

  • Díky determinizaci se zbavím i nedosažitelných a neužitečných stavů, které by bylo jinak potřeba odstranit před minimalizací

3. Minimalizace

  • Hledání ekvivalentních stavů
Poznámka pro Elišku

Tak už jsem objevil první nedostatek Obsidianu😅 Jelikož je renderovaný pomocí MathJaxu (který neumí \begin{tabular}), musel jsem využít tabulky formátované v Markdownu. Nepodařilo se mi tak v nich bohužel nijak zvýraznit/zdvojit čáry mezi sloupečky různých kroků :))

  • Výsledný automat bude tedy vypadat takto
  • , kde :

../../Attachments/fsm-eliska02-2-svg.svg

Úkol 3

  • Pokud máme NKA s -přechody, není potřeba mít více počátečních stavů
  • Počáteční stavy lze nahradit pouze jedním počátečním stavem, a z něj vést -přechody do "původních" počátečních stavů
  • Tím jsme automat převedli na NKA s -přechody a jedním počátečním stavem, který známe z přednášky

../../Attachments/fsm-eliska02-3-svg.svg

  • Opět lze u takového automatu odstranit -přechody, determinizovat a minimalizovat
  • Výsledné automaty jsou ekvivalentní