Turmas - 2º Semestre de 2015
Turmas
2º Semestre de 2015

Uma palavra α é um prefixo de outra palavra β se for possível escrever β como sendo αγ, admitindo-se a possibilidade de γ = ε. 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 (ε). Uma palavra α é um sufixo de outra palavra β se for possível escrever β como sendo γα, admitindo-se a possibilidade de γ = ε. Analise as seguintes afirmativas sobre prefixos, subpalavras e sufixos.

1. Os prefixos da palavra contexto são {c, co, con, cont, conte, contex, context, contexto}.
2. As subpalavras da palavra computador são {ε, a, c, d, m, o, p, r, t, u, ad, co, do, mp, om, or, pu, ta, ut, ado, com, dor, mpu, omp, put, tad, uta, ador, comp, mput, ompu, puta, tado, utad, compu, mputa, omput, putad, tador, utado, comput, mputad, omputa, putado, utador, computa, mputado, omputad, putador, computad, mputador, omputado, computado, omputador, computador}.
3. Os sufixos da palavra abcd são {ε, d, dc, dcb, dcba}.

A análise permite concluir que:

1. apenas a afirmativa I está correta.
2. apenas a afirmativa II está correta.
3. apenas a afirmativa III está correta.
4. apenas as afirmativas I e II estão corretas.
5. apenas as afirmativas I e III estão corretas.

Toda Linguagem Regular pode ser descrita por uma expressão simples, denominada Expressão Regular. Trata-se de um formalismo denotacional, também considerado gerador, pois pode-se inferir como construir ("gerar") as palavras de uma linguagem. Analise as seguintes igualdades de expressões regulares:

1. (a* + b*)* = (b + a)*
2. (a + b)* = (b + a)*
3. a* + b* = (b + a)*

A análise permite concluir que:

1. apenas a afirmativa I está correta.
2. apenas a afirmativa II está correta.
3. apenas a afirmativa III está correta.
4. apenas as afirmativas I e II estão corretas.
5. apenas as afirmativas I e III estão corretas.

Da mesma forma como ocorre com as expressões regulares, os autômatos finitos também possibilitam a formalização das linguagens regulares. No entanto, diferentemente das expressões regulares, que constituem dispositivos de geração de sentenças, os autômatos finitos são dispositivos de aceitação de sentenças. Considere o autômato finito determinístico a seguir.

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

Assinale a alternativa que apresenta a expressão regular que produz a mesma linguagem reconhecida pelo autômato finito determinístico:

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