3. Espressioni regolari e Linguaggi non regolari

Nella teoria della computazione vi sono alcune espressioni volte a descrivere in maniera più lineare gli automi. Queste prendono il nome di espressioni regolari, nelle quali si usano gli stessi operatori algebrici. Il risultato di un'espressione regoalare è un linguaggio. La domanda principale che ci poniamo è relativa alle loro applicazioni. Le espressioni regolari hanno un ruolo fondamentale nelle applicazioni dell'informatica, soprattutto nelle applicazioni che coinvolgono testi. Un esempio di espressione regolare consiste in: (0 $\cup$ 1)*, la quale rappresenta il linguaggio contenente tutte le possibili stringhe di simboli 0 e 1.

Se volessimo dare una definizione formale di espressione regolare, possiamo definire R come espressione regolare se essa è:

• a per qualche a nell'alfabeto $\sum$
• $\epsilon$
• $\emptyset$
• ($R_1$ $\cup$$R_2$), dove $R_1$ ed $R_2$ sono espressioni regolari
• ($R_1$ $\circ$$R_2$), dove $R_1$ ed $R_2$ sono espressioni regolari
• ($R_1$*), dove $R_1$ è un'espressione regolare

Nei primi 2 punti vengono rappresentate le espressioni regolari relative ai linguaggi {a} e {$\epsilon$}, la terza espressione regolare rappresenta il linguaggio vuoto. Mentre nei restanti punti, le espressioni regolari indicano i linguaggi ottenuti attraverso l'unione o la concatenazione dei linguaggi $R_1$ e $R_2$ o tramite l'operazione star del linguaggio $R_1$. Da non confondere le due espressioni $\epsilon$ con $\emptyset$, in quanto la prima rappresenta il linguaggio che contiene solo la lingua vuota, mentre la seconda rappresenta il linguaggio che non contiene alcuna stringa. Per comodità si indica con R* il linguaggio che contiene tutte le stringhe date dalla concatenazione di o più stringhe di R, mentre con $R^+$ si indica il linguaggio che contiene tutte le stringhe date dalla concatenazione di 1 o più stringhe di R.

Possiamo definire alcune proprietà:

$R^+$ $\cup$ $\epsilon$ = R*

L'unione del linguaggio che contiene tutte le stringhe con una lunghezza minima di 1, unito al linguaggio composto solo dalla stringa vuota genera R*

R $\cup$ $\emptyset$ = R

Se si aggiunge il linguaggio vuoto a un qualsiasi linguaggio, si ottiene il linguaggio di partenza

R $\circ$ $\epsilon$ = R

Concatenare la stringa vuota a una qualsiasi stringa non ne altera il valore o significato

R $\cup$ $\epsilon$ $\ne$ R

Questa affermazione si può semplicemente dimostrare attraverso un esempio logico: se R = 0, allora L(R) = {0} ma L(R $\cup$ $\epsilon$) = {0, $\epsilon$}

R $\circ$ $\emptyset$ $\ne$ R

Questa affermazione si può semplicemente dimostrare attraverso un esempio logico: se R = 0, allora L(R) = {0} ma L(R $\circ$ $\emptyset$) = $\emptyset$

Le espressioni regolari e gli automi finiti sono equivalenti rispetto alla loro potenza descrittiva, inoltre un automa può essere convertito in espressione regolare e viceversa. Possiamo enunciare il teorema di equivalenza tra automi finiti ed espressioni regolari: "Un linguaggio è regolare se e solo se qualche espressione regolare lo descrive".

