Turmas - 1º Semestre de 2017
Turmas
1º Semestre de 2017

(Hopcroft, 2002) A teoria de autômatos é o estudo dos dispositivos abstratos de computação, ou "máquinas". Antes de existirem os computadores, na década de 1930, Alan Turing estudou uma máquina abstrata que tinha todas as características dos computadores atuais, pelo menos no que se refere ao quanto eles poderiam calcular. O objetivo de Turing era descrever com exatidão o limite entre o que uma máquina de computação podia fazer e aquilo que ela não podia fazer; suas conclusões se aplicam não apenas às suas máquinas de Turing abstratas, mas também às máquinas reais de hoje. Analise as seguintes afirmativas a respeito dos conceitos centrais da teoria de autômatos:

1. Um string (ou às vezes palavra ou também cadeia) é uma sequência finita de símbolos escolhidos de algum alfabeto. Por exemplo, 01101 é um string do alfabeto binário Σ = {0, 1}.
2. O string vazio é o string com zero ocorrências de símbolos. Esse string, denotado por ε, é um string que pode ser escolhido de qualquer alfabeto.
3. Um conjunto de strings, todos escolhidos a partir de algum Σ*, onde Σ é um alfabeto específico, é chamado linguagem. Se Σ é um alfabeto, e L ⊆ Σ*, então L é uma linguagem sobre Σ. Note que uma linguagem sobre Σ não precisa incluir strings com todos os símbolos de Σ; assim, uma vez que estabelecemos que L é uma linguagem sobre Σ, também sabemos que ela é uma linguagem sobre qualquer alfabeto que seja um superconjunto de Σ.

A análise permite concluir que:

a. nenhuma das afirmativas está correta.

b. apenas as afirmativas I e II estão corretas.

c. apenas as afirmativas I e III estão corretas.

d. apenas as afirmativas II e III estão corretas.

e. todas as afirmativas estão corretas.

(Menezes, 2000) Um prefixo (respectivamente, sufixo) de uma palavra é qualquer sequência de símbolos inicial (respectivamente, final) da palavra. Uma subpalavra de uma palavra é qualquer sequência de símbolos contígua da palavra. Analise as seguintes afirmativas sobre prefixos, sufixos e subpalavras de uma palavra:

1. Os prefixos da palavra compatibilidade são formalmente definidos como: {ε, c, co, com, comp, compa, compat, compati, compatib, compatibi, compatibil, compatibili, compatibilid, compatibilida, compatibilidad, compatibilidade}.
2. 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 (ε).
3. Os sufixos da palavra arara são formalmente definidos como: {ε, a, ar, ara, arar, arara}.

A análise permite concluir que:

a. apenas a alternativa I está correta.

b. apenas a alternativa II está correta.

c. apenas a alternativa III está correta.

d. apenas as afirmativas I e II estão corretas.

e. apenas as afirmativas II e III estão corretas.

(Hopcroft, 2002) Um autômato finito determinístico (AFD) consiste em:

• Um conjunto finito de símbolos de entrada, frequentemente denotado por Σ;
• Um conjunto finito de estados, frequentemente denotado por Q;
• Uma função de transição que toma como argumentos um estado e um símbolo de entrada e retorna um estado, frequentemente denotado por δ;
• Um estado inicial, um dos estados de Q;
• Um conjunto de estados finais ou de aceitação F, sendo um subconjunto de Q.

Desenvolva um autômato finito determinístico sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui xzz ou zzz como prefixo, zzy ou zzz como subpalavra e zyy ou zzx como sufixo}.

(Ramos, 2009) Apesar do elevado interesse prático que recai sobre os autômatos finitos determinísticos, uma vez que eles servem como base para a construção de programas extremamente eficientes, do ponto de vista teórico há também um interesse muito grande pelos autômatos finitos não-determinísticos, devido à maior facilidade com que eles permitem a demonstração de certos teoremas. Do ponto de vista prático, os autômatos finitos não-determinísticos são, muitas vezes, mais intuitivos do que os correspondentes autômatos finitos determinísticos, o que os torna, geralmente, mais adequados para a análise e especificação de linguagens regulares. Considere o autômato finito não-determinístico apresentado a seguir:

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

