Ybadoo - Soluções em Software Livre
Turmas
2º Semestre de 2014

Apresente as possíveis subpalavras da palavra ferramenta.
Desenvolva um autômato finito determinístico sobre o alfabeto Σ = {a, b, c, d} que reconheça a linguagem L = {w | w possui bca ou dac como prefixo, bab ou dbc como subpalavra e cac ou cba como sufixo}.

Questão 03

Algebricamente, um Autômato Finito M pode ser definido como uma quíntupla:

M = (Q, Σ, δ, q0, F)

  • Q é um conjunto finito de estados;
  • Σ é um alfabeto (finito e não-vazio) de entrada;
  • δ é uma função de transição, δ : Q x ΣQ;
  • q0 é o estado inicial, q0Q;
  • F é um conjunto de estados finais, FQ.

No caso de q0F, pode-se concluir que esse Autômato Finito:

  1. não aceita a cadeia vazia
  2. não tem outros estados finais
  3. é determinístico
  4. aceita a cadeia vazia
  5. é não determinístico
Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1234 ou 1212 ou 3434 como prefixo, 3412 ou 4421 ou 1243 ou 2234 como subpalavra e 2212 ou 1123 ou 2431 ou 3444 como sufixo}.

Questão 05

Na Teoria da Computação, um Autômato Finito Não-Determinístico (AFN) é uma máquina de estados finita, onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Essa característica o distingue do Autômato Finito Determinístico (AFD), onde 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 a Linguagem Regular reconhecida pelo Autômato Finito Não-Determinístico apresentado a seguir:

M = ({a, b}, {q0, q1, q2}, δ, q0, {q2})

Grafo do Autômato Finito Não-Determinístico (AFN)
Grafo do Autômato Finito Não-Determinístico (AFN)
  1. L = {w | w possui palavras no formato anbm, com n > 0 e m > 0}
  2. L = {w | w possui palavras no formato anbm, com n ≥ 0 e m ≥ 0}
  3. L = {w | w possui palavras no formato anbn, com n > 0}
  4. L = {w | w possui palavras no formato anbn, com n ≥ 0}
  5. L = {w | w possui palavras no formato anbm, com n > 0 e m ≥ 0}
Desenvolva um Autômato Finito com Movimentos Vazios (AFε) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui accb ou cbab ou dacd como prefixo, bcad ou dcbd ou abca como subpalavra e adab ou abab ou dcab como sufixo}.
Desenvolva uma expressão regular sobre o alfabeto Σ = {a, b, c, d} que produza a linguagem L = {w | w possui ba ou bab ou dac como prefixo, abb ou acbc ou cac como subpalavra e acd ou bca ou cda como sufixo}.

Questão Extra

As Expressões Regulares (ER) sobre um alfabeto Σ podem ser definidas recursivamente, como segue:

  1. Ø é uma expressão regular e denota a linguagem vazia.
  2. ε é uma expressão regular e denota a linguagem contendo exclusivamente a palavra vazia, ou seja, {ε}.
  3. Qualquer símbolo x pertencente a Σ é uma expressão regular e denota a linguagem contendo a palavra unitária x, ou seja, {x}.
  4. Se r e s são expressões regulares e denotam as linguagens R e S, respectivamente, então:
    1. (r+s) é uma expressão regular e denota a linguagem R ∪ S.
    2. (rs) é uma expressão regular e denota a linguagem RS = {uv | u ∈ R e v ∈ S}.
    3. (r*) é uma expressão regular e denota a linguagem R*.

Assinale a alternativa que apresenta, corretamente, uma Expressão Regular (ER) que denota todas as strings de a's e b's que tenham pelo menos dois b's consecutivos:

  1. (a*+bb)(a+ba)*(a+b)*
  2. (a+ba)*bb(ba+a)*
  3. (a+b)*ba*b(a+b)*
  4. (a+bb)*(bb+a)*
  5. (a+ba)*bb(a+b)*