NPDA por aceptar el lenguaje L = {anb(2n) | n>=1} U {anbn | n>=1}

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final 

Problema – Diseñar un PDA no determinista que acepte el lenguaje L = { un ^ n  [Tex]b^{2n} [/Tex]: n>=1} U { un ^ n  [Tex]b^{n} [/Tex]: n>= 1}, es decir,

L = {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ......} 
          U {ab, aabb, aaabbb, aaaabbbb, ......} 

En cada string, el número de a va seguido del doble número de b o el número de a va seguido del mismo número de b. 

Explicación: aquí, debemos mantener el orden de a y b. Es decir, todas las a vienen primero y luego todas las b. Por lo tanto, necesitamos una pila junto con el diagrama de estado. La pila mantiene el conteo de a y b. Tomaremos 2 alfabetos de pila:

\Gamma = { a, z } 

Donde,  \Gama  = conjunto de todo el alfabeto de pila z = símbolo de inicio de pila 

Enfoque utilizado en la construcción de PDA: al diseñar un NPDA, cada ‘a’ viene antes de ‘b’. Si viene ‘b’ entonces

  • Para  un ^ n  [Tex]b^{n} [/Tex]: Cada vez que aparezca ‘a’, empújelo en la pila y si ‘a’ vuelve a aparecer, también empújelo en la pila.
  • Para  un ^ n  [Tex]b^{2n} [/Tex]: Cada vez que aparece ‘a’, presione ‘a’ dos veces en la pila y si ‘a’ aparece de nuevo, haga lo mismo. Cuando aparezca ‘b’ (recuerde que b viene después de ‘a’), extraiga una ‘a’ de la pila cada vez.

De modo que la pila se vacía. Si la pila está vacía, podemos decir que la PDA acepta la string. 

Funciones de transición de pila –

\delta(q0, a, z) \vdash (q1, az)\delta(q0, a, z) \vdash (q3, aaz)\delta(q1, a, a) \vdash (q1, aa)\delta(q1, b, a) \vdash (q2, \epsilon) \delta(q2, b, a) \vdash (q2, \epsilon) \delta(q2, \epsilon, z) \vdash (qf1, z)   \delta(q3 a, a) \vdash (q3, aaa)\delta(q3, b, a) \vdash (q4, \epsilon) \delta(q4, b, a) \vdash (q4, \epsilon) \delta(q4, \epsilon, z) \vdash (qf2, z)   

Donde, q0 = Estado inicial qf1, qf2 = Estado final  \epsilon  = indica operación emergente 

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje L ={ un ^ n  [Tex]b^{2n} [/Tex]: n>=1} U { un ^ n  [Tex]b^{n} [/Tex]: n >=1}.

Publicación traducida automáticamente

Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *