Essa pergunta também está no material:
Respostas
a) Para construir um AFD que reconheça a linguagem {0, 1}* - {0, 01, 10}, podemos seguir os seguintes passos: 1. Comece criando um estado inicial. 2. Em seguida, crie um estado para cada símbolo do alfabeto {0, 1}. 3. Adicione transições entre os estados de acordo com as regras da linguagem. - Por exemplo, se estivermos no estado inicial e recebermos um 0, podemos transicionar para o estado que representa o símbolo 0. - Se estivermos no estado que representa o símbolo 0 e recebermos um 1, podemos transicionar para um estado de aceitação. - Se estivermos em qualquer estado que não seja de aceitação e recebermos um 0 ou 1, podemos permanecer no mesmo estado. 4. Marque um ou mais estados como estados de aceitação, dependendo dos critérios da linguagem. - Nesse caso, podemos marcar o estado que representa o símbolo 1 como estado de aceitação. b) Para construir um AFD que reconheça a linguagem {w ∈ {0, 1}* | w tem número par de 0s e um único 1}, podemos seguir os seguintes passos: 1. Comece criando um estado inicial. 2. Em seguida, crie um estado para cada símbolo do alfabeto {0, 1}. 3. Adicione transições entre os estados de acordo com as regras da linguagem. - Por exemplo, se estivermos no estado inicial e recebermos um 0, podemos transicionar para um estado que representa um número ímpar de 0s. - Se estivermos no estado que representa um número ímpar de 0s e recebermos um 0, podemos transicionar para um estado que representa um número par de 0s. - Se estivermos no estado que representa um número par de 0s e recebermos um 0, podemos transicionar para um estado que representa um número ímpar de 0s. - Se estivermos em qualquer estado e recebermos um 1, podemos transicionar para um estado de aceitação. 4. Marque um ou mais estados como estados de aceitação, dependendo dos critérios da linguagem. - Nesse caso, podemos marcar o estado que representa um número par de 0s e um único 1 como estado de aceitação. Espero que isso ajude! Se você tiver mais dúvidas, é só perguntar.
Responda
Para escrever sua resposta aqui, entre ou crie uma conta