Turmas - 1º Semestre de 2026A Máquina com Pilhas é um autômato determinístico que utiliza uma estrutura de pilha (LIFO) como memória de trabalho. Contudo, é com duas pilhas que se atinge a equivalência à Máquina de Turing, cujo modelo de fita infinita e cabeça de leitura/escrita estabelece o padrão de computabilidade. Desenvolva um autômato com pilha, definido sobre o alfabeto Σ = {0, 1, $}, capaz de realizar a adição de dois números binários. A entrada será fornecida no formato A$B, em que A e B representam os operandos e $ atua como delimitador. Após o processamento, a máquina deve gerar a sequência correspondente à soma binária. A seguir, são apresentados exemplos de entradas e os respectivos resultados esperados.
| Entrada | Saída | Status |
|---|---|---|
| 10$10 | 100 | aceita |
| 100$111 | 1011 | aceita |
| 1011$1010 | 10101 | aceita |
| 101$00 ou 01$101 | indiferente | rejeita |
| $ ou ε | indiferente | rejeita |
M = ({0, 1, $}, D)
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 