Automa a pila

[noipo]

Devo fare quest'esercizio:
Costruire un automa a pila che riconosca il linguaggio generato dalla grammatica:
$S -> BC | AD$
$A -> aA | \epsilon$
$B -> aBb | \epsilon$
$C -> cC | \epsilon$
$D -> bDc | \epsilon$
Dire se le stringhe $ac$ $aabbcc$ e $bbbccc$ appartengono al linguaggio. In caso positivo costruire l'albero di derivazione, in caso negativo mostrare come si comporta l'automa costruito.

Ho fatto così per trovare l'automa:
$delta (q, epsilon, Z_0) = {(q,S)}$
$delta (q, epsilon, S) = {(q,CB), (q,DA)}$
$delta (q, epsilon, A) = {(q,Aa), (q,epsilon)}$
$delta (q, epsilon, B) = {(q,bBa), (q,epsilon)}$
$delta (q, epsilon, C) = {(q,Cc), (q,epsilon)}$
$delta (q, epsilon, D) = {(q,cDb), (q,epsilon)}$

e

$delta (q, a,a) = {(q,epsilon)}$
$delta (q, b,b) = {(q,epsilon)}$
$delta (q, c,c) = {(q,epsilon)}$

Quindi l'automa è: $<{q}, {a,b,c},{Z_0,S,A,B,C,D,a,b,c},delta, q, Z_0, Phi>$

Ora, come faccio a sapere se le stringhe $ac$ $aabbcc$ e $bbbccc$ appartengono al linguaggio?

Grazie

[noipo]

Nessuno?

[apatriarca]

Se non sbaglio aa e c appartengono al linguaggio. aa si ottiene come segue S -> AD -> aAD -> aaAD -> aaD -> aa mentre c si ottiene come segue S -> BC -> C -> cC -> c. ac non si può ottenere invece perché D inserisce una b all'interno della stringa prima di c, mentre B inserisce una b dopo la a. Nota comunque che si vede abbastanza facilmente che il simbolo A viene sostituito con una sequenza di lunghezza arbitraria di a, il simbolo B inserisce una sequenza di a seguita da una sequenza della stessa lunghezza di b, il simbolo C inserisce una sequenza di lunghezza arbitraria di c e il simbolo D inserisce una sequenza di b seguita da una sequenza di lunghezza uguale di c. Riassumendo una stringa appartiene al linguaggio se è fatta in uno dei due modi seguenti:
1. Una sequenza di lunghezza arbitraria di a seguita da una sequenza di b di lunghezza N e da una sequenza di c di ugual lunghezza N.
2. Una sequenza di lunghezza N di a seguita da una sequenza di uguale lunghezza N di b seguita da una sequenza di lunghezza arbitraria di c.

[noipo]

Grazie per la risposta. Quindi vedo se una stringa appartiene al linguaggio semplicemente se riesco ad ottenerla dalla grammatica?

[apatriarca]

O dall'automa o dall'espressione regolare o .. da quello che ti sembra più comodo.

[noipo]

Capito, grazie