Turmas - 2º Semestre de 2016
Turmas
2º Semestre de 2016

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 compatibilidade são {ε, c, co, com, comp, compa, compat, compati, compatib, compatibi, compatibil, compatibili, compatibilid, compatibilida, compatibilidad, compatibilidade}.
2. As subpalavras da palavra sintática são {ε, a, c, i, n, s, t, ca, ic, in, nt, si, ti, tá, át, ica, int, ntá, sin, tic, tát, áti, intá, ntát, sint, tica, táti, átic, intát, ntáti, sintá, tátic, ática, intáti, ntátic, sintát, tática, intátic, ntática, sintáti, intática, sintátic, sintática}.
3. Os sufixos da palavra conformidade são {ε, e, de, ade, dade, idade, midade, rmidade, ormidade, formidade, nformidade, onformidade, conformidade}.

A análise permite concluir que:

a. apenas a afirmativa I está correta.

b. apenas a afirmativa II está correta.

c. apenas a afirmativa III está correta.

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

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

Qual das seguintes expressões regulares, sobre o alfabeto Σ = {w, x, y, z}, reconhece a linguagem L = {w | w possui yyz como prefixo, yzww como subpalavra e wyw como sufixo}.

a. (yyz (ε + (w + x + y + z)*) yzww (ε + (w + x + y + z)*) wyw)

b. (yyz (ε + (w + x + y + z)*) yzw (ε + (w(w + x + y + z)*)) wyw)

c. (yyz (ε + ((w + x + y + z)*yz) w (ε + (w(w + x + y + z)*)) wyw)

d. (yyz (ε + ((w + x + y + z)*yz) yzww (ε + (w(w + x + y + z)*)) wyw)

e. (yyz (ε + ((w + x + y + z)*yz) (ε + (ww(w + x + y + z)*)) wyw)

Movimentos vazios constituem uma generalização dos modelos de máquinas não-determinísticas. Um movimento vazio é uma transição sem leitura de símbolo algum da fita. Pode ser interpretado como um não-determinismo interno do autômato o qual é encapsulado, ou seja, excetuando-se por uma eventual mudança de estados, nada mais pode ser observado sobre um movimento vazio. Qual linguagem o autômato finito com movimentos vazios, apresentado a seguir, reconhece?

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

a. L = {aⁱbⁱcⁱ | i ≥ 0}

b. L = {aⁱbⁱcⁱ | i > 0}

c. L = {aⁱb^jc^k | i ≥ 0, j ≥ 0 e k ≥ 0}

d. L = {aⁱb^jc^k | i > 0, j > 0 e k > 0}

e. L = {aⁱb^jc^k | i > 1, j > 1 e k > 1}

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

Expressões regulares são bastante utilizadas em áreas que abrangem desde a especificação de linguagens de programação e de comandos, até a entrada de dados em editores de texto, programas de busca e análise de padrões. Infelizmente, expressões regulares são pouco eficientes para serem executados diretamente num computador, sendo na grande maioria dos casos, convertidos em autômatos finitos determinísticos, muito mais eficientes na execução em um computador. A conversão de expressões regulares para autômatos finitos determinísticos envolve três passos.

a) Converta a expressão regular (a + ε)(b + ba)* para um autômato finito não-determinístico com movimentos vazios, utilizando o algoritmo de Thompson.

b) Converta, usando o método da construção de subconjuntos, o autômato finito não-determinístico com movimentos vazios do item a para um autômato finito determinístico.

c) Minimize, se possível, o número de estados do autômato do item b.

Na Teoria da Computação, um autômato finito não-determinístico é 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, 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 expressão regular é equivalente ao autômato finito não-determinístico apresentado a seguir?

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

a. ER = ab⁺c^*b⁺a

b. ER = ab^*c^*b^*a

c. ER = a(bcb)^*a

d. ER = a⁺b⁺c^*b⁺a⁺

e. ER = a(bc^*b)⁺a