Pour une grammaire sans contexte G sur Σ = {0, 1, 2}, avec variable de départ S:
S → 0S0 | 1S1 | 2S2 | Y
Y → 22Pour une grammaire sans contexte, comment la convertir en un automate équivalent?
Comment puis-je transformer cela en un équivalent automate Push-Down
Un automate pushdown peut pousser des symboles sur le dessus d'une pile et les pop off. Il peut également baser ses transitions sur le symbole de pile le plus haut. Nous devons penser à un mécanisme qui nous permettra d'accepter le bon langage en manipulant notre pile.
La langue de votre grammaire génère présente les caractéristiques suivantes:
22 au milieu{0, 1, 2}. Autrement dit, il lit les mêmes vers l'avant que vers l'arrière.Nous devons "nous souvenir" du début de la chaîne pour pouvoir dire si la fin de la chaîne est répétée à l'envers. C'est un bon cas d'utilisation pour une pile: nous pouvons pousser les symboles sur la pile comme nous les voyons, puis les enlever au fur et à mesure que nous les relisons. Une autre note: nous savons que nous ne pouvons que commencer à relire après avoir lu 22.
D'abord, nous lisons tout et le pousser sur la pile jusqu'à ce qu'on trouve « 22 »:
Q s S Q' S'
----------------------
// read 0s and 1s and push them on the stack
q0 0 Z q0 0Z
q0 0 0 q0 00
q0 0 1 q0 01
q0 1 Z q0 1Z
q0 1 0 q0 10
q0 1 1 q0 11
// if you read a 2, pus it on the stack and
// go to a new state where we look for a second 2
q0 2 Z q1 2Z
q0 2 0 q1 20
q0 2 1 q1 21
// if you read a 2 and then 0 or 1, go back to the
// initial state and keep reading input. otherwise,
// if you find a second two, proceed
q1 0 2 q0 02
q1 1 2 q0 12
q1 2 2 q2 22
// assume the '22' we just saw was not the one in
// the middle of the input string and that we need
// to keep reading input.
q2 0 2 q0 02
q2 1 2 q0 12
q2 2 2 q2 22
// assume the '22' we just saw was the one in the
// middle of the input string and that we now need
// to start reading from the stack.
q2 - 2 q3 -
q3 - 2 q4 -
q4 0 0 q4 -
q4 1 1 q4 -
q4 2 2 q4 -
q4 - Z q5 Z
// we read a string in the language and are
// ready to accept in q5. go to dead state q6
// explicitly if still have input.
q5 0 Z q6 Z
q5 1 Z q6 Z
q5 2 Z q6 Z
// consume the rest of the input in the dead state.
q6 0 Z q6 Z
q6 1 Z q6 Z
q6 2 Z q6 Z
Les transitions pour q5 et q6 ne sont pas strictement nécessaire si vous définissez écraser la machine pour signifier la chaîne est définitivement rejeté, ce qui est typique. J'inclus ces transitions de sorte que le PDA épuisera gracieusement toutes les entrées sans s'écraser.
Ce PDA n'est pas déterministe. Il n'y a pas de PDA déterministe pour ce langage. Fondamentalement, après avoir lu toute sous-chaîne 22, nous devons deviner si cette instance de 22 était celle du milieu. Si c'est le cas, nous devons commencer à lire la chaîne initiale pour voir si nous avons un palindrome. Sinon, nous devons continuer à pousser des symboles sur la pile.