Turmas - 2º Semestre de 2021
Turmas
2º Semestre de 2021

(vale 1,0 ponto) 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. AB, ABBA, ABABAB

b. AB, ABAA, ABABAB

c. AB, ABAB, ABBAAB

d. AB, ABAB, ABABAB

e. AB, ABAB, ABAABA

(vale 1,0 ponto) 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 barramento possui 54 subpalavras.
2. A palavra multiplicação possui 15 prefixos. {ε, m, mu, mul, mult, multi, multip, multipl, multipli, multiplic, multiplica, multiplicaç, multiplicaçã, multiplicação} (14 prefixos)
3. A palavra compilador possui 11 sufixos.
4. A palavra motherboard possui 66 subpalavras. {ε, a, b, d, e, h, m, o, r, t, ar, bo, er, he, mo, oa, ot, rb, rd, th, ard, boa, erb, her, mot, oar, oth, rbo, the, boar, erbo, herb, moth, oard, othe, rboa, ther, board, erboa, herbo, mothe, other, rboar, therb, erboar, herboa, mother, otherb, rboard, therbo, erboard, herboar, motherb, otherbo, therboa, herboard, motherbo, otherboa, therboar, motherboa, otherboar, therboard, motherboar, otherboard, motherboard} (65 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.

(vale 1,0 ponto) 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. ES_Cachoeiro, AL_Maceio, CE_Fortaleza, SC_Criciuma, RJ_Niteroi

b. ES_Vitoria, GO_Goiania, CE_Fortaleza, MG_Nova_Era, RJ_Niteroi

c. GG_Google, FB_Facebook, BO__Borland, MS_Microsoft, OR_Oracle

d. BA_Mangue_Seco, RS_Cachoeiro, AM_Manaus, RS_Porto_Alegre, SC_Chapeco

e. RJ_Guanabara, IL_Intel, PE-Recife, AD_Adobe, RJ_Niteroi

(vale 1,0 ponto) 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₁})

Avalie as seguintes assertivas:

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

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.

(vale 1,0 ponto) 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 = ({x, y, z}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆}, δ, q₀, {q₆})

P = {C₀, C₁, C₂, C₃, C₄}, com C₀ = {q₆}, C₁ = {q₀}, C₂ = {q₁}, C₃ = {q₄} e C₄ = {q₂, q₃, 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.

(vale 1,0 ponto) 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₁₇})

(vale 1,0 ponto) 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 Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui aca ou bba ou dad como prefixo, adbcb ou cadbd ou dbcad como subpalavra e bddb ou cbca ou ddbc 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₂₀, q₂₁, q₂₂, q₂₃, q₂₄, q₂₅, q₂₆, q₂₇, q₂₈, q₂₉, q₃₀}, δ, q₀, {q₃₀})

(vale 1,0 ponto) 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₇})