Problema relativo alla creazione di un tipo di PDA
Ho delle difficoltà in merito a un esercizio su PDA.
Viene chiesto di definire un PDA accettante $L={a^nb^mc^l|n+m>l$ e $l$ è pari$}$
Essenzialmente i problemi sono due: non saprei come definire un PDA in grado di accettare parole pari, e non riesco a capire come poter legare le due regole. Fin'ora il tipo di esercizi che ho fatto al più richiedeva che le regole venissero rispettate sotto OR (regola1 OR regola2, dove basta gestire due rami in cui uno o l'altro siano verificati), in questo caso viene richiesto che entrambe le regole siano verificate, e non capisco in che modo devo operare;
per quel che riguarda la regola $n+m>l$ ho definito l'automa in questo modo:
1. $delta(q_0,a,Z_0)={(q_0,XZ_0)} , delta(q_0,b,Z_0)={(q_0, XZ_0)}$
$delta(q_0,a,X)={(q_0,XX)}, delta(q_0,b,XX)={(q_0,XX)}$
Questo primo insieme di produzioni inserisce il simbolo $X$ nello stack indipendentemente da quali siano gli input
2. $delta(q_0,c,Z_0)=Ø, delta(q_0,c,X)=Ø$
Produzioni nel caso non vi siano $a,b$ come input
3. $delta(q_0,\epsilon,Z_0)={(q1,Z_0)}, delta(q_0,\epsilon,X)={(q_1,Z_0)}$
Permette di passare allo stato $q_1$ in ogni momento senza modificare lo stack.
4. $delta(q_1,c,X)={(q_1,\epsilon)}$
elimina un simbolo dallo stack ogni volta che vede $c$ e rimane in $q_1$
$delta(q_1,\epsilon,Z_0)=Ø$
caso in cui il numero di $n+m=l$
5. $delta(q_1,\epsilon,X)={(q_2,X)}$ con $q_2$ stato finale accettante (non ci sono piu input e lo stack contiene ancora simboli, quindi la condizione $n+m$ è verificata.
Il problema è che non sapendo gestire regole in AND non sono convinto di quanto possa esser utile(consumo già in parte lo stack senza operare alcuna verifica sulla parità, e non saprei fare le cose contemporaneamente, e più in generale non so come verificare la parità).
Sarebbe utile anche un po di documentazione relativa a esercizi simili data la loro scarsità online(non ho trovato neanche risposta sull'Ullman, dove gli esercizi proposti al più contengono regole in OR, o sono i classici che si trovano un po ovunque, o meglio, che da qui derivano)
Viene chiesto di definire un PDA accettante $L={a^nb^mc^l|n+m>l$ e $l$ è pari$}$
Essenzialmente i problemi sono due: non saprei come definire un PDA in grado di accettare parole pari, e non riesco a capire come poter legare le due regole. Fin'ora il tipo di esercizi che ho fatto al più richiedeva che le regole venissero rispettate sotto OR (regola1 OR regola2, dove basta gestire due rami in cui uno o l'altro siano verificati), in questo caso viene richiesto che entrambe le regole siano verificate, e non capisco in che modo devo operare;
per quel che riguarda la regola $n+m>l$ ho definito l'automa in questo modo:
1. $delta(q_0,a,Z_0)={(q_0,XZ_0)} , delta(q_0,b,Z_0)={(q_0, XZ_0)}$
$delta(q_0,a,X)={(q_0,XX)}, delta(q_0,b,XX)={(q_0,XX)}$
Questo primo insieme di produzioni inserisce il simbolo $X$ nello stack indipendentemente da quali siano gli input
2. $delta(q_0,c,Z_0)=Ø, delta(q_0,c,X)=Ø$
Produzioni nel caso non vi siano $a,b$ come input
3. $delta(q_0,\epsilon,Z_0)={(q1,Z_0)}, delta(q_0,\epsilon,X)={(q_1,Z_0)}$
Permette di passare allo stato $q_1$ in ogni momento senza modificare lo stack.
4. $delta(q_1,c,X)={(q_1,\epsilon)}$
elimina un simbolo dallo stack ogni volta che vede $c$ e rimane in $q_1$
$delta(q_1,\epsilon,Z_0)=Ø$
caso in cui il numero di $n+m=l$
5. $delta(q_1,\epsilon,X)={(q_2,X)}$ con $q_2$ stato finale accettante (non ci sono piu input e lo stack contiene ancora simboli, quindi la condizione $n+m$ è verificata.
Il problema è che non sapendo gestire regole in AND non sono convinto di quanto possa esser utile(consumo già in parte lo stack senza operare alcuna verifica sulla parità, e non saprei fare le cose contemporaneamente, e più in generale non so come verificare la parità).
Sarebbe utile anche un po di documentazione relativa a esercizi simili data la loro scarsità online(non ho trovato neanche risposta sull'Ullman, dove gli esercizi proposti al più contengono regole in OR, o sono i classici che si trovano un po ovunque, o meglio, che da qui derivano)
Risposte
giacchè non trovavo documentazione sufficiente, mi son messo alla ricerca di qualche lezione online su youtube, e da un esercizio che non c'entrava un granchè mi è balenata un idea che potrebbe risolvere il problema:
mi evito il patema della riscrittura delle produzioni, e descrivo l'idea:
sono sempre tre stati $q_0, q_1, q_2$, il primo stato funziona come prima (vengono memorizzati nello stack tanti simboli quante $a,b$ lette), la differenza è che l'operazione di pop non avviene nello stato $q_1$ ma distribuita su $q_1,q_2$. Si consideri $q_1$ lo stato di lunghezza pari e $q_2$ lo stato di lunghezza dispari. Se si è in $q_1$ e si vede una c, si va nello stato $q_2$ e se si vede una c da $q_2$ si va in $q_1$(fintanto che si può consumare l'input), successivamente ci si sposta tra i due stati continuando la verifica, ma sugli elementi restanti dello stack in questo modo si "conta" la parità su tutta la parola, iterando finchè il numero elementi dello stack non si è svuotato. Se a questo punto si è in $q_1$ la parola è pari.
Fatemi notare eventuali errori, spero che comunque possa tornare utile a qualcuno.
mi evito il patema della riscrittura delle produzioni, e descrivo l'idea:
sono sempre tre stati $q_0, q_1, q_2$, il primo stato funziona come prima (vengono memorizzati nello stack tanti simboli quante $a,b$ lette), la differenza è che l'operazione di pop non avviene nello stato $q_1$ ma distribuita su $q_1,q_2$. Si consideri $q_1$ lo stato di lunghezza pari e $q_2$ lo stato di lunghezza dispari. Se si è in $q_1$ e si vede una c, si va nello stato $q_2$ e se si vede una c da $q_2$ si va in $q_1$(fintanto che si può consumare l'input), successivamente ci si sposta tra i due stati continuando la verifica, ma sugli elementi restanti dello stack in questo modo si "conta" la parità su tutta la parola, iterando finchè il numero elementi dello stack non si è svuotato. Se a questo punto si è in $q_1$ la parola è pari.
Fatemi notare eventuali errori, spero che comunque possa tornare utile a qualcuno.
Può andare bene, direi. Prova, non mi sembra difficile difficile.
Una mia idea alternativa: se trova 'a' l'automa alterna (controllando lo stack) due simboli $X$ e $Y$, analogamente fa per 'b'. In questo modo puoi sapere se la stringa iniziale $a^n b^m$ è composta da da un numero pari o dispari di caratteri, e sulla base di questa informazione sapere se la stringa $c^l$ lo è.
Come vedi la mia idea è analoga alla tua, solo che usa simboli invece di stati.
Una mia idea alternativa: se trova 'a' l'automa alterna (controllando lo stack) due simboli $X$ e $Y$, analogamente fa per 'b'. In questo modo puoi sapere se la stringa iniziale $a^n b^m$ è composta da da un numero pari o dispari di caratteri, e sulla base di questa informazione sapere se la stringa $c^l$ lo è.
Come vedi la mia idea è analoga alla tua, solo che usa simboli invece di stati.
ti ringrazio per la reply, sembrano entrambi funzionanti
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo