Aiuto esercizi su Linguaggi Formali

[first100]

Ciao a tutti,

vorrei sapere se c'è qualcuno in grado di aiutarmi su esercizi su linguaggi formali , in pratica il ragionamento che dovrei seguire in questo tipo di esercizi.

In particolare non riesco a capire come data una grammatica,trovo il linguaggio L(G), o dato un linguaggio definire la sua grammatica.

oppure trovare un linguaggio attraverso la produzione

ho degli appunti e slide (purtroppo non ho potuto frequentare) ma non riesco a capire bene il meccanismo, grazie a chi mi aiuterà

[megas_archon]

E' possibile che sia possibile aiutarti se spieghi più in dettaglio cosa non ti è chiaro, di quel che leggi.

Una grammatica è, essenzialmente, un sistema di riscrittura, cioè un certo tipo di grafo i cui nodi sono liste di simboli nell'alfabeto da cui parti.

Il linguaggio di una grammatica è l'insieme di tutte le stringhe che puoi raggiungere applicando ripetutamente le regole di riscrittura, cioè la chiusura transitiva della relazione di riscrittura.

Probabilmente, però, hai bisogno di una spiegazione più vicina a quel che stai leggendo?

[first100]

Ciao, mi scuso veramente tanto per il ritardo nella risposta, ma è stato un periodo molto intenso in cui non sono riuscito a collegarmi.

Per quanto riguarda la discussione che avevo aperto oltre un mese fà , il problema principale è risolvere gli esercizi in cui si determina la grammatica di un linguaggio , applicazione del pumping lemma e classificazione dei linguaggi secondo Chomsky.

Come primo punto di difficoltà vorrei capire bene come si determina la grammatica che genera un linguaggio:

Se io ho :

$ L = { a^n b^n c^n | n> 0 }$

vorrei determinare la grammatica che genera questo linguaggio L:

io ho fatto:
$S$ è il simbolo iniziale
$P={A → aA | ε , B → bBc | bc }$ sono le produzioni.

ma non sono sicuro di aver fatto bene perchè vado un pò a tentativi

Grazie

[apatriarca]

Non sono un esperto in queste cose ma l'impressione è che la tua produzione non genera lo stesso numero di \(a\), \(b\) e \(c\) come richiesto nel linguaggio. Che tipo di linguaggio si tratta secondo Chomsky?

[first100]

Ciao , penso che la grammatica sia di tipo 2 ma come vedi sono molto incerto.

[apatriarca]

No, la tua intuizione è sbagliata. Si tratta di un linguaggio sensibile al contesto (i.e. tipo 1). Per dimostrarlo puoi fare uso di determinati teoremi come il pumping lemma. Si tratta in effetti di uno degli esempi più classici di questo tipo di linguaggio.

Se faccio uso della tua produzione, supponendo che \(S \to A\,B\), hai che \(A\) produrrà un certo numero (\(n \geq 0\)) di \(a,\) mentre \(B\) produrrà una differente quantità \(m > 0\) di `b` seguite dalla stessa quantità di `c`. Il tuo linguaggio è insomma \(\{ a^nb^mc^m \mid n \geq 0, m > 0 \}\) che è diverso da quello originale in cui si richiede che \(n = m\). Per produrre quel linguaggio è necessario fare uso di una grammatica un po' più complicata che si ricorda di quante \(a\) hai inserito. Qualcosa come segue
\[
\begin{align*}
S \to a\,B\,C \\
S \to a\,S\,B\,C \\
C\,B \to C\,Z \\
C\,Z \to W\,Z \\
W\,Z \to W\,C \\
W\,C \to B\,C \\
a\,B \to a\,b \\
b\,B \to b\,b \\
b\,C \to b\,c \\
c\,C \to c\,c
\end{align*}
\]
Intuitivamente quello che stai facendo è che usando la seconda produzione di \(S\) \(n-1\) volte seguita dalla prima avrai qualcosa nella forma \(a^n\,(B\,C)^n\). A questo punto è necessario spostare tutte le \(B\) in modo che precedano le \(C\). Il primo passo è quello di chiamare queste \(B\) fuori posto come \(Z\) usando la terza regola e tutte le \(C\) fuori posto (quelle che precedono una \(B\) fuori posto) come \(W\) usando la quarta regola. In questo modo otteniamo \(a^n\,B\,(W\,Z)^{n-1}C\). A questo punto sostituiamo le \(Z\) con \(B\) e le \(W\) con \(B\) usando le regole cinque e sei. A questo punto abbiamo \(a^n\,B^2\,(C\,B)^{n-2}C^2\). Abbiamo quindi messo in ordine un \(B\) e un \(C\) aggiuntivo. A questo punto ripetiamo i passaggi finché non otteniamo le \(B\) e le \(C\) nell'ordine che desideriamo e usiamo le ultime regole per trasformare i simboli \(B\) e \(C\) in \(b\) e \(c\).

Nota che ho copiato questa grammatica da qui. Non sono stato insomma io a scriverla. Non faccio queste cose da un sacco di tempo per cui non mi è ad esempio del tutto chiaro perché sia necessario passare dalle produzioni \(Z\) e \(W\) invece di scrivere semplicemente \(C\,B \to B\,C\) e quindi richiedere semplicemente che ogni volta che abbiamo questi simboli in ordine inverso li possiamo scambiare. Potrebbe essere una limitazione nel modo in cui vanno scritte queste grammatiche.

Come ultima nota è importante osservare che le produzioni non sono della forma \(A \to \alpha\) come per le grammatiche di tipo 2. In effetti non è possibile scrivere la grammatica in quel modo proprio perché non è una grammatica di tipo 2, ma di tipo 1.

[first100]

Grazie mille, comunque qualcosa sto riuscendo a capirla anche se ho molta confusione , apro thread con un altro esercizio