Regulární výrazy, automaty s e-přechody

Regulární výrazy

Definice

• Množina regulárních výrazů (regular expressions) nad abecedou $\Sigma$, označovaná $RE(\Sigma )$, je definována induktivně takto:
  1. $ϵ,\varnothing$ a $a$ pro každé $a\in \Sigma$ je regulární výraz nad $\Sigma$ (tzv. základní regulární výrazy)
  2. Jsou-li $E$, $F$ regulární výrazy nad $\Sigma$, jsou také $(E.F),(E+F)$ a $(E{)}^{\ast }$ regulární výrazy nad $\Sigma$
  3. Každý regulární výraz vznikne po konečném počtu aplikací kroků $1$ a $2$

• Základní regulární výrazy se podobají symbolům, se kterými jsme se bězně setkávali. Tučně jsou zapsány proto, že je třeba je chápat jako symboly zcela nové; tyto “dvojníky” jsme zavedli proto, abychom mohli vždy snadno rozlišit mezi syntaxí a sémantikou regulárních výrazů.

• V regulárních výrazech se mohou vyskytovat také kulaté závorky jako metasymboly, které pomáhají vymezit rozsah operátorů. Abychom jejich použití omezili na minimum, přijmeme konvenci týkající se priority operátorů: Největší prioritu má "$\ast$", pak "$.$" a nakonec "$+$", přičemž “nadbytečné” závorky lze vypouštět.

• Každý regulární výraz $E$ nad abecedou $\Sigma$ popisuje (jednoznačně určuje) jazyk $L(E)$ nad abecedou $\Sigma$ (jazyk $L(E)$ je sémantikou regulárního výrazu $E$) podle těchto pravidel:

  • $L(a)=\{a\}$ pro každé $a\in \Sigma$
  • $L(ϵ)=\{ϵ\}$
  • $L(\varnothing )=\varnothing$
  • $L(E_1+E_2)=L(E_1)\cup L(E_2)$
  • $L(E_1.E_2)=L(E_1).L(E_2)$
  • $L(E^{\ast })=(L(E){)}^{\ast }$

Příklady

$L((a+b{)}^{\ast }(ab+bb)(a+b{)}^{\ast })=\{w\in (a,b{)}^{\ast }\mid w\text{ obsahuje podslovo }ab\text{ nebo }bb\}$ $L((aa+ab+ba+bb{)}^{\ast })=\{w\in \{a,b{\}}^{\ast }\mid w\text{ maˊ sudou deˊlku}\}$ $L((0^{\ast }{1}^{\ast }{2}^{\ast }{)}^{\ast })=\{0,1,2{\}}^{\ast }$

• Z výše řečeného se okamžitě nahlédne fakt, že jazyk je regulární nad $\Sigma$ právě když je popsatelný nějakým regulárním výrazem nad $\Sigma$.

• Nechť $E$ je regulární výraz. Pak existuje konečný automat rozpoznávající $L(E)$
• Nechť $L$ je akceptovaný nějakým (libovolným) DFA, pak $L$ je popsatelný nějakým regulárním výrazem.

Struktura převeditelnosti

Nedeterministický konečný automat s $ϵ$-přechody

• Model nedeterministického konečného automatu je možné dála rozšířit o tzv. $ϵ$-kroky. Automat pak může svůj stav za určitých okolností změnit samovolně. Tato schopnost je formálně popsána pomocí $ϵ$-kroků, které si lze na přechodových grafech představit jako hrany, jejichž návěštím je prázdné slovo. Přes tyto hrany může automat během výpočtu na slově $w$ měnit svůj stav bez toho, aby ze vstupu cokoliv přečetl - mezi přečtením dvou po sobě jdoucích symbolů z $w$ může provést libovolné konečné množství $ϵ$-přechodů

Příklad

• Následující automat s $ϵ$-kroky rozpoznává právě ta slova $w\in \{0,1{\}}^{\ast }$, která jsou tvaru $01^{k_1}01^{k_2}...01^{k_n}$, kde $n\ge 1$ a $k_i\ge 1$ pro každé $1\le i\le n$:

Definice

• Nedeterministický konečný automat s $ϵ$-přechody $M$ je uspořádaná pětice $M=(Q,\Sigma ,\delta ,q_0,F)$
  • $Q$ je neprázdná konečná množina stavů
  • $\Sigma$ je konečná množina vstupních symbolů, nazývaná také vstupní abeceda
  • $\delta$ je přechodová funkce ve tvaru $\delta :Q\times (\Sigma \cup \{ϵ\})\to 2^Q$
  • $q_0\in Q$ je počáteční stav
  • $F\subseteq Q$ je množina koncových/akceptujících stavů

• Rozšířenou přechodovou funkci $\hat{\delta }$ ovšem musíme definovat odlišným způsobem. Nejprve zavedeme funkci $D_{ϵ}:Q\to 2^Q$, která pro daný stav $p$ vrací množinu stavů, kterých může $M$ dosáhnout z $p$ bez toho, aby četl vstup.

• Pro dané $p\in Q$ je $D_{ϵ}(p)$ nejmenší množina $X\subseteq Q$ taková, že platí:

  • $p\in X$
  • Pokud $q\in X$ a $r\in \delta (q,ϵ)$, pak také $r\in X$.

• Funkci $D_{ϵ}$ je možné přirozeně rozšířit na množiny stavů: je-li $Y\subseteq Q$, položíme $D_{ϵ}(Y)={\cup }_{q\in Y}{D}_{ϵ}(q)$

• Nyní již můžeme definovat rozšířenou přechodovou funkci $\hat{\delta }:Q\times {\Sigma }^{\ast }\to 2^Q$ takto:

  • $\hat{\delta }(q,ϵ)=D_{ϵ}(q)$
  • $\hat{\delta }(q,wa)={\cup }_{p\in \hat{\delta }(q,w)}{D}_{ϵ}(\delta (p,a))$

• Jazyk přijímaný $M$ s $ϵ$-přechody je definován takto: $L(M)=\{w\in {\Sigma }^{\ast }\mid \hat{\delta }(q_0,w)\cap F\ne 0\}$

• Ke každému NFA s $ϵ$-přechody existuje ekvivalentní NFA (bez $ϵ$-přechodů)

Navigace

Předchozí: Konečné automaty deterministické a nedeterministické Následující: Minimalizace konečného deterministického automatu Celý okruh: 1. Teoretické základy informatiky