Considere uma linguagem L, definida sobre o alfabeto Σ = {a, b}, aonde todas as strings possuem sempre o mesmo número de a’s e b’s, em qualquer or...

A linguagem L é uma linguagem livre de contexto, pois pode ser gerada por uma gramática livre de contexto. Uma possível gramática para L é: S → aSbS | bSaS | ε A máquina abstrata M que reconhece L pode ser um autômato de pilha não determinístico (APND) com uma única pilha. O APND começa no estado inicial q0 e empilha um símbolo especial Z0 na pilha. Em seguida, para cada símbolo de entrada lido, o APND pode fazer uma das seguintes transições: 1. Se o topo da pilha contém um a e o símbolo de entrada é b, o APND desempilha o a e lê o b. 2. Se o topo da pilha contém um b e o símbolo de entrada é a, o APND desempilha o b e lê o a. 3. Se o topo da pilha contém Z0 e o símbolo de entrada é a, o APND empilha um a e lê o a. 4. Se o topo da pilha contém Z0 e o símbolo de entrada é b, o APND empilha um b e lê o b. O APND aceita a entrada se, após ler todos os símbolos de entrada, a pilha estiver vazia. Como a linguagem L pode ser reconhecida por um APND, ela é uma linguagem livre de contexto.