Turmas - 2º Semestre de 2025
Turmas
2º Semestre de 2025

(Enade, 2005) Que cadeia é reconhecida pelo autômato representado pelo diagrama de estados a seguir?

M = ({0, 1}, {q₀, q₁, q₂, q₃}, δ, q₀, {q₁})

a. 101010

b. 111011000

c. 11111000

d. 10100

e. 00110011

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 γαδ, 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. As palavras araraúna e hardware possuem a mesma quantidade de subpalavras.
2. As palavras delimitador e informática possuem a mesma quantidade de prefixos.
3. As palavras cabeludo e limpador possuem a mesma quantidade de subpalavras.
4. As palavras arara e caneca possuem a mesma quantidade de 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.

(Enade, 2005) O autômato a seguir reconhece sequências de caracteres compostos pelas letras I, V e X, que representam, em notação romana, números correspondentes ao intervalo de 1 a 10, na notação arábica.

M = ({I, V, X}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇}, δ, q₀, {q₁, q₂, q₃, q₄, q₅, q₆, q₇})

Observe a correspondência da representação dos alfabetos romano e arábico fornecida pela tabela abaixo.

Considerando essas informações, estenda o autômato apresentado acima para reconhecer números no alfabeto romano, correspondentes aos números de 1 a 50 no alfabeto arábico.

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-determinísticos, 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-determinísticos 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 Σ = {1, 2, 3, 4} que reconheça a linguagem L = {w | w possui 2323 ou 2413 ou 3324 como prefixo, 23443 ou 24432 ou 32121 como subpalavra e 214 ou 323 ou 433 como sufixo}.

Qual é a Expressão Regular que denota a linguagem L = {w ∈ {a, b, c}* | |w| deve ser ímpar}?

Exemplos de palavras válidas: a, b, c, aaa, abc, aba, abb, abcba, ...

Exemplos de palavras inválidas: ε, aa, ab, bb, abcb, bcbc, abcabc, ...

a. (a + b + c)*

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

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

d. (a + b + c) ((a + b + c)(a + b + c))*

e. (a + b + c)* ((a + b + c) (a + b + c))*

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₆, 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 Σ = {w, x, y, z} que reconheça a linguagem L = {w | w possui xzx ou yzy como prefixo, xyw ou yxw como subpalavra e wyx ou ywz como sufixo}.

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