Convertendo uma gramática livre de contexto em um PDA

Convertendo uma gramática livre de contexto em um PDA - minha solução está correta?

Estou revendo para o meu meio termo e queria postar isso para ver se alguém pode detectar algum erro. Eu devo fazer um PDA que reconheça esse CFG:

$\qquad\begin{align} S &\to R1R1R1 \\ R &\to 0R \mid 1R \mid \varepsilon \end{align}$

Aqui está a minha solução; Estou ciente de que esqueci de desenhar o segundo círculo em torno do meu estado de aceitação.

insira a descrição da imagem aqui

formal-languages automata context-free pushdown-automata Rafael
fonte

Seu curso provavelmente menciona o algoritmo de tradução padrão (simples). Você já tentou aplicá-lo? (Além disso, essa imagem é difícil de decifrar.) Qual é suposto ser o estado final? Finalmente, não que "verifique a minha resposta" perguntas tendem a obra não tão bem em SE (no caso em que a resposta é um chato "sim, não cometer erros".

Raphael

Verificar esta pergunta pode ajudar.

Lucas Mathieson

Respostas:

Essa linguagem simplesmente não reconhece nenhuma string em $\{0,1\}^*$ que tem pelo menos três $1$ está nele?

Nesse caso, você só precisa de um autômato determinístico finito regular que pode contar até três para reconhecê-lo.

autômato finito que conta até três

Isso ocorre porque não estou disposto a fazer uma tradução direta dessa gramática, se é isso que você realmente deseja verificar: P

hugomg
fonte