Appuyez Automates une langue

Question

Je veux concevoir un automate pushdown pour la langue

L = { a^i b^j c^k | i = j or k <= j <= 2k} 

La solution proposée par l'instructeur comme illustré dans le schéma suivant.

Mais mon souci ici est, qu'il ne gère pas la chaîne de la forme lorsque |2c| > |b|. C'est quand dans l'état q8, et si tous les B sont empilés, mais l'entrée C n'est pas encore terminée. Cette transition n'est pas capturée ici.

Est-ce que mon problème est correct? Ou la solution proposée est un PDA correct. Rappelez-vous que j> = k, ce qui signifie | b |

Answer 1

> = | c |.

Si tous les "b" en entrée étaient lus, alors le nombre de B empilés est supérieur (ou égal) au nombre de "c" à lire dans l'entrée.

• Si j = k, alors il utilisera la transiction de q8 à q8 jusqu'à la fin de l'entrée. Si j = 2k, il lira un "c" (q8 -> q9) et sortira deux B de la pile (q9 -> q8), donc seulement les chaînes avec | b | = 2 | c | peut être accepté. Si j < 2k, il utilisera q8 -> q9 et q9 -> q8 jusqu'à ce que le nombre de B empilés soit égal au nombre de "c" à lire dans l'entrée. Ensuite, il utilisera q 8-> q8 jusqu'à la fin de l'entrée.