Possiamo definire un automa finito non deterministico generalizzato come un automa che ha sugli archi delle espressioni regolari come funzioni di transizione. Possiamo definire formalmente questo tipo di automa attraverso una quintupla $(Q, \sum, \delta, q_{start}, q_{accept})$, nella quale Q è l'insieme finito degli stati, $\sum$ è l'alfabeto di input,$\delta: ( Q -$ { $q_{accept}$) $\times$ (Q - {$q_{start}$}) $\rightarrow$ R è la funzione di transizione,$q_{start}$ rappresenta lo stato iniziale e $q_{accept}$ rappresenta lo stato accettante.

La computazione di questo automa è simile agli altri. Un GNFA accetta una stringa w in $\sum*$ se w = $w_1w_2 \dots w_k$ dove ogni $w_i$ è in $\sum*$ ed esiste una sequenza di stati $q_1, q_2, \dots , q_k$, tale che $q_0 = q_{start}$, ovvero lo stato iniziale, $q_k = q_{accept}$, ovvero lo stato accettante, e per ogni i risulta che $w_i \in L(R_i)$, dove $R_i = \delta (q_{i-1},q_i)$ ovvero $R_i$ è l'espressione presente sull'arco da $q_{i-1}$ a $q_i$

Tutte le tipologie di automi finiti hanno dei limiti per i quali non riconoscono alcuni tipi di linguaggi definiti linguaggi non regolari. Per dimostrare che un linguaggio non è regolare si può seguire il teorema del pumping lemma. Questo teorema suggerisce che tutti i linguaggi regolari le stringhe possono essere replicate se la loro lunghezza raggiunge almeno uno specifico valore, definito lunghezza del pumping. Quindi le parole dei linguaggi che rispettano questa regola contengono una parte che può essere ripetuta un numero qualsiasi di volte, ottenendo sempre un'altra stringa che appartiene al linguaggio. Enunciamo il teorema come:

Pumping Lemma

Se A è un linguaggio regolare, allora esiste un numero p, denominato lunghezza del pumping, tale che se s è una qualsiasi stringa in A di lunghezza almeno p, allora s può essere divisa in tre parti: s=xyz, che soddisfano le seguenti condizioni:

• per ogni $i \geq 0, xy^iz \in A$
• |y|$> 0$
• |xy|$\leq$ p

Quando dividiamo la stringa s in tre parti xyz, x o z possono essere $\epsilon$, mentre per la seconda condizione y deve essere diversa da $\epsilon$. La terza condizione afferma che prendendo in considerazione x e y insieme hanno una lunghezza al più p. Per dimostrare questo teorema definiamo un DFA M = $(Q,\sum,\delta,q_1,F)$ che riconosce il linguaggio A, mentre con p indichiamo il numero di stati di M. Sia s = $s_1s_2 \dots s_n$ una stringa appartenete al linguaggio A di lunghezza n, con $n \geq p$. Sia inoltre $r_1, \dots , r_{n+1}$ la sequenza di stati attraversati da M mentre viene elaborata la stringa s, si ha $r_{i+1} = \delta (r_i,s_i)$per 1 $1 \leq i \leq n$. Questa sequenza ha una lunghezza pari a n + 1, ovvero di almeno p + 1. All'interno della sequenza vi è uno o più stati che vengono ripetuti più volte, secondo il principio della piccionaia.

Denominando il primo stato come $r_j$ e il secondo come $r_l$. Notiamo come $r_l$ si presenta nelle prime p+1 posizioni in una sequenza che inizia in $r_l$, abbiamo quindi $l \leq p+1$. Ora definiamo x, y, z come: x=$s_1 \dots s_{j-1}$, y=$s_j \dots s_{l-1}$ e z=x=$s_l \dots s_{n}$. Verifichiamo adesso che M accetti $xy^iz$ per ogni $i \geq 0$. Sappiamo che $j \ne l$ e quindi |y| > 0; e $l \leq p + 1$, perciò |xy|$\leq$p. Quindi tutte le condizioni sono rispettate.

Per usare il pumping lemma per provare che un linguaggio B non è regolare, in primo luogo si assume che B sia regolare per ottenere una contraddizione. Successivamente si usa il pumping lemma per assicurare l'esistenza di una lunghezza del pumping p tale che tutte le stringhe di lunghezza maggiore o uguale a p in B possano essere iterate. In seguito occorre trovare una stringa s in B che ha una lunghezza maggiore o uguale a p, ma che non può essere iterata. Infine bisogna dimostrare che s non può essere iterata considerando tutti i modi di dividerla e per ogni divisione trovando un valore di i tale che $xy^iz \notin B$.