share: true
aliases:
  - AAG 1
complete: true
author: Jan

Regulární jazyky

BI-SPOL.21-1

Regulární jazyky:

Deterministické a nedeterministické konečné automaty.
Determinizace konečného automatu.
Minimalizace deterministického konečného automatu.
Operace s konečnými automaty.
Regulární gramatiky, regulární výrazy, regulární rovnice.

Regulární jazyk

Je to formální jazyk, který lze přijmout konečným automatem (NKA i DKA)
Je to formální jazyk, který lze popsat regulárním výrazem
Je to formální jazyk, který lze generovat regulární gramatikou

../../Attachments/Pasted image 20221011221811.png

#veta Kleeneova věta

Libovolný jazyk je regulární, právě když je přijímaný konečným automatem

Příklady regulárních jazyků:

$ř ě$

Deterministický konečný automat (DKA)

Je jasně určeno, jak se automat bude chovat, jaký bude další stav, patří do regulárních jazyků.

#definice Deterministický konečný automat je pětice

- konečná množina vnitřních stavů
- konečná vstupní abeceda
- zobrazení
- počáteční stav
- množina koncových stavů

Konfigurace konečného automatu je
- počáteční -
- dvojice (dvojice stavu a zbytku vstupního řetězce)
- koncová - , kde (tedy je koncový stav, zbylý řetězec je prázdný)
Přechod je relace nad taková, že
- kde je symbol abecedy, podle kterého přecházíme, tedy
- cílový stav

Připomenutí operátorů nad abecedou

- množina všech neprázdných řetězců nad

- množina všech řetězců nad , tedy včetně prázdného řetězce

Nedeterministický konečný automat (NKA)

Není jasně určeno, do které z následujících stavů půjde
Může mít více přechodů pro jeden stejný symbol
Často se využívá pro vytvoření návrhu algoritmů, protože vytvoření stavů je intuitivnější než u DKA

#definice Nedeterministický konečný automat je pětice

- zobrazení z do množiny všech podmnožin (značíme )
(zbytek symbolů stejný jako u DKA)

Stav je dosažitelný, pokud existuje řetězec takový, že existuje posloupnost přechodů z počátečního do
Stav je užitečný, pokud existuje řetězec takový, že existuje posloupnost přechodů z do koncového

Determinizace NKA

Vstup: NKA
Výstup: DKA takový, že (přijímá stejný jazyk)

Každý NKA lze převést do nějakého DKA (ten ale často může mít více stavů)
- Pokud má NKA stavů, DKA může mít až stavů
- Časová složitost tohoto algoritmu je tedy
Nový stav v DKA je tedy vlastně skupina (množina) původních stavů

Algoritmus:

Výsledný DKA má stejnou abecedu jako vstupní NKA
(Počáteční stav NKA zabalíme do množiny. Počátečním stavem DKA je tedy jednoprvková množina)
(Přidáme nový stav do množiny všech stavů, postupně ji budeme naplňovat)
Pro každý symbol najdeme podmnožinu stavů , do nichž automat přejde z počátečního stavu na symbol
1. Pokud , pak přidáme do . a označíme jako "nezpracovanou"
2. Zároveň nastavíme přechod
Procházíme všechny "nezpracované" množiny :
1. Pro každý symbol (Tedy všechny původní cílové stavy sjednotíme do nového "sjednoceného" stavu)
2. Pokud výsledná množina , pak ji do přidáme a označíme jako "nezpracovanou"
3. Aktuální označíme jako "zpracovanou"
Stav označíme jako koncový právě tehdy, když (tedy pokud nějaký "podstav" byl koncový i v původním NKA)

../../Attachments/Pasted image 20260528141830.png

Minimalizace DKA

Vstup: DKA
Výstup: DKA ekvivalentní s

Postup:

