Regulære Udtryk

Regulære udtryk og NFA'er er ækvivalente.

Man taler om regulære udtryk over et alfabet.

Basis-udtryk

Regulært udtryk R	Sproget betegnet af R, L(R)
a $[a\in \Sigma]$	{a}
Ø	{}
$\varepsilon$	{$\varepsilon$}

Sammensatte udtryk

Regulært udtryk R	Sproget betegnet af R, L(R)
$(R_1\cup R_2)$	$L(R_1) \cup L(R_2)$
$(R_1 \circ R_2)$	$L(R_1) \circ L(R_2)$
$R^*$	$L(R)^*$

Regulære Udtryk er Ækvivalente med NFA'er

Eksempel: $$ (aa \space \cup \space b)^* $$ Kan tegnes som NFA:

Og som vi så i Lektion 2, så kan en NFA skrives om til en DFA.

Generaliseret NFA (GNFA)

Definition:

En GNFA er en 5-tupel

​ $(Q, \Sigma,q_{start},q_{accept},\delta)$

Q: mængde af tilstande

$\Sigma$: input alfabet

$q_{start}$: starttilstand $q_{start} \in Q$

$q_{accept}$: accepttilstand $q_{accept} \in Q$

$\delta$: Skal over en "bordskik"

Bordskik:

• Én transition mellem hvert par af tilstande, dog
• Ingen transitioner fra $q_{accept}$
• Ingen transition til $q_{start}$
• Regulære udtryk på transitionerne.

Eksempel

Konstruer Regulært Udtryk ud fra GNFA

Fjern tilstande i G én efter én og opdater.

Til sidst har vi 2 tilstande med et regulært udtryk mellem.

Fjerne tilstande

• Må ikke være $q_{start}$ eller $q_{accept}$
• Kald den tilstand vi fjerne $q_{rip}$

Opdatere transitioner

Før og efter

• For hvert par $q_i,q_j \neq q_{rip}$ lav denne opdatering

Algoritme

$\text{CONVERT}(G)=$

1. Lad mængden af tilstande i $G$ være $Q_G$.

   Hvis $Q_G =\{q_{start}, q_{accept}\}$ så stop.

   Returner $R$, hvor:

1. Ellers vælg $q_{rip} \notin \{q_{start}, q_{accept}\}$

2. For hvert par $(q_i, q_j)$ opdatér transitioner som vist ovenfor.

   Kald ny GNFA for $G'$.

   $Q_{G'}=Q_G \smallsetminus \{q_{rip}\}$

3. $\text{CONVERT}(G')$

---

Last update: June 11, 2019