🖥️ Wiki

❯

Interdisciplinare

❯

espressioni regolari (regex)

espressioni regolari (regex)

05 ott 20262 minuti

È l’equivalente delle espressioni algebriche per le stringhe:

Esempio: $(0 \cup 1) 0^{⋆}$ su $ε = {0, 1}$

{(0 \cup 1) ⟹ {0} \cup {1} = {0, 1}^{⋆} ⟹ {0}^{⋆} ⟶ (0 \cup 1) 0^{⋆} ⟹ {0, 1} \circ 0^{⋆}

Un’espressione regolare è definita induttivamente come:

re (Σ) = ⎩ ⎨ ⎧ caso base caso induttivo ⎩ ⎨ ⎧ \emptyset \in re (Σ) ε \in re (Σ) a \in re (Σ), 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 (Σ)

dove $ε$ è la stringa vuota.

Ad ogni $re (Σ)$ corrisponde un linguaggio $L (v)$ :

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

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

Data $r \in re (Σ)$ , voglio costruire un automa 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)

Vista grafico

Link entranti

Automi calcolabilità e complessità

Creato con Quartz v4.4.0 © 2026

GitHub
Discord Community