linguaggio regolare

Classe REG dei linguaggi

Un linguaggio è regolare se esiste un macchina a stati finiti che ne riconosce tutte le stringhe.

$$\text{REG}=\{L\subseteq {\Sigma }^{\star }:\exists \text{DFA}M\text{t.c.}L(M)=L\}$$

$L(M)=L$ significa che l’automa $M$ riconosce $L$.

Definire un linguaggio regolare tramite la funzione di transizione estesa

Per definire rigorosamente un $L(DFA)$, cioè il linguaggio regolare associato ad un DFA, si usa la funzione di transizione estesa.

$$\delta :Q\times \Sigma \to Q$$ $${\delta }^{\star }:Q\times {\Sigma }^{\star }\to Q$$

Così un linguaggio regolare si può definire come l’insieme $\{\sigma \in \Sigma :{\delta }^{\star }(\sigma )\in F\}$.

Delta star si può definire ricorsivamente in modo elegante partendo da $\delta$:

$$\{\begin{array}{l}{\delta }^{\star }(q,\epsilon )=\delta (q,\epsilon )\\ {\delta }^{\star }(q,ax)={\delta }^{\star }(\delta (q,a),x)a\in \Sigma ,x\in {\Sigma }^{\star }\end{array}$$

N.B.: La stringa vuota $\epsilon$ sta in ${\Sigma }^{\star }$ (Star di Kleene di $\Sigma$) per definizione, ma non per forza nel linguaggio, che è un sottoinsieme di ${\Sigma }^{\star }$.

$$a\in \Sigma x\in {\Sigma }^{\star }$$

Il linguaggio riconosciuto da un DFA $M=(Q,\Sigma ,\delta ,q_0,F)$ è $L(M)=\{x\in {\Sigma }^{\star }:{\delta }^{\star }(q_0,x)\in F\}$.

Proprietà dei linguaggi regolari

I linguaggi regolari hanno una chiusura rispetto ad alcune operazioni:

• unione: $L_1\cup L_2=\{x\in {\Sigma }^{\star }:x\in L_1\vee x\in L_2\}$
• intersezione: $L_1\cap L_2=\{x\in {\Sigma }^{\star }:x\in L_1\wedge x\in L_2\}$
• complemento: $\overline{L_1}=\{x\in {\Sigma }^{\star }:x\in L_1\}$
• concatenazione: dati $x=a_1,\dots ,a_n$ e $y=b_1,\dots ,b_n$, si ha $L_1\circ L_2$ = $a_1,\dots ,a_n{b}_1,\dots ,b_n$; ricorsivamente:

$$\{\begin{array}{l}x\epsilon =x,x,y\in \Sigma \\ x(ya)=(xy)a,a\in \Sigma \end{array}$$ $$L_1\circ L_2=\{xy:x\in L_1,y\in L_2\}$$

• potenza (è tipo il prodotto cartesiano):

$$\{\begin{array}{l}{x}^0=\epsilon \\ x^{n+1}=x^{n}x;n\ge 0\end{array}$$

Per i linguaggi

$$\{\begin{array}{l}{L}^0=\{\epsilon \}\\ L^{n+1}=L^n\circ L;n\ge 0\end{array}$$

Dimostrazioni

Unione

• Tesi: $L_1=L_1(M_1)$ e $L_2=L_2(M_2)$
• Ipotesi: $L_1\cup L_2$

Si assume che ${\Sigma }_1={\Sigma }_2$.

Difficoltà: non posso eseguire $M_1$ e $M_2$ su $x$ e vedere che succede. In qualche modo invece, bisogna costruire un DFA che li “esegue in parallelo”.

Devo definire $M=(Q,\Sigma ,\delta ,q_0,F)$ tale che:

• $Q=Q_1\times Q_2$
• $\delta ((r_1,r_2),a)=({\delta }_1(r_1,a),{\delta }_2(r_2,a))$
• $q_0=(q_1,q_2)$
• $F=(F_1\times Q_2)\cup (F_2\times Q_1)=\{(r_1,r_2):r_1\in F_1\vee r_2\in F_2\}$ (se uno dei due stati $Q_1$ o $Q_2$ sono finali non ci interessa dell’altro, stiamo ragionando sull’unione)

Il resto della dimostrazione è inutile per il corso.

Ri-dimostrazioni usando gli NFA

REG è chiuso per $\cup$

Dati due NFA $N_1,N_2$ che riconoscono rispettivamente $L_1,L_2$ costruisco un NFA $N$ che riconosce $L_1\cup L_2$.

REG è chiuso per $\circ$ (concatenazione)

Dati due NFA $N_1,N_2$ che riconoscono rispettivamente $L_1,L_2$ costruisco un NFA $N$ che riconosce $L_1\circ L_2$.

REG è chiusa per $\star$

Dato un NFA $N_1$ tale che $L(N)=L$ (che riconosce $L$) costruisco un NFA $N^{\star }$ tale che $L(N^{\star })=L^{\star }$.

Mettiamo conto che $N$ riconosce $L=\{0,1\}$, implementato con un albero di caratteri:

Per fare un DFA che riconosce $L^2=\{00,01,10,11\}$ bisogna copiare l’albero di $N$ e “attaccarlo” su ogni sua foglia:

Si potrebbe provare a ripetere il procedimento all’infinito per $N^{\star }$:

Ma questo non sarebbe un DFA, perché ha stati infiniti.

Però si può costruire un NFA analogo a questo partendo dal caso iniziale $\{0,1\}$:

Nel caso generale, vale che: