Turmas - 2º Semestre de 2024
Turmas
2º Semestre de 2024

(Poscomp, 2023) Dada a linguagem L = {w ∈ {a, b}* | o antepenúltimo símbolo de w é a}, analise as seguintes afirmativas.

1. O Autômato Finito Determinístico (AFD) que reconhece L tem, no mínimo, 8 (oito) estados.
2. O menor Autômato Finito Determinístico (AFD) que reconhece L tem 2 (dois) estados finais.
3. O menor Autômato Finito Não Determinístico (AFN) que reconhece L tem 4 (quatro) estados.
4. A Expressão Regular (ER) (a+b)^*a(a+b)⁺ denota L.

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.

Comentários:

A Expressão Regular não garante que o antepenúltimo símbolo de w seja a, uma vez que a expressão (a+b)⁺ pode produzir uma sequência aleatória de símbolos a's e b's de tamanho 1 a n.

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

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

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 motherboard possui 12 prefixos.
2. A palavra compilador possui 55 subpalavras.
3. A palavra barramento possui 55 subpalavras.
4. A palavra multiplicação possui 15 sufixos.

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.

Comentários:

A palavra barramento possui 54 subpalavras, sendo {ε, a, b, e, m, n, o, r, t, am, ar, ba, en, me, nt, ra, rr, to, ame, arr, bar, ent, men, nto, ram, rra, amen, arra, barr, ento, ment, rame, rram, ament, arram, barra, mento, ramen, rrame, amento, arrame, barram, rament, rramen, arramen, barrame, ramento, rrament, arrament, barramen, rramento, arramento, barrament, barramento}.

A palavra multiplicação possui 14 sufixos, sendo {ε, o, ão, ção, ação, cação, icação, licação, plicação, iplicação, tiplicação, ltiplicação, ultiplicação, multiplicação}.

(Poscomp, 2023) Qual é a Expressão Regular (ER) que denota a linguagem a seguir?

L = {w ∈ {a, b}* | w não pode terminar com ba}

a. (a+b)*ba

b. (a+b)*(aa+b)

c. (a+b)*(aa+b+ε)

d. ((a+b)*(aa+b))+a+ε

e. A linguagem L não é regular e, portanto, não pode ser denotada por uma ER.

Comentários:

(a+b)*ba produz palavras com o sufixo ba

(a+b)*(aa+b) não produz todas as palavras possíveis, como por exemplo, {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb, ...}.

(a+b)*(aa+b+ε) permitir palavras com o sufixo ba.

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 (1*0)* representa o autômato da figura.
2. A expressão regular 1*01*(01*01*)* representa o autômato da figura.
3. A expressão regular 1*(01*01*)*01* representa o autômato da figura.
4. A expressão regular (1*01*01*)* 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.

Comentários:

(1*0)* não produz palavras com o sufixo 1, como por exemplo 01.

(1*01*01*)* produz a palavra vazia.

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₅})

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₀, 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.

Comentários:

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

M = ({a, b}, {C₀, C₁, C₂}, δ, C₁, {C₀})

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 Σ = {w, x, y, z} que reconheça a linguagem L = {w | w possui wzy ou yxw como prefixo, xwxy ou yzyw como subpalavra e ywy ou yzz 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₁₇})

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, adabc ou badcb ou dabbd 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₃₀})

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

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