[Teoria] Definizione di espressione regolare

[Fab996]

Non ho ben capito la definizione di espressione regolare. Dato un alfabeto $\Sigma$ ed un insieme di simboli ${+,\star,(,),\cdot,0}$ si definisce espressione regolare sull'alfabeto $\Sigma$ una stringa $r \in (\Sigma \cup {+,\star,(,),\cdot,0})^+$ tale che valga una delle condizioni $1) r=0$ $2) r \in \Sigma$ $3) r=(s+t) $o $r=(s\cdott) $o $r=s^\star$. Qualcuno potrebbe spiegarmela?

[killing_buddha]

Dato un insieme \(\Sigma\) di simboli, il monoide libero su \(\Sigma\) consta dell'insieme delle tuple
\[
\Sigma^\star = \coprod_{n\ge 0} \Sigma^n = \{(x_1,\dots, x_n)\mid x_i \in\Sigma,\; n\ge 0\}
\]con la convenzione che \(\Sigma^0=\{\varnothing\}\), dove \(\varnothing\) è la "parola vuota", che fa da elemento neutro per l'operazione di monoide (che è la giustapposizione di tuple: se \(\vec x_n = (x_1,\dots, x_n)\) e \(\vec y_m = (y_1,\dots, y_m)\) allora \(\vec x_n \circ \vec y_m := (x_1,\dots, x_n,y_1,\dots, y_m)\)). Questo insieme soddisfa la seguente proprietà universale: ogni funzione \(f : \Sigma \to M\), dove \(M\) è un monoide, si estende in maniera unica a un omomorfismo di monoidi \(\bar f : \Sigma^\star \to M\).

Ora, rozzamente, una espressione regolare serve a definire dei pattern per (ad esempio) compiere operazioni di cerca-e-sostituisci a un testo: a seconda del valore semantico di alcune wildcards, come il punto (trova un carattere qualsiasi), il caret (trova qualsiasi cosa diverso dal carattere o dal gruppo che segue), l'asterisco (trova \([0,\infty)\) occorrenze di ciò che precede) e altro, puoi quindi specificare di trovare non tanto "la parola autismo all'interno di un testo", ma (ad esempio con "aut.+o") tutte le parole che iniziano per aut e finiscono per o, tipo autismo e automobilismo. Ma non troverà "auto" perché aver scritto "aut.+o" dice trova qualsiasi parola che abbia la struttura aut-[almeno un carattere]-o. Per trovare anche auto avrei dovuto scrivere "aut.*o" (aut-[zero o più caratteri]-o)

Come si collegano le due cose? Semplice, dato un alfabeto \(\Sigma\), certi elementi di \(\Sigma^\star\) sono espressioni regolari "ben formate" (data la struttura generica di una regex, e in particolare dei modificatori è ovvio che non tutte ti vanno bene), e queste regole per stabilire se una regex è ben formata sono proprio quelle che riporti.



PS: Incidentalmente, ho dato in pasto a una regexp il testo che sto scrivendo prima di postarlo: ora non ricordo qual è il dialetto specifico che il mio editor utilizza, ma per groupare le espressioni matematiche tra i simboli backslash-tondaaperta e backslash-tondachiusa la matematica che mentre scrivo è rinchiusa tra dollari uso questa regexp:

Codice:

\\((.*?)\\) -> \\\(\1\\\)

In pratica sto dicendo: trova (pigramente) qualsiasi cosa sia contenuto tra simboli di dollaro, e salvalo in un registro: poi chiudi quello che hai salvato tra i delimitatori slash-tondaaperta e slash-tondachiusa che aprono e chiudono un ambiente matematico in TeX.

[Fab996]

Grazie, perché appunto conosco come utilizzare le regex, per esempio attraverso il comando grep, ma non avevo ben chiaro il nesso con il formalismo di espressione regolare. Mi potresti aiutare con questi esercizi, tenendo conto che la notazione da me utilizzata è $\varepsilon$ parola vuota, linguaggio vuoto $\Lambda \equiv \emptyset$? Gli esercizi sono, dire se le seguenti affermazioni sono vere o false $1)L(baa) \in L(a^(\star)b^(\star)a^(\star)b^(\star))$ e $2)L(\emptyset^(\star))=\emptyset$

[killing_buddha]

Cos'è $L(A)$?

[Fab996]

Indica il linguaggio rappresentato dall'espressione regolare $A$