Qual dos autômatos finitos determinísticos apresentados a seguir é equivalente ao autômato finito não-determinístico M₄.

a.

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

b.

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

c.

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

d.

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

e.

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

(Rosa, 2010) Movimentos vazios são transições em autômatos finitos não determinísticos (AFN) que permitem a mudança de estado sem consumir símbolo da cadeia terminal. Uma das vantagens dos movimentos vazios nos estudos das linguagens formais é o fato de facilitar algumas construções relacionadas com os autômatos. Vale lembrar que, assim como os autômatos não determinísticos, a existência de movimentos vazios não aumenta o poder computacional no reconhecimento de linguagens.

Desenvolva um autômato finito com movimentos vazios sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui [abc como prefixo e bba ou cab como subpalavra] ou [cba como prefixo e acc ou bab como subpalavra] e bac ou bcc como sufixo}.

(Ramos, 2009) Como alternativa para a representação dos conjuntos regulares, visando obter maior concisão e facilidade de manipulação, Kleene desenvolveu, na década de 1950, a notação das expressões regulares. Da mesma forma como ocorre para os conjuntos regulares, as expressões regulares sobre um alfabeto Σ podem também ser definidas recursivamente como segue:

• Ø é uma expressão regular e denota o conjunto regular Ø;
• ε é uma expressão regular e denota o conjunto regular {ε};
• Cada σ, σ ∈ Σ, é uma expressão regular e denota o conjunto regular {σ}, σ ∈ Σ.

Se x e y são expressões regulares sobre Σ que denotam, respectivamente, os conjunto regulares X e Y, então:

• (x)
• x | y ou x + y
• x·y ou xy
• x*

Também são expressões regulares e denotam, respectivamente, os conjunto regulares X, X ∪ Y, XY e X*.

Construa uma expressão regular sobre o alfabeto Σ = {a, b}, tal que a respectiva linguagem gerada contenha todas aquelas cadeias w ∈ Σ* que apresentem a seguinte característica:

• Se w contém a subcadeia aa, então w não contém a subcadeia bb.

ER = ((a + ε)(ba + a)*) + ((b + ε)(ab + b)*)

(Menezes, 2000) O Algoritmo de Thompson é um algoritmo utilizado para transformar uma expressão regular em um autômato finito com movimentos vazios, ou seja, pode ser considerado como um compilador de expressão regular para autômato finito com movimentos vazios. Do ponto de vista mais teórico, o Algoritmo de Thompson é uma parte da prova de que ambos aceitam exatamente as mesmas palavras, ou seja, as linguagens regulares. Qual das expressões regulares apresentas a seguir gera o autômato finito com movimentos vazios M₇.

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

a. ER = (ab* + ac*)*b

b. ER = a(b* + ac*)*b

c. ER = a(b* + ac)*b

d. ER = a(b* + c*)*b

e. ER = ((ab)* + (ac)*)*b

(Rosa, 2010) Um autômato mínimo de uma linguagem regular L é um autômato finito determinístico (AFD) M = (Q, Σ, δ, q₀, F) tal que L = T(M) e que, para qualquer outro AFD M’ = (Q’, Σ’, δ’, q₀’, F’) tal que L = T(M’), tem-se que #Q’ ≥ #Q. Para um dado conjunto A, #A denota o cardinal (número de elementos) de A. Dado um AFD M, deve-se denotar por T(M) o conjunto de cadeias aceitas por M, o conjunto de w ∈ Σ* que envia M de q₀ para algum estado em F. Considere o autômato finito determinístico apresentado a seguir:

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

Qual dos autômatos finitos determinísticos apresentados a seguir é o autômato mínimo do autômato finito determinístico M₈.

a.

M_8a = ({a, b}, {q₀, q₁, q₂, q₃}, δ, q₀, {q₃})

b.

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

c.

M_8c = ({a, b}, {q₀, q₁}, δ, q₀, {q₁})

d.

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

e.

M_8e = ({a, b}, {q₀, q₁, q₂, q₃, q₄}, δ, q₀, {q₂, q₄})