[LF] Linguaggio regolare accettato
Salve,
vorrei un aiuto a capire come dimostrare questo esercizio.
Ora per dimostrarlo devo avere l'automa (nel mio caso un DFA) per dimostrare per induzione che esistono transizioni che portano negli stati finiali.
Però questo automa devo costruirlo, come posso fare senza passare per la definizione di una espressione regolare o qualsiasi altra cosa?
Ringrazio
vorrei un aiuto a capire come dimostrare questo esercizio.
Si verifichi che il seguente linguaggio $L$ con $\Sigma={0,1}$ sono regolari, dove $L$ è l'insieme di tutte le stringhe tali che il terzulitimo simbolo è $0$.
Ora per dimostrarlo devo avere l'automa (nel mio caso un DFA) per dimostrare per induzione che esistono transizioni che portano negli stati finiali.
Però questo automa devo costruirlo, come posso fare senza passare per la definizione di una espressione regolare o qualsiasi altra cosa?
Ringrazio
Risposte
Non ho capito cosa ti serve... Se definisci un DFA che accetta $L$ sei a dama: $L$ è regolare.
ciao Rggb 
intendo dire come costruisco questo DFA?
Come ragiono per costruire un automa, senza prima definire un formalismo tipo l'espressione regolare che descrive quel linguaggio.
Data la descrizione in linguaggio naturale, costruire l'automa.
La transizione che descrive se il linguaggio $L$ è accettato dal DFA $M$ è lo stato ${\delta_{f}(q_0,v0w) in F ||w|=2} in M$.
Ora ci sono degli step grafici per disegnare questo automa? Non penso si vada a tentativi, si fa notte se no
Spero abbia chiarito il mio intento
La dimostrazione che $L$ è regolare viene dopo, prima devo avere qusto automa per applicare l'induzione su di esso.
intendo dire come costruisco questo DFA?
Come ragiono per costruire un automa, senza prima definire un formalismo tipo l'espressione regolare che descrive quel linguaggio.
Data la descrizione in linguaggio naturale, costruire l'automa.
La transizione che descrive se il linguaggio $L$ è accettato dal DFA $M$ è lo stato ${\delta_{f}(q_0,v0w) in F ||w|=2} in M$.
Ora ci sono degli step grafici per disegnare questo automa? Non penso si vada a tentativi, si fa notte se no
Spero abbia chiarito il mio intento
La dimostrazione che $L$ è regolare viene dopo, prima devo avere qusto automa per applicare l'induzione su di esso.
Innanzitutto non c'è bisogno di nessuna dimostrazione per induzione dopo: se è riconosciuto da un DFA è regolare (c'è un teorema che lo prova).
Ci sono delle tecniche standard per la costruzione degli automi a partire da funzioni booleane, però servono più che altro per minimizzare gli stati dell'automa, di solito è molto più semplice arrivare direttamente ad esso.
Il caso in questione è piuttosto semplice: prova a pensare all'input come un flusso di caratteri e cerca di trovare un modo per far rimanere in uno stato accettante l'automa solo se il terzultimo carattere dell'input correntemente letto è $0$. Puoi aiutarti anche pensando al comportamento che l'automa dovrebbe assumere: legge il primo simbolo; se il simbolo letto è $0$ allora tra due simboli l'automa dovrà essere in uno stato accettante, altrimenti no. E vai avanti a ragionare in questo modo fino a non trovare una condizione che si ripete e che quindi ti permetta di far mantenere l'automa in uno stato accettante solo se il terzultimo simbolo attualmente letto è $0$.
Spero di averti dato qualche suggerimento utile.
Ci sono delle tecniche standard per la costruzione degli automi a partire da funzioni booleane, però servono più che altro per minimizzare gli stati dell'automa, di solito è molto più semplice arrivare direttamente ad esso.
Il caso in questione è piuttosto semplice: prova a pensare all'input come un flusso di caratteri e cerca di trovare un modo per far rimanere in uno stato accettante l'automa solo se il terzultimo carattere dell'input correntemente letto è $0$. Puoi aiutarti anche pensando al comportamento che l'automa dovrebbe assumere: legge il primo simbolo; se il simbolo letto è $0$ allora tra due simboli l'automa dovrà essere in uno stato accettante, altrimenti no. E vai avanti a ragionare in questo modo fino a non trovare una condizione che si ripete e che quindi ti permetta di far mantenere l'automa in uno stato accettante solo se il terzultimo simbolo attualmente letto è $0$.
Spero di averti dato qualche suggerimento utile.
Per dare un'idea con un disegno, abbiamo una situazione di questo tipo:
le possibili stringhe accettate sono quelle che finiscono con
$000$ (stato $q_5$)
$001$ (stato $q_6$)
$010$ (stato $q_7$)
$011$ (stato $q_8$)
Non ho ancora messo le "frecce" che partono dagli stati finali, ma non è così complicato.
Se ad esempio da $q_5$ si passa il simbolo $1$, abbiamo che gli ultimi tre simboli sono per forza $001$, quindi bisogna andare in $q_6$. Analogamente si costruiscono tutti i casi, fino ad avere una cosa di questo tipo:
le possibili stringhe accettate sono quelle che finiscono con
$000$ (stato $q_5$)
$001$ (stato $q_6$)
$010$ (stato $q_7$)
$011$ (stato $q_8$)
Non ho ancora messo le "frecce" che partono dagli stati finali, ma non è così complicato.
Se ad esempio da $q_5$ si passa il simbolo $1$, abbiamo che gli ultimi tre simboli sono per forza $001$, quindi bisogna andare in $q_6$. Analogamente si costruiscono tutti i casi, fino ad avere una cosa di questo tipo:
"hamming_burst":
Ora ci sono degli step grafici per disegnare questo automa? Non penso si vada a tentativi, si fa notte se no
Non ho mai fatto notte andando "a naso", per così dire, nel costruire (definire schematicamente/graficamente) un DFA.
"hamming_burst":
La dimostrazione che $L$ è regolare viene dopo, prima devo avere qusto automa per applicare l'induzione su di esso.
Come ti ho detto sopra e come anche Deckard ha rimarcato, non c'è nulla da dimostrare.
Comunque penso(*) tu intenda usare un metodo formale per passare dalla descrizione in linguaggio naturale:
"$L$ è un linguaggio sull'alfabeto pippo, tale che le stringhe sono fatte così e colà"
alla descrizione formalizzata, nel tuo caso:
$L={x0y: |y|=2 ^^ x in {0,1}^star ^^ y in {0,1}^star}$
(come hai scritto sopra)
per poi passare magari a
$L={x0y: (y=00\ vv y=01\ vv y=10\ vv y=11) ^^ x in {0,1}^star}$
eccetera. Ma a me sembra "equivalente" al definire direttamente il DFA.
Alternativa: scrivi la grammatica regolare che genera il linguaggio (e magari dimostri che esprime il linguaggio definito "a parole"), e da questa generi l'automa; e anche stavolta non c'è niente da dimostrare dopo: se la grammatica è regolare il linguaggio che esprime è regolare e quindi puoi definire un DFA.
(*) Se ho capito male, allora rispiegamelo. :\
sì avete ragione
in effetti andare a tentoni provando se una stringa (che appartiene al mio linguaggio) "disegna" il DFA e facendo backtrack quando non funziona, è la stessa cosa che pensare ad ogni transazione in maniera più formale.
Vi ringrazio, devo un po' smanettare con queste definizioni
Ma a me sembra "equivalente" al definire direttamente il DFA.
in effetti andare a tentoni provando se una stringa (che appartiene al mio linguaggio) "disegna" il DFA e facendo backtrack quando non funziona, è la stessa cosa che pensare ad ogni transazione in maniera più formale.
Vi ringrazio, devo un po' smanettare con queste definizioni
Comunque, solidarietà. Disegnare automi, ma anche mdT precisando tutti gli stati, funzioni, ecc. come visto fare in un topic da queste parti ultimamente, è la cosa più noiosa che si possa concepire.
Farlo una, due volte per capire come funzione la cosa ok, ci sta. Di più diventa un'inutile punizione. I prof., che ho potuto constatare esistono ancora, che assegnano esercizi del genere agli esami di informatica teorica meriterebbero di dimostrare IP=PSPACE usando il calcolo hilbertiano. O equivalentemente scrivere un gestionale in assembly.
Farlo una, due volte per capire come funzione la cosa ok, ci sta. Di più diventa un'inutile punizione. I prof., che ho potuto constatare esistono ancora, che assegnano esercizi del genere agli esami di informatica teorica meriterebbero di dimostrare IP=PSPACE usando il calcolo hilbertiano. O equivalentemente scrivere un gestionale in assembly.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo