Turmas - 1º Semestre de 2018
Turmas
1º Semestre de 2018

(Ramos, 2009) 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 testabilidade são {ε, t, te, tes, test, testa, testab, testabi, testabil, testabili, testabilid, testabilida, testabilidad, testabilidade}.
2. As subpalavras da palavra autômatos são {ε, a, m, o, s, t, u, at, au, ma, os, to, tô, ut, ôm, ato, aut, mat, tos, tôm, utô, ôma, atos, autô, mato, tôma, utôm, ômat, autôm, matos, tômat, utôma, ômato, autôma, tômato, utômat, ômatos, autômat, tômatos, utômato, autômato, utômatos, autômatos}.
3. Os sufixos da palavra confiabilidade são {ε, e, de, ade, dade, idade, lidade, ilidade, bilidade, abilidade, iabilidade, fiabilidade, nfiabilidade, onfiabilidade, confiabilidade}.

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.

(Hopcroft, 2002) Um autômato finito é definido como M = (Σ, Q, δ, q₀, F) onde Σ é um conjunto finito de símbolos de entrada, Q é um conjunto finito de estados, δ é uma função de transição, q₀ é o estado inicial e F é o conjunto de estados finais. Analise as afirmativas apresentadas a seguir, referentes a apresentação da função de transição de um autômato finito.

1. O diagrama de transição de estados são grafos orientados não-ordenados, rotulados nos vértices com os nomes dos estados e nos arcos com os símbolos do alfabeto de entrada do autômato finito. Trata-se de uma representação gráfica equivalente à notação algébrica, oferecendo, porém, uma melhor visualização do autômato.
2. Para cada estado q em Q e para cada símbolo de entrada a em Σ, seja δ(q, a) = p. Então, o diagrama de transições tem um arco do nó q para o nó p, rotulado por a. Se existirem vários símbolos de entrada que causam transições de q para p, então o diagrama de transições pode ter um arco rotulado pela lista desses símbolos.
3. Uma tabela de transições é uma representação convencional e tabular de uma função como δ que recebe dois argumentos e retorna um valor. As linhas da tabela correspondem às entradas, e as colunas correspondem aos estados. A entrada para a linha correspondente à entrada a e para a coluna correspondente ao estado q é o estado δ(q, a).

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 II e III estão corretas.

(Ramos, 2009) 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 daquela notação, 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₃ = ({x, y, z}, {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.

a. x*y + z*

b. xx*y + zz*

c. xx*(y + z)z*

d. x*(y + z)z*

e. (xx)*(y + z)z*

(Hopcroft, 2002) Analise as afirmativas apresentadas a seguir, referentes ao funcionamento dos operadores de uma expressão regular.

1. A expressão regular ab* + ba* denota a linguagem que consiste em todas as strings que são um único a seguido por qualquer número de b’s ou um único b seguido por qualquer número de a’s, como em abbb ou baa.
2. A expressão regular ab* + ba* denota a linguagem que consiste em todas as strings que são a sequência ab repetidas vezes ou a sequência ba repetidas vezes, como em abab ou bababa.
3. A expressão regular (ab*) + (ba*) denota a linguagem que consiste em todas as strings que são a sequência ab repetidas vezes ou a sequência ba repetidas vezes, como em ababab ou baba.

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 II e III estão corretas.

(Menezes, 2000) Um sistema de estados finitos é um modelo matemático de sistemas com entradas e saídas discretas. Pode assumir um número finito e pré-definido de estados. Cada estado resume somente as informações do passado necessárias para determinar as ações para a próxima entrada. Desenvolva um Autômato Finito Determinístico (AFD) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iij ou kki como prefixo, ijk ou ikj como subpalavra e kik ou kjj como sufixo}.

(Ricarte, 2008) O método da construção de subconjuntos é um procedimento sistemático que converte um autômato finito com movimentos vazios num autômato finito determinístico. O princípio associado a esse método é criar novos estados, no autômato finito determinístico, que estejam associados a todas as possibilidades de estados originais em um dado momento da análise da sentença no processo de reconhecimento. Para cada estado original, essas possibilidades incluem o estado do autômato finito com movimentos vazios e todos os estados que podem ser atingidos a partir dele com transições pela string vazia. Converta, usando o método da construção de subconjuntos, o autômato finito não-determinístico com movimentos vazios apresentado a seguir para um autômato finito determinístico.

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₁₉})

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

(Ricarte, 2008) Em geral, a aplicação do método da construção de subconjuntos produz autômatos com estados redundantes, ou seja, estados que poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida. Minimize, se possível, o número de estados do autômato finito determinístico resultante da Questão 06.

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

(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-determinismos, 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-determinismos 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. Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1212 ou 1234 ou 3434 como prefixo, 1243 ou 2234 ou 3412 ou 4421 como subpalavra e 1123 ou 2212 ou 2431 ou 3444 como sufixo}.