Esercizio su linguaggi
salve a tutti.
non riesco a risolvere questo tipo di problema:
dato un linguaggio $L={a^kb^n|n>=0,k<=n}$ costruire una grammatica che lo genera. é possibile utilizzare una grammatica regolare? se si dare la sua definizione.
come faccio a costruire la grammatica se ho k<=n?
non riesco a risolvere questo tipo di problema:
dato un linguaggio $L={a^kb^n|n>=0,k<=n}$ costruire una grammatica che lo genera. é possibile utilizzare una grammatica regolare? se si dare la sua definizione.
come faccio a costruire la grammatica se ho k<=n?
Risposte
Direi che il problema è in parte equivalente a quello di chiedere di trovarla per questo linguaggio:
\[ L = \{ a^k\,b^k \mid k \geq 0 \}. \]
Data infatti una grammatica per questo puoi semplicemente aggiungere un numero arbitrario di \(b\) alla fine per ottenere una stringa della tua grammatica originaria. Hai qualche idea di come risolvere questo problema?
\[ L = \{ a^k\,b^k \mid k \geq 0 \}. \]
Data infatti una grammatica per questo puoi semplicemente aggiungere un numero arbitrario di \(b\) alla fine per ottenere una stringa della tua grammatica originaria. Hai qualche idea di come risolvere questo problema?
no...
Prova a pensare di costruire la stringa in maniera iterativa. Partendo dalla stringa vuota, che in questo caso denoto per comodità con \(C(0)\) e per poi costruire tutti i \( C(k) = a^k\,b^k. \) Riesci ad immaginarti un metodo per costruire \(C(k+1)\) a partire da \(C(k)\)?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo