[Linguaggi formali]AUTOMI A PILA

[Riccardo93]

Salve a tutti ragazzi, ho un grande problema che spero voi mi possiate aiutare a risolvere. Dovrei realizzare la tabella delle funzioni di transizione di "a^m b a^n".Quando mi trovavo di fronte a linguaggi del tipo a^m b^m sapevo che quando iniziavo a ricevere la "b" avendo "a" iniziavo la cancellazione. Spero che qualcuno mi possa aiutare per l'esame di lunedi.Grazie in anticipo e buona serata

[Nikopol]

Ma n e m sono legati in qualche modo? Altrimenti si tratta di una semplice espressione regolare (a*ba*) rappresentabile tramite automa a stati finiti.

[Riccardo93]

n e m sono numeri diversi maggiori di zero. Io devo rappresentare quell'espressione regolare a*ba* tramite un automa a pila e scrivere i valori dentro la tabella.Il mio problema è che non so come procedere dopo che mi arriva la b.Spero che mi potrai aiutare.Grazie e buona giornata

[Nikopol]

Dato che m e n sono vincolati (n != m && n,m > 0) devi in effetti usare un PDA e dunque non si parla più espressioni regolare.

Sono un po' arruginito in linguaggi formali ma proverei a procedere in questo modo:
ogni volta che leggo 'a' in input, prima di incontrare 'b', aggiungo 'a' alla pila;
se leggo 'b' allora so che ho letto le prime n 'a';
finchè leggo 'a' e il top dello stack contiene 'a' la elimino;
se quello che rimane è stringa vuota e pila vuota allora n == m, dunque la stringa non fa parte del linguaggio;
se invece rimane la stringa vuota e la pila contiene ancora delle 'a' allora n != m, dunque accetto;
altrimenti rimane stringa non vuota e pila vuota; consumo tutte le 'a' della stringa; se non incontro 'b' accetto;
Dunque il PDA accetta per stato finale.

Schematizzato (Z è primo simbolo della pila, EPS è epsilon):
q0 -> q0: a, Z / aZ; a, a / aa
q0 -> q1: b, a / a;
q1 -> q1: a, a / EPS;
q1 -> q2: a, Z / Z; EPS, a / Z
q2 -> q2: a, Z / Z

Adesso si può facilmente scrivere la tabella delle transizioni, lascio a te il compito

[mroghy]

Giuro che ho letto "autoNOmi piRla". Non me ne vogliano tutti gli autonomi che cercano di sbarcare il lunario nonostante la Repubblica faccia di tutto per impedirglielo.

[Riccardo93]

Grazie infinite per la risposta ma non ho ben capito una cosa. Fino a quando leggo 'a' aggiungo 'a' alla pila, ma nel momento esatto in cui incontro la 'b' passo a cancellare oppure devo aggiungere qualcosa ancora? Scusa ancora per l'ignoranza

[Nikopol]

Quando leggi 'b', cambi di stato e non modifichi la pila.

[Riccardo93]

Sei stato veramente molto gentile,dato che sei così disponibile ne approfitto per chiederti un ultimissima cosa. Se invece di a*ba* ci fosse a*b*a* come mi devo comportare quando arriva la b?

[Nikopol]

Figurati
Comunque a*ba* è un espressione regolare che denota un linguaggio regolare, rappresentabile da un automa a stati finiti (non hai bisognio di scomodare un automa a pila perchè non c'è nessun vincolo sul numero di 'a' che precedono e seguono la 'b').
{a^n.b.c^m | n != m} invece denota un linguaggio libero dal contesto rappresentabile da un automa a pila (ti serve la pila per tenere traccia delle 'a' lette prima di 'b' per poi controllare che il vincolo n !=m sia rispettato).

Detto questo, a*b*a* è un espressione regolare e, come già detto, può essere rappresentato da un DFA.
Se invece intendevi qualcosa tipo {a^n.b^n.c^n | n > 0} allora non si tratta più di un linguaggio libero dal contesto e quindi non è rappresentabile tramite automa a pila. Non sono sicuro al 100%, puoi verificare se sia effettivamente così usando il pumping lemma

[Riccardo93]

Ho un esame da fare oggi e l'ultimo esercizio chiede di realizzare sempre la tabella delle transizioni di un automa a pila. L'espressione regolare che il prof.vuole risolta è di solito del tipo a^m.b^n.a^n. Mi perdo sempre quando arrivo alla b.