Odstranění nedosažitelných stavů
Odstranění zbytečných stavů
Sloučení ekvivalentních stavů
1. Rozdělíme stavy do dvou tříd na koncové/nekoncové
2. Dívám se, jestli se stavy v jedné třídě přecházejí do stejného cíle na stejný vstupní znak
3. Pokud ne, rozdělím je do více tříd a znovu testuji přechody a rozděluji
4. Až se rozdělování zastaví, zbyly už jen ekvivalentní stavy

Hledání ekvivalentních stavů:

Výsledný automat je:

Operace s konečnými automaty

Jazykové operace

Kombinují dva automaty (nebo upravují jeden), aby nový automat uměl pracovat s kombinací jejich slov

Sjednocení jazyků - Výsledný automat přijímá jak jazyk A, tak jazyk B
Průnik jazyků - Výsledný automat přijímá pouze slova, která splňují podmínky obou automatů A i B zároveň
Doplněk jazyka - Otočení funkce automatu -- to, co doteď přijímal, bude zamítat, a naopak (v praxi prohození koncových/nekoncových stavů)
Součin jazyků (zřetězení) - Slovo se skládá ze dvou částí -- tam kde jeden automat skončil (koncový stav), musí ten druhý začít (počáteční stav)
Iterace jazyka (Kleene star) - Umožňuje slovo opakovat libovolněkrát za sebou

Strukturální operace

Neměníme to, jaká slova automat přijímá, ale pouze jeho vnitřní strukturu

Odstranění více počátečních stavů
Odstranění nedosažitelných či zbytečných stavů
Odstranění epsilon-přechodů
Determinizace
Minimalizace
Převod na úplně určený automat

Regulární gramatiky

Gramatika, Klasifikace gramatik

(univerzální definice jako u bezkontextové gramatiky)

#definice Gramatika je uspořádaná čtveřice

, kde:

- konečná množina neterminálů
též - konečná množina terminálů
- množina přepisovacích pravidel
- počáteční symbol (neterminál) gramatiky (též větný/startovací symbol)
Je to formalismus pro generování jazyka

#definice Gramatika je regulární, jestliže každé pravidlo má tvar

nebo , kde (neterminály) a (terminál)
a zároveň není na pravé straně žádného z pravidel

Regulární výrazy

#definice Regulární výraz

Regulární výraz nad abecedou je definován tímto způsobem:

jsou RV pro všechna
Jsou-li RV nad , pak i následující jsou RV nad :
1. sjednocení, alternativa
2. zřetězení (nebo bez tečky jen )
3. iterace

#definice Hodnota regulárního výrazu

Hodnota regulárního výrazu je jazyk, který daný regulární výraz reprezentuje.

Regulární rovnice

Matematický nástroj k převodu konečného automatu na regulární výraz.

Protože zřetězení (operátor tečka) není komutativní, rozdělujeme na levé a pravé regulární rovnice:

Levá: Neznámý RV se vyskytuje v zřetězení vždy nalevo od známých RV
Pravá: Neznámý RV se vyskytuje v zřetězení vždy napravo od známých RV

Např. následující regulární rovnice s neznámou nad abecedou je pravá

Řešení regulárních rovnic

Nechť jsou RV, pak platí:

(levá regulární rovnice)
(pravá regulární rovnice)
*pozn. je rekurentní člen, je ukončovací člen

Vysvětlení pravých regulární rovnic na konečném automatu:

Mějme rovnici
- Původní je označeno jak stav
- Rekurentní člen je symbol abecedy
- Ukončovací člen je prázdný symbol
Tedy do stavu (levá strana před rovnítkem) se dostanu
- přes symbol ze stavu
- nebo (operátor +) nedělám nic a ukončím () (proto označíme stav i jako koncový)
Lze tedy rovnici i zjednodušit přes operátor iterace jako

Převod konečného automatu na RV

Máme dvě metody:

Metoda levých regulární rovnic (příchozí přechody)
Metoda pravých regulárních rovnic (odchodí přechody)

../../Attachments/Pasted image 20260531094201.png

Vytvořeno: 2. 6. 2026, 11:21
Poslední aktualizace: 9. 6. 2026, 12:17