Turmas - 2º Semestre de 2023
Turmas
2º Semestre de 2023

Considerando-se a definição de autômatos finitos, assinale a única alternativa que contém somente cadeias de caracteres totalmente aceitas pelo autômato finito apresentado a seguir.

M = ({A, B}, {q₀, q₁, q₂, q₃}, δ, q₀, {q₂})

a. BA, BAAB, BABABA

b. BA, BABB, BABABA

c. BA, BABA, BABABA

d. BA, BABA, BAABBA

e. BA, BABA, BABBAB

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. A palavra compilador possui 54 subpalavras. {ε, a, c, d, i, l, m, o, p, r, ad, co, do, il, la, mp, om, or, pi, ado, com, dor, ila, lad, mpi, omp, pil, ador, comp, ilad, lado, mpil, ompi, pila, compi, ilado, lador, mpila, ompil, pilad, compil, ilador, mpilad, ompila, pilado, compila, mpilado, ompilad, pilador, compilad, mpilador, ompilado, compilado, ompilador, compilador} (55 subpalavras)
2. A palavra multiplicação possui 14 prefixos.
3. A palavra motherboard possui 11 sufixos. {ε, d, rd, ard, oard, board, rboard, erboard, herboard, therboard, otherboard, motherboard} (12 sufixos)
4. A palavra barramento possui 54 subpalavras.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV 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. Assinale a única alternativa onde está CORRETA a lista formada somente por todas as cadeias de caracteres reconhecidas pela expressão regular [A-Z][a-z]*[_][A-Z][A-Z] (padrão unix). As cadeias estão separadas por vírgula.

a. Vitoria_ES, Goiania_GO, Fortaleza_CE, Nova_Era_MG, Niteroi_RJ

b. Google_GG, Facebook_FB, Borland__BO, Microsoft_MS, Oracle_OR

c. Mangue_Seco_BA, Cachoeiro_RS, Manaus_AM, Porto_Alegre_RS, Chapeco_SC

d. Guanabara_RJ, Intel_IL, Recife­-PE, Adobe_AD, Niteroi_RJ

e. Cachoeiro_ES, Maceio_AL, Fortaleza_CE, Criciuma_SC, Niteroi_RJ

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 = ({0, 1}, {q₀, q₁}, δ, q₀, {q₁})

Analise as afirmativas apresentadas a seguir:

1. A expressão regular 0*1*0*1 representa o autômato da figura. Não produz todas as sentenças reconhecidas pelo autômato, como por exemplo, 10101
2. A expressão regular 11*0*1+0*1*1 representa o autômato da figura. Não produz todas as sentenças reconhecidas pelo autômato, como por exemplo, 10101
3. A expressão regular 0*1(00*1+1)* representa o autômato da figura.
4. A expressão regular (1+0)*1 representa o autômato da figura.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

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 seguintes afirmativas sobre a aplicação do processo de minimização de estados ao autômato finito determinístico apresentado a seguir.

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

P = {C₀, C₁, C₂}, com C₀ = {q₃}, C₁ = {q₁, q₂, q₄} e C₂ = {q₀}

1. Os estados q₁ e q₂ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
2. Os estados q₃ e q₄ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
3. Os estados q₁ e q₄ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
4. Os estados q₀ e q₃ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

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 sobre o alfabeto Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui adc ou cba como prefixo, abcd ou dcac como subpalavra e caa ou cdc como sufixo}.

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

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 sobre o alfabeto Σ = {w, x, y, z} que reconheça a linguagem L = {w | w possui wyw ou xxw ou zwz como prefixo, wzxyx ou ywzxz ou zxywz como subpalavra e xzzx ou yxyw ou zzxy como sufixo}.

M = ({w, 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₂₃, q₂₄, q₂₅, q₂₆, q₂₇, q₂₈, q₂₉, q₃₀}, δ, q₀, {q₃₀})

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. É obrigatório a apresentação das tabelas utilizadas na determinação dos estados do 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₂₁, q₂₂, q₂₃, q₂₄, q₂₅, q₂₆}, δ, q₀, {q₂₆})

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