Linguaggi regolari, context-free e non context-free
Ciao, sono giorni che studio Linguaggi di programmazione ma non riesco ad applicare la teoria alla pratica. Come faccio a capire in modo pratico se un linguaggio è regolare, context-free o non context-free? C'è un metodo immediato o quasi per saperlo? Il pumping lemma non l'ho capito molto bene.
Ciò che ho capito è che un linguaggio del genere ${a^n b^m | n>=0}$ non è regolare perchè chiede che ci siano un numero "preciso" di $a$ e di $b$ e questo non è possibile con i linguaggi regolari. E' giusto come ragionamento? A me sembra un pò vago...
E per i context-free?
Per esempio questi linguaggi cosa sono?
Ciò che ho capito è che un linguaggio del genere ${a^n b^m | n>=0}$ non è regolare perchè chiede che ci siano un numero "preciso" di $a$ e di $b$ e questo non è possibile con i linguaggi regolari. E' giusto come ragionamento? A me sembra un pò vago...
E per i context-free?
Per esempio questi linguaggi cosa sono?
- $L_1 = {ab^n ab^(2n) |n > 0}$
- $L_2 = {ab^n c^k a^n b^k |k,n > 0}$
- $L_3 = {ab^n ab^(2n) ab^(3n)|n > 0}$
- $L_4 = {ab^n b^k a^n b^k |k,n > 0}$
[/list:u:2k42aef7]
Grazie mille
Risposte
Premessa: sono abbastanza arrugginito su questi argomenti. Magari aspetta che qualcun altro confermi le mie risposte (e che ti spieghi il pumping lemma).
Un linguaggio regolare può essere riconosciuto da un automa a stati finiti, un linguaggio libero dal contesto può essere riconosciuto da un automa a pila, per gli altri servono formalismi più potenti (es. macchina di Turing).
$\{a^n b^m | n \geq 0 \}$ è regolare, ma forse intendevi $\{a^n b^n | n \geq 0 \}$. Questo non è regolare, perché $n$ è grande a piacere (potrebbe esserci un qualsiasi numero di $a$, purché seguite dallo stesso numero di $b$). Serve almeno un automa a pila, perché devi contare quanto vale $n$ (e lo fai usando la memoria della pila).
In generale, se nell'espressione di un linguaggio compare più di una volta $n$ o $k$, non basta un automa a stati finiti, perché devi in qualche modo memorizzare quanto è grande $n$ o $k$. Se compare solo due volte, potrebbe bastare un automa a pila (ma anche no, vedi $L_2$). Di più no, perché la seconda volta che conti distruggi il valore, e non sai più quanto vale per la terza volta.
In realtà, se $n$ è limitato (es. minore di $N$) puoi sempre usare un automa a stati finiti. Infatti tutti i calcolatori reali, che hanno memoria finita, possono riconoscere solo linguaggi regolari. Però se $N$ è molto grande possiamo fare finta che siano Turing-completi.
Esempi:
Nessuno dei linguaggi che hai scritto è regolare.
$L_1$
Linguaggio libero dal contesto.
Leggi un $a$. Leggi tante $b$ copiandole nella pila. Leggi un $a$. Leggi tante $b$ togliendo un elemento dalla pila ogni 2. Se la pila è vuota, accetti.
$L_3$
Non basta un automa a pila. Vedi $L_1$, quando arrivi alla terza $a$ non sai più quanto vale $n$.
Linguaggio non libero dal contesto.
$L_4$
Linguaggio libero dal contesto.
Leggi $a$. Leggi tante $b$ e le copi nella pila. Leggi tante $a$ e togli una $b$ dalla pila ogni volta. Leggi tante $b$ e togli una $b$ dalla pila ogni volta. Se la pila è vuota, accetti.
Puoi anche scrivere il linguaggio così: $L_4 = {ab^{n+k} a^n b^k |k,n > 0}$
$L_2$
Sembra simile a $L_4$ ma c'è una differenza: prima avevi tante $b$ seguite da tante $a$ e tante $b$, e ti bastava controllare che la somma di $a$ e delle ultime $b$ fosse uguale al numero delle prime $b$. Ora invece devi contare esattamente quante $a$, $b$ e $c$ incontri. Però tu conti prima $n$ e poi $k$, ma dopo ti servono nell'ordine inverso. Ti servirebbe una seconda pila per invertire la memoria, ma un automa a due pile è equivalente alla macchina di Turing.
Linguaggio non libero dal contesto.
Il linguaggio $L_4' = {ab^n c^k b^k a^n |k,n > 0}$ invece può essere riconosciuto da un automa a pila ($n$ e $k$ ti servono nell'ordine giusto), quindi è libero dal contesto.
Un linguaggio regolare può essere riconosciuto da un automa a stati finiti, un linguaggio libero dal contesto può essere riconosciuto da un automa a pila, per gli altri servono formalismi più potenti (es. macchina di Turing).
$\{a^n b^m | n \geq 0 \}$ è regolare, ma forse intendevi $\{a^n b^n | n \geq 0 \}$. Questo non è regolare, perché $n$ è grande a piacere (potrebbe esserci un qualsiasi numero di $a$, purché seguite dallo stesso numero di $b$). Serve almeno un automa a pila, perché devi contare quanto vale $n$ (e lo fai usando la memoria della pila).
In generale, se nell'espressione di un linguaggio compare più di una volta $n$ o $k$, non basta un automa a stati finiti, perché devi in qualche modo memorizzare quanto è grande $n$ o $k$. Se compare solo due volte, potrebbe bastare un automa a pila (ma anche no, vedi $L_2$). Di più no, perché la seconda volta che conti distruggi il valore, e non sai più quanto vale per la terza volta.
In realtà, se $n$ è limitato (es. minore di $N$) puoi sempre usare un automa a stati finiti. Infatti tutti i calcolatori reali, che hanno memoria finita, possono riconoscere solo linguaggi regolari. Però se $N$ è molto grande possiamo fare finta che siano Turing-completi.
Esempi:
Nessuno dei linguaggi che hai scritto è regolare.
$L_1$
Linguaggio libero dal contesto.
Leggi un $a$. Leggi tante $b$ copiandole nella pila. Leggi un $a$. Leggi tante $b$ togliendo un elemento dalla pila ogni 2. Se la pila è vuota, accetti.
$L_3$
Non basta un automa a pila. Vedi $L_1$, quando arrivi alla terza $a$ non sai più quanto vale $n$.
Linguaggio non libero dal contesto.
$L_4$
Linguaggio libero dal contesto.
Leggi $a$. Leggi tante $b$ e le copi nella pila. Leggi tante $a$ e togli una $b$ dalla pila ogni volta. Leggi tante $b$ e togli una $b$ dalla pila ogni volta. Se la pila è vuota, accetti.
Puoi anche scrivere il linguaggio così: $L_4 = {ab^{n+k} a^n b^k |k,n > 0}$
$L_2$
Sembra simile a $L_4$ ma c'è una differenza: prima avevi tante $b$ seguite da tante $a$ e tante $b$, e ti bastava controllare che la somma di $a$ e delle ultime $b$ fosse uguale al numero delle prime $b$. Ora invece devi contare esattamente quante $a$, $b$ e $c$ incontri. Però tu conti prima $n$ e poi $k$, ma dopo ti servono nell'ordine inverso. Ti servirebbe una seconda pila per invertire la memoria, ma un automa a due pile è equivalente alla macchina di Turing.
Linguaggio non libero dal contesto.
Il linguaggio $L_4' = {ab^n c^k b^k a^n |k,n > 0}$ invece può essere riconosciuto da un automa a pila ($n$ e $k$ ti servono nell'ordine giusto), quindi è libero dal contesto.
Grazie, ora mi e' mooolto piu' chiaro!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo