É possível verificar que esta linguagem é livre de contexto. Consequentemente esta linguagem pode ser reconhecida por um autô´mato com pilha. Como uma máquina de Turing é um autô´mato mais genérico, a linguagem também pode ser reconhecida por uma máquina de Turing.