Automi a pila deterministici

Esercizio 01

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b} della forma: $a^n{b}^n$, dove n è un numero naturale.

Esercizio 02

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b} della forma: $a^n{b}^{\mathrm{2n}}$, dove n è un numero naturale.

Esercizio 03

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b} della forma: $a^n{b}^m$, dove n ed m sono numeri naturali tali che $m\ge n$.

Esercizio 04

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b} della forma: $a^n{b}^n$, dove n ed m sono numeri naturali tali che $n\ge m$.

Esercizio 05

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b, c} della forma: $a^i{b}^j{c}^k$, dove i, j, k sono numeri naturali tali che i + k = j. In altri termini, il numero di b deve essere pari alla somma delle a e delle c.

Per semplicità, puoi assumere che ci siano almeno una a, almeno una b, almeno una c.

Esercizio 06

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b, c} della forma: $wc{w}^R$, dove w è una sequenza di a e di b, di lunghezza qualsiasi, mentre $w^R$ è la sequenza w, ma al contrario.

In altri termini, il DPDA deve riconoscere sequenze palindrome, aventi al centro la lettera c.

Esercizio 07

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {(, )} che siano “ben parentesizzate”.

Esercizio 08

Disegna il diagramma degli stati di un DPDA che riconosce solo sequenze sull’alfabeto {a, b} della forma: $a^{2n}{b}^n$, dove n è un numero naturale (maggiore o uguale a zero).