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à