Title: Linguaggi di Programmazione Primo Semestre / 09 - Proprietà algebriche dei linguaggi regolari

Def: Automa a pila non deterministico (PDA)

Transazioni di un PDA, descrizione di uno stato, mossa, cammino

Def: Linguaggio Accettato dei pda

Teorema, sull'espressività dei PDA che hanno che riconoscono attraverso lo sato finale e quelli che terminano con la fine della pila

Teorema: Linguaggio Libero e accettazione di un pda

Dimostrazione, Linguaggio Libero è equivalente ad un linguaggio accettato da un pda