Construir autómatas pushdown para L = {a(2*m)c(4*n)dnbm | m, n ≥ 0}

Requisito previo: autómatas pushdown , la aceptación de autómatas pushdown por parte del PDA de estado final
juega un papel muy importante en la tarea de diseño del compilador. Por eso es necesario tener una buena práctica en PDA. Nuestro objetivo es construir un PDA para L = {a ^(2*m) c ^(4*n) d ⁿ b ^m | m, n ≥ 0}

Ejemplos –

Input: aaccccdb
Output: Accepted

Input: aaaaccccccccddbb
Output: Accepted

Input: acccddb
Output: Not Accepted 

Enfoque utilizado en esta PDA:
puede haber cuatro casos mientras se procesa la string de entrada dada.

Caso-1: m=0 – En este caso, la string de entrada tendrá la forma {c ^(4*n) d ⁿ }. En esta condición, siga presionando c en la pila hasta que nos encontremos con ‘d’. Al recibir ‘d’, verifique si la parte superior de la pila es ‘c’, luego extraiga ‘cccc’ de la pila. Continúe abriendo cccc hasta que se procesen todas las d de la string. Si llegamos al final de la string de entrada y la pila se vacía, entonces llegamos al estado final, es decir, acepta la string de entrada, de lo contrario se mueve al estado muerto.

Caso-2: n=0 – En este caso, la string de entrada tendrá la forma {a ^(2*m) b ^m }. En esta condición, siga empujando a en la pila hasta que nos encontremos con ‘b’. Al recibir b, verifique si la parte superior de la pila es ‘a’, luego extraiga ‘aa’ de la pila. Continúe sacando aa hasta que se procesen todas las b de la string. Si llegamos al final de la string de entrada y la pila se vacía, entonces llegamos al estado final, es decir, acepta la string de entrada, de lo contrario se mueve al estado muerto.

Caso-3: m, n>0 – En este caso, la string de entrada tendrá la forma {(a ^(2*m) c ^(4*n) d ⁿ b ^m }. En esta condición, siga presionando a y c en la pila hasta que nos encontremos con ‘d’. Al recibir d, verifique si la parte superior de la pila es ‘c’, luego saque ‘cccc’ de la pila. Siga sacando cccc hasta que se procesen todas las d de la string de entrada. Luego Al recibir b, verifique si la parte superior de la pila es ‘a’, luego extraiga ‘aa’ de la pila. Siga sacando aa hasta que se procesen todas las b de la string de entrada. Si llegamos al final de la string de entrada y la pila se vacía , luego alcance el estado final, es decir, acepte la string de entrada; de lo contrario, pase al estado muerto.

Caso-4: m, n=0 – En este caso, la string de entrada estará vacía. Por lo tanto salta directamente al estado final.

Nota –

1. Usamos (b, a/€, aa) para sacar 2 a, es decir, aa cuando nos encontramos con b.
2. Usamos (d, c/€, cccc) para mostrar 4 c, es decir, cccc cuando nos encontramos con d.