Turmas - 2º Semestre de 2026
Turmas
2º Semestre de 2026

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 computador e compilador possuem a mesma quantidade de subpalavras.
2. As palavras analisabilidade e associatividade possuem a mesma quantidade de prefixos.
3. As palavras infraestrutura e extraterrestre possuem a mesma quantidade de subpalavras.
4. As palavras compatibilidade e inteligibilidade 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.

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 = ({a, b, c}, {A, B, C, D, E, F}, δ, A, {D, E, F})

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

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.

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 Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui bcb ou bcd ou dab como prefixo, bcca ou cbdb ou cdbc como subpalavra e bcba ou cadc ou dbba como sufixo}.

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 ε, 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 Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui baca ou caab ou dcda como prefixo, abca ou bdda ou dad como subpalavra e add ou cab ou dbcb como sufixo}.

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. Analise a expressão regular sobre o alfabeto {a, b} abaixo:

(a+b)*a(a+b)*+(a+b)*b(a+b)*

A expressão pode ser simplificada como:

a. (a+b)*

b. a*b*

c. ab+ba

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

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

Na Teoria da Computação, um autômato finito não-determinístico é uma máquina de estados finita, em que, para cada par de estado e símbolo de entrada podem haver vários próximos estados possíveis. Essa característica o distingue do autômato finito determinístico, em que o próximo estado possível é univocamente determinado. Autômatos finitos não-determinísticos reconhecem exatamente o conjunto de linguagens regulares que são, dentre outras coisas, úteis para a realização da análise léxica e reconhecimento de padrões. Qual expressão regular é equivalente ao autômato finito não-determinístico apresentado a seguir?

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

a. a*b*a

b. a⁺bb⁺a

c. a⁺bb*a

d. a⁺b⁺a

e. a*(bb)*a

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 Σ = {1, 2, 3, 4} que reconheça a linguagem L = {w | w possui 212 ou 414 como prefixo, 243 ou 423 como subpalavra e 342 ou 431 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}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁, q₁₂, q₁₃, q₁₄, q₁₅, q₁₆, q₁₇}, δ, q₀, {q₁₇})