Quelles sont les langues acceptées dans le PDA?

Question

Je n'arrive pas à comprendre la notation des automates à pousser lorsque j'appuie sur des piles et que je les éclate.

Je comprends que la pile doit être vide pour que la chaîne soit acceptée.

Voici mon PDA:

Si je crée un schéma de transition pour dire entrée 0011 je le faire comme ceci:

State   Input   Stack 

q0    0011   ɛ 

q0    011   0 

q0    11   00 

q0    1    100 

q0    ɛ    1100 

Depuis l'entrée est vide et la pile n'est pas vide, ceci n'est pas accepté?

Donc, si je mets une entrée comme bien c'est la chose ... Je suis sûr que c'est faux parce que si je mets une chaîne dans le PDA, il n'acceptera pas.

Je suppose pour résumer ma question réelle, est la notation pour le premier non-terminal (0, ɛ/0) (1, ɛ \ 1) Est-ce que cela signifie à l'entrée 0 ajouter 0 à la pile (même pour l'entrée 1, faire le contraire)? Pour le deuxième terminal, cela signifie-t-il que ... Eh bien, c'est ce qui me déroute (est-ce que je retire des chaînes de la pile ou de l'entrée?) J'imagine que je dois retirer des articles de la pile?

Est-ce que cela signifie que le langage accepté par ce PDA est l'ensemble vide? Si non, pouvez-vous expliquer où je vais mal?

Answer 1

Il existe différentes conventions, mais une convention commune est que vous acceptez quand:

1. L'entrée est épuisé; et
2. Vous êtes un état en cours d'acceptation; et
3. La pile est vide.

Vous pouvez vraiment utiliser plusieurs sous-ensembles de ces règles, et utiliser d'autres ensembles de règles, et obtenir des systèmes qui fonctionnent également pour les langages sans contexte. Les machines auraient des interprétations différentes dans ces systèmes, mais le pouvoir expressif serait le même.

En supposant le système à trois points ci-dessus, comme le souligne Welbog, ce PDA accepte le langage des palindromes de longueur égale sur l'alphabet {0, 1}. Parlons de ce que fait chaque état.

1. q0 lit soit 0 ou 1 et expulse 0 ou 1, respectivement, sur la pile, encore et encore aussi longtemps que vous le souhaitez. Si vous lisez la chaîne x, vous insérez la chaîne x dans la pile.

2. q1 lit soit 0 ou 1 et, si vous avez ce symbole sur le dessus de la pile, pops tout, plus et gagner plus aussi longtemps que vous le souhaitez. Si vous lisez la chaîne x, vous faites apparaître x^R sur la pile.

Si nous faisons q1 un état acceptant, et exiger que la pile soit vide lorsque l'entrée est épuisée, cela implique:

1. On est passé de x^R, si x a été lu alors que dans l'état q1 .
2. La pile contient x^R si nous lisons x^R à l'état q0.
3. Nous lisons x^R puis x et accepté, donc nous acceptons que des chaînes comme x^R x, soit palindromes même longueur
4. De plus, toute palindrome même longueur a un chemin à travers ce PDA qui entraîne qu'elle soit acceptée, étant donné que la PDA peut rester dans q0 pour |x|/2 symboles d'entrée, la transition à q1 et lire les |x|/2 restants. Puisque le PDA n'est pas déterministe, cela suffit pour dire que la chaîne est acceptée.