Esercizi su gerarchie di Chomsky

Dato il seguente linguaggio L, di alfabeto: $ X = {a,b}$

$ L = {a^n b^k | n ≥0, k≤ n}$

1) L è regolare?

2) Stabilire in quale gerarchia di Chomsky ricade L

3) Determinare una grammatica che generi L


Risposte:
1) Dovrei applicare il pumping lemma?

2) Qui non saprei proprio come procedere

3) Mi trovo le produzioni :

S -> lambda (produzione vuota per il caso base, dove k = 0)
S -> aSb (aggiunge "ab" a w e incrementa sia n che k di 1)
S -> aS (aggiunge una "a" a w e incrementa n di 1)

Grazie a chi mi aiuterà

1. Puoi certamente fare uso del pumping lemma per dimostrare che non si tratta di un linguaggio regolare. Intuitivamente la relazione tra \(k\) e \(n\) è in generale un segno che il linguaggio non può essere regolare. Ti invito a cercare di risolvere il problema per conto tuo.

Per il punto due immagino che puoi in un certo senso fare uso della tua grammatica nel punto 3. Sai infatti che non è regolare ma che può essere gerato da una grammatica del tipo che hai usato nel punto 3. Il punto uno esclude il tipo 3, mentre il fatto che hai una grammatica libera dal contesto che genera il tuo linguaggio significa che non può essere di tipo 1 o inferiore.

Il terzo punto mi sembra corretto.

grazie mille!