Autômatos de estados finitos: estados finais

Em nosso curso de conceitos de linguagem de programação, nosso instrutor afirmou que não há problema em um estado final levar a outro estado em um diagrama de estados finitos.

Mas esse parece ser um conceito fundamentalmente contraditório. Como um estado final, por definição, é aquele que termina as transições, ou seja, quando você o alcança, não há mais nada a fazer.

E, no entanto, ele apresentou um slide como este, onde os estados finais são representados por dois círculos ... Como é possível que B, D, E e H sejam estados finais quando claramente não são?

Você parece ter um mal-entendido entre modelos generativos e modelos "reconhecendo".

A gramática que você tem à direita gera palavras aplicando regras, iniciando na variável inicial e interrompendo depois que não houver mais variáveis.

Os autômatos, no entanto, reconhecem um idioma da seguinte maneira: você alimenta o autômato uma palavra, letra por letra, e o autômato realiza transições com base nas letras dadas a ele.

Se, depois de ler todas as letras, o autômato terminar em um estado de aceitação (aka final), então dizemos que o autômato aceita a palavra.

Portanto, é melhor pensar neles como estados "aceitos", em vez de estados "finais", embora ambos os termos sejam comumente usados.

um estado final, por definição, é aquele que termina as transições, ou seja, quando você o alcança, não há mais nada a fazer.

A fonte da sua confusão é que essa não é a definição. "Estado final" é uma má escolha de nome, e a maioria dos autores parece preferir "estado de aceitação". A definição é que o autômato aceita se sua execução termina em um estado final / de aceitação e rejeita o contrário.

Na verdade, é confuso! Para resolver seu problema, chame-os de estados "aceitos" em vez de "finais". Porque é isso que eles realmente são, apenas um marcador que nos diz que, neste momento, a cadeia processada pertence ao idioma.

"um estado final por definição é aquele que termina as transições, ou seja, que quando você o alcança, não há mais nada a fazer."

Na convenção tradicional de trabalhar com aceitadores (ou seja, autômatos de estados finitos que informam se uma determinada string pertence / não pertence a um idioma), um estado final é aquele que, quando alcançado com uma string vazia (a entrada era consumido inteiramente) significa que a cadeia inicial é aceita, ou seja, faz parte do idioma do autômato.

Como você pode ver. A gramática dada diz A -> a. Portanto, o automaom aceita terminar na string "a". Mas também permite A -> aB -> abD -> abc, então a string "abc" também é aceita. Se terminarmos a string nesse ponto, estaremos em um estado final e, portanto, a string foi aceita. Mas ainda podemos querer que a string "ab" seja aceita. Portanto, precisamos garantir que {"a", "ab", "abc"} sejam todos aceitos pelo autômato. Não veja os estados finais como um estado tal que, se o inserirmos, talvez nunca o abandonemos, veja-o como um estado para nos dizer se nossa string atual é aceita ou não.