Turmas - 2º Semestre de 2014
Turmas
2º Semestre de 2014

Algebricamente, um Autômato Finito M pode ser definido como uma quíntupla:

• Q é um conjunto finito de estados;
• Σ é um alfabeto (finito e não-vazio) de entrada;
• δ é uma função de transição, δ : Q x Σ → Q;
• q₀ é o estado inicial, q₀ ∈ Q;
• F é um conjunto de estados finais, F ⊆ Q.

No caso de q₀ ∈ F, pode-se concluir que esse Autômato Finito:

1. não aceita a cadeia vazia
2. não tem outros estados finais
3. é determinístico
4. aceita a cadeia vazia
5. é não determinístico

Na Teoria da Computação, um Autômato Finito Não-Determinístico (AFN) é uma máquina de estados finita, onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Essa característica o distingue do Autômato Finito Determinístico (AFD), onde o próximo estado possível é univocamente determinado. Autômatos Finitos Não-Determinísticos reconhecem exatamente o conjunto de Linguagens Regulares que são, dentre outras coisas, úteis para a realização da Análise Léxica e reconhecimento de padrões. Qual a Linguagem Regular reconhecida pelo Autômato Finito Não-Determinístico apresentado a seguir:

1. L = {w | w possui palavras no formato aⁿb^m, com n > 0 e m > 0}
2. L = {w | w possui palavras no formato aⁿb^m, com n ≥ 0 e m ≥ 0}
3. L = {w | w possui palavras no formato aⁿbⁿ, com n > 0}
4. L = {w | w possui palavras no formato aⁿbⁿ, com n ≥ 0}
5. L = {w | w possui palavras no formato aⁿb^m, com n > 0 e m ≥ 0}

As Expressões Regulares (ER) sobre um alfabeto Σ podem ser definidas recursivamente, como segue:

1. Ø é uma expressão regular e denota a linguagem vazia.
2. ε é uma expressão regular e denota a linguagem contendo exclusivamente a palavra vazia, ou seja, {ε}.
3. Qualquer símbolo x pertencente a Σ é uma expressão regular e denota a linguagem contendo a palavra unitária x, ou seja, {x}.
4. Se r e s são expressões regulares e denotam as linguagens R e S, respectivamente, então:
   1. (r+s) é uma expressão regular e denota a linguagem R ∪ S.
   2. (rs) é uma expressão regular e denota a linguagem RS = {uv | u ∈ R e v ∈ S}.
   3. (r*) é uma expressão regular e denota a linguagem R*.

Assinale a alternativa que apresenta, corretamente, uma Expressão Regular (ER) que denota todas as strings de a's e b's que tenham pelo menos dois b's consecutivos:

1. (a*+bb)(a+ba)*(a+b)*
2. (a+ba)*bb(ba+a)*
3. (a+b)*ba*b(a+b)*
4. (a+bb)*(bb+a)*
5. (a+ba)*bb(a+b)*