Alternativa A
Análise Detalhada do Autômato
Para resolver esta questão, precisamos interpretar o diagrama de transição de estados fornecido na imagem. O texto identifica o dispositivo como um Autômato Finito Determinístico (AFD).
1. Estrutura do Autômato
- Estado Inicial: q0 (indicado pela seta de entrada).
- Estado Final: q4 (indicado pelo círculo duplo).
- Alfabeto de Entrada: \Sigma = \{a, b, c\}.
- Transições: As setas representam as transições entre estados. Os rótulos seguem a notação
entrada:saida,acao (ex: a:a,R). Para fins de linguagem aceita em um AFD, focamos apenas no símbolo de entrada que dispara a transição.
2. Caminhos Possíveis (Do Inicial ao Final)
Existem três caminhos distintos para sair do estado inicial q0 e chegar ao estado final q4:
- Caminho Superior (Via q1):
- Sai de q0 para q1 com entrada
a. - Fica em q1 com laço de entrada
a (pode repetir quantas vezes quiser). - Sai de q1 para q4 com entrada
b. - Expressão Regular deste caminho: a a^* b, que simplifica para $a^+ b$.
- Strings aceitas: ab, aab, aaab, \dots (um ou mais
as seguidos de um b). - Caminho Central (Via q2):
- Sai de q0 para q2 com entrada
b. - Fica em q2 com laço de entrada
c. - Sai de q2 para q4 com entrada
b. - Expressão Regular deste caminho: b c^* b.
- Strings aceitas: bb, bcb, bccb, \dots
- Caminho Inferior (Via q3):
- Sai de q0 para q3 com entrada
c. - Fica em q3 com laços de entrada
a e b. - Sai de q3 para q4 com entrada
c. - Expressão Regular deste caminho: c (a \cup b)^* c.
- Strings aceitas: cc, cac, cbc, \dots
3. Linguagem Total
A linguagem aceita pelo autômato é a união desses três caminhos:
L = \{ a^n b \mid n \ge 1 \} \cup \{ b c^n b \mid n \ge 0 \} \cup \{ c w c \mid w \in \{a,b\}^* \}
4. Análise das Alternativas
A pergunta pede qual conjunto pertence à linguagem (ou seja, é um subconjunto válido):
- (A) $\{ a^n b \mid n \ge 1 \}$: Este conjunto corresponde exatamente ao Caminho Superior. Como todas as strings deste conjunto são aceitas pelo autômato, este é um subconjunto válido da linguagem. Correto.
- (B) \epsilon (string vazia): Não é aceita, pois não há transição direta de q0 para q4 sem ler símbolos, e q0 não é estado final. Incorreto.
- (C) \{ a^* b^* c^* \}$**: Contém strings como $abc, que não podem ser geradas por nenhum dos caminhos (não há caminho que aceite
a seguido de c). É um superconjeto, não um subconjeto. Incorreto.** - (D) $\{ a^n b^n \mid n \ge 1 \}$: Requer contagem igual de
as e bs, o que exige memória além de um autômato finito (seria uma Máquina de Pilha). O autômato aqui aceita qualquer número de as seguido de um único b. Incorreto.
Conclusão
A alternativa correta é a A, pois descreve um conjunto de strings que são perfeitamente aceitas pelo primeiro ramo do autômato (começar com a, repetir a e terminar com b).