Turmas - 2º Semestre de 2019
Turmas
2º Semestre de 2019

(Ramos, 2009) 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 autossustentável pode possuir no máximo 17 prefixos.
2. A palavra programação pode possuir no máximo 60 subpalavras.
3. A palavra gramática pode possuir no máximo 45 subpalavras.
4. A palavra determinístico pode possuir no máximo 14 sufixos.

A análise permite concluir que:

a. apenas as assertivas I e II estão corretas.

b. apenas as assertivas I e III estão corretas.

c. apenas as assertivas II e III estão corretas.

d. apenas as assertivas II e IV estão corretas.

e. apenas as assertivas III e IV estão corretas.

(Ramos, 2009) Expressões regulares são bastante utilizadas em áreas que abrangem desde a especificação de linguagens de programação e de comandos, até a entrada de dados em editores de texto, programas de busca e análise de padrões. Qual das seguintes expressões regulares, sobre o alfabeto Σ = {1, 2, 3} reconhece a linguagem L = {w | w possui 312 como prefixo, 211 como subpalavra e 121 como sufixo}.

a. ER = (312 (ε + (1 + 2 + 3)* ) 21 (ε + (1 (1 + 2 + 3)*)) 121)

b. ER = (312 (ε + ((1 + 2 + 3)* 21)) (ε + (1 (1 + 2 + 3)*)) 121)

c. ER = (312 (ε + ((1 + 2 + 3)* 2)) (ε + (11 (1 + 2 + 3)*)) 121)

d. ER = (312 (ε + ((1 + 2 + 3)* 2)) (ε + (1 (1 + 2 + 3)*)) 121)

e. ER = (312 (ε + ((1 + 2 + 3)* 2)) 1 (ε + (1 (1 + 2 + 3)*)) 121)

(POSCOMP, 2018) O Autômato Finito com Movimentos Vazios (AFε) apresentado a seguir foi construído utilizando o algoritmo de Thompson, tomando-se como base uma determinada Expressão Regular (ER). Esse AFε deve ser transformado para um Autômato Finito Determinístico (AFD), utilizando o algoritmo de subconjuntos. Em relação à ER e à conversão AFε para AFD, considere as assertivas abaixo, assinalando V, se verdadeiras, ou F, se falsas.

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

(     ) A ER de origem é a(a + b)*b.

(     ) A ER de origem é a*(a + b)b*.

(     ) O AFD resultante tem 5 estados.

(     ) O AFD resultante tem 4 estados.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. V – F – V – F

b. V – F – F – V

c. F – V – V – F

d. F – V – F – V

e. F – V – F – F

(Ricarte, 2008) 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. Quantos estados o Autômato Finito Determinístico apresentado a seguir terá após a aplicação do processo de minimização de estados do autômato?

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

a. 1

b. 2

c. 3

d. 4

e. 5

(Menezes, 2000) 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} que reconheça a linguagem L = {w | w possui bbc ou cca como prefixo, cab ou cba como subpalavra e baa ou bcb como sufixo}.

(Ramos, 2009) 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 Σ = {1, 2, 3, 4} que reconheça a linguagem L = {w | w possui 234 ou 341 ou 411 como prefixo, 132 ou 412 ou 423 como subpalavra e 121 ou 213 ou 342 como sufixo}.

(Ramos, 2009) 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 e, 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 Σ = {w, x, y, z} que reconheça a linguagem L = {w | w possui wyzy ou xzxy ou zyyw como prefixo, wxxy ou xyx ou ywzy como subpalavra e xwzw ou yxx ou zw 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. Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b}, tal que a respectiva linguagem gerada contenha todas aquelas cadeias w ∈ Σ*, tal que w não possua dois b’s consecutivos.

ER = (b + ε)(a + ab)*