Sono le espressioni di un’algebra dei linguaggi, la quale supporta le operazioni chiuse $\cup, \circ$ (binarie) e $⋆$ (unaria).

$R$ è un’espressione regolare ( $R \in re (Σ)$ ) se (induttivamente):

R = ⎩ ⎨ ⎧ caso base caso induttivo ⎩ ⎨ ⎧ \emptyset ε a, a \in Σ ⎩ ⎨ ⎧ R_{1} \cup R_{2}, R_{1}, R_{2} \in re (Σ) R_{1} \circ R_{2}, R_{1}, R_{2} \in re (Σ) R_{1}^{⋆}, R_{1} \in re (Σ)

N.B.: $ε$ è la stringa vuota e $\emptyset$ è il linguaggio vuoto.

Ogni regex $R \in re (Σ)$ restituisce in output un linguaggio $L (R)$ :

L (R) = ⎩ ⎨ ⎧ caso base caso induttivo ⎩ ⎨ ⎧ \emptyset se R = \emptyset ε se R = {ε} {a} se R = {a} ⎩ ⎨ ⎧ L (R_{1}) \cup L (R_{2}) se R = R_{1} \cup R_{2} L (R_{1}) \circ L (R_{2}) se R = R_{1} \circ R_{2} L (R_{1}^{⋆}) se R = R_{1}^{⋆}

Esempio

(0 \circ (0 \cup 1)^{⋆}) \cup ((0 \cup 1)^{⋆} \circ 1)

Valutazione:

$0 \cup 1 = {0, 1}$
$(0 \cup 1)^{⋆} = {0, 1}^{⋆} = {0, 1, 00, 10, 01, 11, \dots}$
$0 \circ (0 \cup 1)^{⋆} = {00, 01, 000, 010, 001, 011, \dots}$
$(0 \cup 1)^{⋆} \circ 1 = {01, 11, 001, 101, 011, 111, \dots}$
$(0 \circ (0 \cup 1)^{⋆}) \cup ((0 \cup 1)^{⋆} \circ 1) = {00, 01, 01, 11, 000, 001, 010, 101, 001, 011, 011, 111, \dots}$

Teorema: un linguaggio è regolare $⟺$ esiste un’espressione regolare che lo descrive

Teorema: Ogni espressione regolare può essere convertita nell’automa deterministico a stati finiti (DFA) che riconosce il linguaggio che essa descrive e viceversa. Quindi un linguaggio è regolare se e solo se esiste una regex che lo descrive.

todo pag. 67

Primo passo

Data $r \in re (Σ)$ , voglio costruire un automa deterministico a stati finiti (DFA) o un automa non deterministico a stati finiti (NFA) $N$ tale che $L (r) = L (N)$ .

Usiamo la ricorsione:

caso base ⎩ ⎨ ⎧ r = a \in Σ start \to ◯ \to a ∙ r = ε start \to ∙ r = \emptyset start \to ◯

Per induzione,

R_{1} \cup R_{2} ⟹ \exists DFA/NFA M_{1}, M_{2} : R_{1} \circ R_{2} \land L (R_{1}) = L (M_{1}) \land L (R_{2}) = M_{2} ⟹ \exists DFA/NFA M tale che L (M) = L (r)

todo continua

Secondo passo

Da $M$ definiamo un GNFA equivalente… todo continua

Definiamo il Generic Non deterministic Finite state Automaton (GNFA) canonico

🖥️ Wiki

Esplora

espressioni regolari (regex)

Esempio

Teorema: un linguaggio è regolare $⟺$ esiste un’espressione regolare che lo descrive

Primo passo

Secondo passo

Vista grafico

Tabella dei contenuti

Link entranti

🖥️ Wiki

Esplora

espressioni regolari (regex)

Esempio

Teorema: un linguaggio è regolare ⟺ esiste un’espressione regolare che lo descrive

Primo passo

Secondo passo

Vista grafico

Tabella dei contenuti

Link entranti

Teorema: un linguaggio è regolare $⟺$ esiste un’espressione regolare che lo descrive