Autômatos finitos possuem diversas aplicações práticas, como na detecção de sequências de caracteres em um texto. A função programa do autômato abaixo apresenta um autômato que reconhece sequências sobre o alfabeto Σ = {a, b, c} e uma gramática livre de contexto que gera um subconjunto de Σ*, em que λ representa a palavra vazia. Autômato: M = (S, Σ, δ, s0, F), onde S = {0, 1, 2, 3, 4, 5}, s0 = 0 (estado inicial), F = {5}, Σ = {a, b, c}. A função δ pode ser representada pela tabela abaixo (Tabela 1). A gramática é apresentada em Gramática 1. Analisando a gramática e o autômato acima, conduz-se que:

1) Linguagem reconhecida pelo autômato (pela Tabela 1)

• O estado inicial é $0$ e o único estado de aceitação é $5$.
• O estado $5$ é sumidouro aceitador (com $a,b,c$ permanece em $5$), então basta alcançar $5$ uma vez.
• A única forma de chegar em $5$ é pela transição $\delta(4,c)=5$. Logo, o autômato aceita exatamente as palavras que conseguem levar o autômato ao estado $4$ e, em seguida, ler um $c$.

Vamos ver como chegar ao estado $4$:

• $0 \xrightarrow{a} 1$ (de $0$, com $b$ ou $c$ fica em $0$).
• Para avançar: $1 \xrightarrow{b} 2$, depois $2 \xrightarrow{b} 3$, depois $3 \xrightarrow{a} 4$.

Assim, para chegar a $4$ é necessário ler a sequência $abb a$ após algum ponto em que se leu um $a$ que colocou o autômato em $1$. Juntando tudo, o caminho completo até aceitar é: [ 0 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{b} 3 \xrightarrow{a} 4 \xrightarrow{c} 5 ] Ou seja, o autômato aceita qualquer string que contenha o padrão $abbac$ (como subcadeia), e depois disso qualquer coisa é aceita (por ser estado sumidouro aceitador).

Além disso, note um detalhe importante: em $1$ existe laço com $a$ ($\delta(1,a)=1$) e em $3$ existe transição com $b$ voltando para $1$ ($\delta(3,b)=1$). Isso permite repetir blocos do tipo $ab$ antes de completar o sufixo $abc$ do caminho final. De fato, a estrutura permite reconhecer strings que têm algum prefixo qualquer, depois zero ou mais repetições de $ab$, depois o trecho $abc$ (na reta final para chegar em $5$), e depois qualquer sufixo.

Isso corresponde à expressão regular: [ (a+b+c)^*,(ab)^*,abc,(a+b+c)^* ]

2) Conferindo as alternativas

• D) fala em prefixo ababc. O autômato não exige prefixo fixo, e o padrão que leva ao aceite é associado a chegar em $4$ e ler $c$ (padrão essencial ligado a $\delta(4,c)$), não a obrigar o início do string.
• C) diz que a linguagem do autômato é a mesma da gramática. A gramática dada gera um subconjunto de $\Sigma^*$ (e sua forma não indica diretamente que ela gere exatamente todos os strings contendo esse padrão), então não é a melhor conclusão.
• E) coincide com a caracterização por expressão regular do comportamento do autômato.

Portanto, a conclusão correta é que a linguagem reconhecida pelo autômato é a mesma da expressão regular apresentada em E.

Alternativa correta: (E).