Turmas - 2º Semestre de 2017
Turmas
2º Semestre de 2017

(Ramos, 2009) Analise as afirmativas referentes aos conceitos básicos de linguagens formais e autômatos:

1. Uma palavra α é um prefixo de outra palavra β se for possível escrever β como sendo αγ, admitindo-se a possibilidade de γ = ε. Nos casos em que γ ≠ ε, diz-se que α é um prefixo próprio da palavra β. Note que a palavra vazia (ε) pode ser considerada um prefixo (α) de qualquer palavra (β).
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 (ε). Note que prefixos (γ) e sufixos (δ) são casos particulares de subpalavras (α).
3. Uma palavra α é um sufixo de outra palavra β se for possível escrever β como sendo αγ, admitindo-se a possibilidade de γ = ε. Nos casos em que γ ≠ ε, diz-se que α é um sufixo próprio da palavra β. Note que a palavra vazia (ε) pode ser considerada um sufixo (α) de qualquer palavra (β).

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.

(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 referentes a apresentação da função de transição de um autômato finito:

1. Para cada estado de Q existe um nó correspondente no diagrama de transições e uma coluna na tabela de transições.
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 aos estados, e as colunas correspondem às entradas. A entrada para a linha correspondente ao estado q e para a coluna correspondente à entrada a é 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. Desenvolva um autômato finito determinístico 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) Autômatos finitos não-determinísticos que apresentam transições em vazio são aqueles que admitem transições de um estado para outro com e, além das transições normais, que utilizam os símbolos do alfabeto de entrada. Transições em vazio podem ser executadas sem que seja necessário consultar o símbolo corrente da fita de entrada, e sua execução nem sequer causa o deslocamento do cursor de leitura. Desenvolva um autômato finito com movimentos vazios sobre o alfabeto Σ = {w, x, y, z} que reconheça a linguagem L = {w | w possui wzyz ou xywx ou ywwz como prefixo, xwzx ou yzwy ou zwyx como subpalavra e xwyz ou yxyz ou yzyz como sufixo}.

(Hopcroft, 2002) Analise as afirmativas referentes ao funcionamento dos operandos de uma expressão regular:

1. A expressão regular 01* + 10* denota a linguagem que consiste em todos os strings que são a sequência 01 repetidas vezes ou a sequência 10 repetidas vezes, como em 0101 ou 101010.
2. A expressão regular 01* + 10* denota a linguagem que consiste em todos os strings que são um único 0 seguido por qualquer número de 1’s ou um único 1 seguido por qualquer número de 0’s, como em 0111 ou 100.
3. A expressão regular 01* + 10* denota a linguagem que consiste em todos os strings que são um único 0 seguido por qualquer número de 1’s mais um único 1 seguido por qualquer número de 0’s, como em 011100.

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.

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. Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b}, tal que a respectiva linguagem gerada contenha todas aquelas cadeias w ∈ Σ*, tal que se w contém o prefixo aa então w não contém o sufixo bb.

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

(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. Analise o autômato finitos com movimentos vazios apresentado a seguir.

M₇ = ({x, y, z}, {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 analise permite concluir, que após a execução do método da construção de subconjuntos, o autômato finito determinístico resultante terá quantos estados?

a. 4 estados.

b. 5 estados.

c. 6 estados.

d. 7 estados.

e. 8 estados.

(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. Analise as afirmativas sobre os estados redundantes do autômato finito determinístico apresentado a seguir.

M₈ = ({0, 1}, {A, B, C, D, E, F, G, H}, δ, A, {C})

1. Os estados B e H são equivalentes.
2. Os estados D e F são equivalentes.
3. Os estados C e G são equivalentes.
4. Os estados A e E são equivalentes.
5. Os estados A e G são equivalentes.

A analise permite concluir que:

a. 1 afirmativa é verdadeira.

b. 2 afirmativas são verdadeiras.

c. 3 afirmativas são verdadeiras.

d. 4 afirmativas são verdadeiras.

e. 5 afirmativas são verdadeiras.