- Na questão 1, eu infelizmente escrevi "x0x1...xn (note a indexação)" e isso, apesar de formalmente correto, confunde de duas formas:
- O que é para notar é: começa de 0 e vai da esquerda prá direita.
- O que não é prá notar é o n. O comprimento da palavra não tem nada a ver com o módulo, nas partes (a) e (b); as palavras podem ter qualquer comprimento.
Como provar que um dado AD reconhece uma certa linguagem? Bom, é preciso ser criativo. Dei uns exemplos em aula, mas foram poucos.
Uma idéia que costuma funcionar é encontrar, para cada estado p, uma descrição do conjuto de palavras cujo processamento leva de s a p. Tendo encontrado essa descrição, o que falta, para mostrar sua validade, é mostrar que ela é compatível com as arestas - "se estou em p e processando a vou para q, isso bate com as descrições". Terminado isso, juntam-se as descrições correspondentes a estados finais.
Com autômatos grandes isso dá muito trabalho, e na correção da lista vou aceitar "demonstrações" menos detalhadas.
Notem que a sugestão acima não é o único jeito de se demonstrar que um certo autômato funciona.
Com autômatos grandes isso dá muito trabalho, e na correção da lista vou aceitar "demonstrações" menos detalhadas.
Notem que a sugestão acima não é o único jeito de se demonstrar que um certo autômato funciona.