Aiuto Gerarchia di Chomsky
Salve ragazzi
Vorrei sapere, nel caso generale, qual'è il metodo adatto per stabilire, dato un linguaggio, qual'è la classe più specifica della gerarchia di Chomsky a cui esso appartiene.
Ad esempio per questo linguaggio:
$X={a,b} L={ w in X | w=a^j b^k | 0<=j<=k}$
Grazie mille per l'aiuto!
(È un anno che cerco di dare questo esame
)
Vorrei sapere, nel caso generale, qual'è il metodo adatto per stabilire, dato un linguaggio, qual'è la classe più specifica della gerarchia di Chomsky a cui esso appartiene.
Ad esempio per questo linguaggio:
$X={a,b} L={ w in X | w=a^j b^k | 0<=j<=k}$
Grazie mille per l'aiuto!
(È un anno che cerco di dare questo esame
)
Risposte
Esistono teoremi che si possono applicare per verificare se un linguaggio appartiene ad una specifica classe. Ma per esempi di questo tipo è spesso possibile avere una idea generale prima di fare alcun "calcolo".
Il tuo esempio è per esempio certamente non regolare. La condizione che \(j \leq k\) richiede che il linguaggio sia in qualche modo in grado di mantenere una storia. Questo genere di condizioni sono invece normalmente ottenibili attraverso linguaggi context-free. In questo caso posso ad esempio usare la seguente grammatica context-free:
\[
\begin{align*}
S &\to aSb \\
S &\to Sb \\
S &\to ε
\end{align*}
\]
Questo è un metodo più che altro utile quando inizi a guardare ad un linguaggio per cercare di stabilire a quale classe possa appartenere. Quando risolvi un esercizio devi poi ovviamente usare un qualche tipo di teorema. Il fatto di aver trovare una grammatica di un certo tipo per quel linguaggio ovviamente ti permette di stabilire che è almeno di quella classe. Se avessimo insomma costruito una grammatica regolare per quel linguaggio sarebbe stato sufficiente a dire fosse regolare. Ma questo non è possibile come possiamo dimostrare usando il pumping lemma.
Supponiamo il linguaggio \(L\) sia regolare. Esiste allora una costante \(p\) per cui ogni parola \(w\) più lunga di \(p\) può essere scritta nella forma \( xyz \) per cui valgono le seguenti condizioni: \(|y| \geq 1,\) \(|xy| \leq p,\) \(\forall\, n \geq 0 \; xy^nz \in L.\) Siccome il numero di \(b\) deve essere maggiore di quello di \(a,\) il numero di \(b\) in \(y\) deve essere maggiore o uguale a quello delle \(a\) perché l'ultima condizione sia verificata. Ma il numero di \(a\) in una generica parola è limitato solo dal numero di \(b\) e non è quindi possibile fissare un valore costante \(p\) entro il quale sia possibile trovare una \(b\) come richiede la seconda condizione. Il linguaggio non può quindi essere regolare in quando siamo arrivati ad una contraddizione.
Il tuo esempio è per esempio certamente non regolare. La condizione che \(j \leq k\) richiede che il linguaggio sia in qualche modo in grado di mantenere una storia. Questo genere di condizioni sono invece normalmente ottenibili attraverso linguaggi context-free. In questo caso posso ad esempio usare la seguente grammatica context-free:
\[
\begin{align*}
S &\to aSb \\
S &\to Sb \\
S &\to ε
\end{align*}
\]
Questo è un metodo più che altro utile quando inizi a guardare ad un linguaggio per cercare di stabilire a quale classe possa appartenere. Quando risolvi un esercizio devi poi ovviamente usare un qualche tipo di teorema. Il fatto di aver trovare una grammatica di un certo tipo per quel linguaggio ovviamente ti permette di stabilire che è almeno di quella classe. Se avessimo insomma costruito una grammatica regolare per quel linguaggio sarebbe stato sufficiente a dire fosse regolare. Ma questo non è possibile come possiamo dimostrare usando il pumping lemma.
Supponiamo il linguaggio \(L\) sia regolare. Esiste allora una costante \(p\) per cui ogni parola \(w\) più lunga di \(p\) può essere scritta nella forma \( xyz \) per cui valgono le seguenti condizioni: \(|y| \geq 1,\) \(|xy| \leq p,\) \(\forall\, n \geq 0 \; xy^nz \in L.\) Siccome il numero di \(b\) deve essere maggiore di quello di \(a,\) il numero di \(b\) in \(y\) deve essere maggiore o uguale a quello delle \(a\) perché l'ultima condizione sia verificata. Ma il numero di \(a\) in una generica parola è limitato solo dal numero di \(b\) e non è quindi possibile fissare un valore costante \(p\) entro il quale sia possibile trovare una \(b\) come richiede la seconda condizione. Il linguaggio non può quindi essere regolare in quando siamo arrivati ad una contraddizione.
Grazie mille per l'aiuto, ora ho capito come muovermi!
In pratica, se riesco, trovo una grammatica valida per il linguaggio cosi da determinare una prima possibile classe di appartenenza, e dopo tramite il pumping lemma per i context free o per i linguaggi regolari (equivalenti a quelli lineari desti) determino se il linguaggio può avere una classe più appropriata
In pratica, se riesco, trovo una grammatica valida per il linguaggio cosi da determinare una prima possibile classe di appartenenza, e dopo tramite il pumping lemma per i context free o per i linguaggi regolari (equivalenti a quelli lineari desti) determino se il linguaggio può avere una classe più appropriata
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo