[Linguaggi regolari] Stringhe con numero pari di 0
Salve a tutti! Ho qualche problema con un esercizio sui linguaggi regolari: più precisamente ho un linguaggio composto da stringhe che contengono un numero pari di 0 (sono contate anche le stringhe che non ne contengono). L'automa l'ho costruito ed è uguale a quello che si trova nella seguente pagina di wikipedia http://it.wikipedia.org/wiki/Automa_a_s ... rministico
Però ora devo provare tramite induzione che tali stringhe fanno parte del linguaggio ma non ho idea di come fare. Qualche suggerimento?
Però ora devo provare tramite induzione che tali stringhe fanno parte del linguaggio ma non ho idea di come fare. Qualche suggerimento?
Risposte
Non capisco cosa devi provare... forse che l'automa accetta tutte le stringhe con un numero pari di zeri (?)
Si esatto..ma forse mi sono espresso male. Purtroppo non ho ancora ben capito questi esercizi quindi mi trovo un pò in difficoltà. Avevo pensato di fare in questo modo (ma che secondo me è sbagliato poichè non prova che TUTTE le stringhe con un numero pari di 0 appartengono al linguaggio):
-studiare (tramite la funzione delta che però non rieco a rappresentare poichè è sparita la funzione per creare le formule O.o) la stringa che contiene due 0 (mostrando che appartiene al linguaggio);
-studiare la stringa che contiene uno 0 soltanto (mostrando che tale stringa non appartiene al linguaggio);
come ho già detto per me non è il metodo giusto perchè questi due casi non rappresentano la totalità delle stringhe accettate e non dal linguaggio e quindi mi trovo a un punto morto!
-studiare (tramite la funzione delta che però non rieco a rappresentare poichè è sparita la funzione per creare le formule O.o) la stringa che contiene due 0 (mostrando che appartiene al linguaggio);
-studiare la stringa che contiene uno 0 soltanto (mostrando che tale stringa non appartiene al linguaggio);
come ho già detto per me non è il metodo giusto perchè questi due casi non rappresentano la totalità delle stringhe accettate e non dal linguaggio e quindi mi trovo a un punto morto!
Mi sembra di dover dimostrare l'esistenza dell'acqua calda, ma comunque se gli esercizi del tuo testo (curiosità: quale?) son questi, facciamolo.
La stringa vuota con n=0 zeri appartiene al linguaggio, ed è riconosciuta dall'automa come tale; infatti l'automa ha stato iniziale accettante.
Supposto che una stringa 's' (appartenente al linguaggio) con k zeri sia accettata, si dimostra facilmente che una stringa 'sw' dove 'w' contiene esattamente due zeri, indipendentemente da come è fatta, viene accettata dall'automa e quindi appartiene al linguaggio.
Principio di induzione: caso base+passo induttivo, dimostrazione completata.
[ Tieni presente che - veramente - è come dimostrare che, visto che l'acqua è calda, allora è calda. Ma davvero ti si richiede questo? ]
EDIT: rimossi i tag formule che non stanno funzionando...
La stringa vuota con n=0 zeri appartiene al linguaggio, ed è riconosciuta dall'automa come tale; infatti l'automa ha stato iniziale accettante.
Supposto che una stringa 's' (appartenente al linguaggio) con k zeri sia accettata, si dimostra facilmente che una stringa 'sw' dove 'w' contiene esattamente due zeri, indipendentemente da come è fatta, viene accettata dall'automa e quindi appartiene al linguaggio.
Principio di induzione: caso base+passo induttivo, dimostrazione completata.
[ Tieni presente che - veramente - è come dimostrare che, visto che l'acqua è calda, allora è calda. Ma davvero ti si richiede questo? ]
EDIT: rimossi i tag formule che non stanno funzionando...
In realtà la cosa è più complessa: l'esercizio mi dava una tabella di transizione da cui ricavare l'automa a stati finiti.
Questo automa riconosceva il linguaggio comprendente tutte le stringhe aventi un numero pari di 0 (condizione a cui do il nome di L1) e un numero dispari di 1 (l'alfabeto è {0,1}).
Ora io ho voluto studiare separatamente le due condizioni nel modo seguente: ho preso il complemento del linguaggio che ha stringhe con un numero dispari di 1 (cioè il linguaggio che ha stringhe con un numero pari di 1 e che chiamo L2) in modo da poter studiare il linguaggio di partenza tramite la proprietà di chiusura (che dice che se due linguaggi L1 e L2 sono regolari allora anche l'intersezione tra L1 e il complemento di L2 è regolare). Cosi studiando solo L1 avrei dimostrato la regolarità del linguaggio di partenza.
Spero di non aver fatto troppa confusione! Cmq l'esercizio è tratto dalla dispensa "Fondamenti di informatica:linguaggi formali e calcolabilità" di Agostino Dovier e Roberto Giacobazzi.
Ah e grazie per la tua risposta precedente.
Questo automa riconosceva il linguaggio comprendente tutte le stringhe aventi un numero pari di 0 (condizione a cui do il nome di L1) e un numero dispari di 1 (l'alfabeto è {0,1}).
Ora io ho voluto studiare separatamente le due condizioni nel modo seguente: ho preso il complemento del linguaggio che ha stringhe con un numero dispari di 1 (cioè il linguaggio che ha stringhe con un numero pari di 1 e che chiamo L2) in modo da poter studiare il linguaggio di partenza tramite la proprietà di chiusura (che dice che se due linguaggi L1 e L2 sono regolari allora anche l'intersezione tra L1 e il complemento di L2 è regolare). Cosi studiando solo L1 avrei dimostrato la regolarità del linguaggio di partenza.
Spero di non aver fatto troppa confusione! Cmq l'esercizio è tratto dalla dispensa "Fondamenti di informatica:linguaggi formali e calcolabilità" di Agostino Dovier e Roberto Giacobazzi.
Ah e grazie per la tua risposta precedente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo