Autômatos são usualmente representados na forma de um grafo dirigido, onde estados são representados por círculos, sendo que estados finais são representados por círculos duplos, e as transições por arestas rotuladas com os símbolos que disparam a transição entre os dois estados conectados. Uma outra forma de representar um autômato, mais apropriada para fins de processamento automático, é através de tabelas de transição.
Disponível em:
Acesso em: 30 abril. 2018 (adaptado).
Considere o diagrama de estados de um autômato finito determinístico M ilustrado abaixo.
Sobre esse autômato, assinale a alternativa falsa.
Soluções para a tarefa
Resposta b
O autômato rejeita a palavra 0110011 pois não da para formá-la
se for tentar formar, o automato falha.
Para tentar formar basta andar pelos estados do automato. Ele tem que iniciar em q0 e terminar em q0 (estados inicial e final)
q0 - q2 - q3 - q2 - q0 - q2 - q3 - q2
Aqui foi formada a palavra 0110011 , porém o automato não terminou ainda pois não chegou no seu estado final q0. então não é possivel criar essa palavra
Para a palavra ser aceitavel teria que ter mais um 0 no final dela 0110011 0
A alternativa falsa é que M aceita a palavra 0110011, o que torna correta a alternativa b).
Para resolvermos esse exercício, temos que saber que um automato finito, que pode também ser chamado de máquina de estados, é a representação de uma máquina de reconhecimento de linguagens.
Assim, dada uma palavra (uma palavra é uma cadeia de caracteres) como entrada para esse automato, sua função é verificar se essa palavra pertence à linguagem aceita pela máquina através da transição dos elementos presentes na palavra. No caso do automato, o seu estado final é o estado q0, que também é o estado inicial.
Essa transição é feita através de estados, e, para que a transição ocorra, é necessário que haja uma seta para um outro estado que contenha o elemento presente na posição atual da palavra.
Com isso, observando o automato, podemos testar as palavras e verificar se pertencem à linguagem através das transições.
Para 110, partindo de q0, temos a seguinte sequência:
→ q0, entrada em 1 → transição para q1.
→ q1, entrada em 1 → transição para q0.
→ q0, entrada em 0 → transição para q2.
→ Assim, o estado final não é um estado de aceitação. Com isso, essa palavra é rejeitada.
Repetindo o processo para as palavras 0110011 e 110101, é possível verificar que a palavra 0110011 não possui seu último estado sendo q0, que é o único estado de aceitação.
Com isso, podemos concluir que a alternativa falsa é que M aceita a palavra 0110011, o que torna correta a alternativa b).
Para aprender mais, acesse
https://brainly.com.br/tarefa/22834222
https://brainly.com.br/tarefa/21285520
