Turmas - 1º Semestre de 2016
Turmas
1º Semestre de 2016

Uma palavra α é uma subpalavra de outra palavra β se for possível escrever β como sendo γαδ, admitindo-se a possibilidade de γ ou δ ou ambos serem palavras vazias (ε). Quantas subpalavras distintas a palavra computador pode fornecer?

1. 54
2. 55
3. 56
4. 57
5. 58

Um autômato finito determinístico é uma máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para cada cadeia de entrada. Qual linguagem o autômato finito determinístico apresentado a seguir reconhece?

M = ({a, b, c}, {q₀, q₁, q₂}, δ, q₀, {q₂})

1. L = {aⁱbⁱcⁱ | i ≥ 0}
2. L = {aⁱbⁱcⁱ | i > 0}
3. L = {aⁱb^jc^k | i ≥ 0, j ≥ 0 e k ≥ 0}
4. L = {aⁱb^jc^k | i > 0, j > 0 e k > 0}
5. L = {aⁱb^jc^k | i ≥ 0, j > 0 e k > 0}

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. Isso o distingue do autômato finito determinístico (AFD), onde o próximo estado possível é univocamente determinado. Embora AFD e AFN possuam definições distintas, pode ser mostrado na teoria formal que eles são equivalentes e, deste modo, para qualquer AFN dado, pode-se construir um AFD equivalente e vice-versa. Considere o AFN apresentado a seguir:

M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

Qual dos seguintes autômatos finitos determinísticos é equivalente ao autômato finito não-determinístico apresentado?

1. M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

   

2. M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

   

3. M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

   

4. M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

   

5. M = ({0, 1}, {q₀, q₁, q₂}, δ, q₀, {q₂})

   

Dado o autômato finito não-determinístico com movimentos vazios, construído utilizando o algoritmo de Thompson.

M = ({a, b}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁, q₁₂, q₁₃, q₁₄, q₁₅, q₁₆, q₁₇}, δ, q₀, {q₁₇})

1. Converta, usando o método da construção de subconjuntos, o autômato finito não-determinístico com movimentos vazios apresentado para um autômato finito determinístico.
2. Minimize, se possível, o número de estados do autômato do item a.