Acceptation des automates de refoulement
Il existe deux manières différentes de définir l'acceptabilité des PDA.
Acceptabilité de l'état final
Dans l'acceptabilité de l'état final, un PDA accepte une chaîne lorsque, après avoir lu la chaîne entière, le PDA est dans un état final. À partir de l'état de départ, nous pouvons effectuer des mouvements qui se terminent dans un état final avec toutes les valeurs de pile. Les valeurs de la pile ne sont pas pertinentes tant que nous nous retrouvons dans un état final.
Pour un PDA (Q, ∑, S, δ, q 0 , I, F), le langage accepté par l'ensemble des états finaux F est -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}
pour toute chaîne de pile d'entrée x.
Acceptabilité de la pile vide
Ici, un PDA accepte une chaîne lorsque, après avoir lu la chaîne entière, le PDA a vidé sa pile.
Pour un PDA (Q, ∑, S, δ, q 0 , I, F), le langage accepté par la pile vide est -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}
Exemple
Construisez un PDA qui accepte L = {0n 1n | n ≥ 0}
Solution
Ce langage accepte L = {ε, 01, 0011, 000111, .............................}
Ici, dans cet exemple, le nombre de ‘a’ et ‘b’ doivent être les mêmes.
Au départ, nous mettons un symbole spécial ‘$’ dans la pile vide.
Puis à l'état q2, si nous rencontrons l'entrée 0 et top est Null, nous poussons 0 dans la pile. Cela peut itérer. Et si nous rencontrons l'entrée 1 et top est 0, nous popons ce 0.
Puis à l'état q3, si nous rencontrons l'entrée 1 et top est 0, nous popons ce 0. Cela peut également itérer. Et si nous rencontrons l'entrée 1 et top est 0, nous faisons apparaître l'élément supérieur.
Si le symbole spécial '$' est rencontré en haut de la pile, il est sorti et il passe finalement à l'état d'acceptation q 4 .
Exemple
Construisez un PDA qui accepte L = {ww R | w = (a + b) *}
Solution
Au départ, nous mettons un symbole spécial «$» dans la pile vide. À l'étatq2, la west en cours de lecture. En étatq3, chaque 0 ou 1 est sauté lorsqu'il correspond à l'entrée. Si une autre entrée est donnée, le PDA passera à un état mort. Lorsque nous atteignons ce symbole spécial '$', nous passons à l'état d'acceptationq4.