Linguaggio libero dal contesto
Salve, devo stabilire di che tipo è il linguaggio $L=\{0^i1^m0^k,m>0,i\leq m,k\geq m\}$.
Secondo me è context free, ho dimostrato (spero correttamente) che non è regolare. Dite che sia vero?
Per mostrarlo vorrei costruire una grammatica CF che lo genera ma non riesco perché non ci sono abbastanza esempi sul testo di riferimento e non ho capito molto bene come si fa in pratica.
Il massimo che sono riuscita a scrivere è questo:
$S\to S0$
$A\to10$
$B\to1A0$
$C\to0A|0B$
però non va bene perché non ci sono tutte le stringhe che cominciano con almeno $m$ simboli "$0$"
Si può fare in qualche modo?
Grazie a tutti!
Secondo me è context free, ho dimostrato (spero correttamente) che non è regolare. Dite che sia vero?
Per mostrarlo vorrei costruire una grammatica CF che lo genera ma non riesco perché non ci sono abbastanza esempi sul testo di riferimento e non ho capito molto bene come si fa in pratica.
Il massimo che sono riuscita a scrivere è questo:
$S\to S0$
$A\to10$
$B\to1A0$
$C\to0A|0B$
però non va bene perché non ci sono tutte le stringhe che cominciano con almeno $m$ simboli "$0$"
Si può fare in qualche modo?
Grazie a tutti!
Risposte
La tua grammatica non definisce regole per sostituire lo start-symbol $S$ con qualcosa d'altro... 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo