TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Automatos Finitos

Por:   •  1/7/2015  •  Artigo  •  877 Palavras (4 Páginas)  •  2.260 Visualizações

Página 1 de 4

Autômatos Finitos DETERMINÍSTICOS

  1. Construa um AFD para as seguintes linguagens:

  1. {w ∈{0,1}* | w tem tamanho 3}
  2. {w ∈{0,1}* | w tem tamanho menor que 3}
  3. {w ∈{0,1}* | w tem tamanho maior que 3}
  4. {w ∈{0,1}* | w tem tamanho múltiplo de 3}
  5. {w ∈{0,1}* | cada 0 de w é imediatamente seguido de, no mínimo dois 1´s}
  6. {w ∈{0,1}* | os primeiros 4 símbolos de w contêm, no mínimo, dois 1´s}
  7. {w ∈{0,1}* | w NÃO contém 000 nem 111}
  8. {w ∈{0,1}* | os últimos três símbolos de w NÃO são 000}
  9. {w ∈{0,1,2}* |  w tem número par de 0´s, par de 1´s e par de 2´s}
  10. { uavbxcy | u,v,x,y ∈{a,b,c}*}
  11. {w ∈{a,b}* | w começa com a e tem tamanho par}
  12. {w ∈{a,b}* | w nunca tem mais de dois a´s consecutivos}
  13. {w ∈{a,b}* | w tem um número ímpar de ab´s}
  14. {w ∈{a,b}* | |w| ≥ 2 e os a´s (se houver) precedem os b´s (se houver)}
  15. {w ∈{a,b,c,d}* | os a´s (se houver) precedem os b´s (se houver) e os c´s (se houver) precedem os d´s (se houver)}
  16. { xban | x ∈{a,b}*, n ≥ 0 e x tem um número par de a´s}
  17. { xamban | x ∈{a,b}*, m+n é par e x não termina em a}
  1. Seja o primeiro símbolo de uma palavra a posição 1, o segundo símbolo é a posição 2, e assim por diante. Seja i um número natural qualquer: a posição i indica uma posição qualquer na palavra, as posições 2i (ou 2i+2, ou 2i+4, etc.) indicam as posições pares dentro da palavra, as posições 2i-1 (ou 2i+1, 2i+3, etc.) indicam as posições ímpares. Construa AFD´s para as seguintes linguagens sobre o alfabeto {0,1}:
  1. O conjunto de palavras em que o símbolo na posição 2i é diferente do símbolo na posição 2i+2, para i ≥ 1.
  2. O conjunto de palavras em que o símbolo na posição 2i-1 é diferente do símbolo na posição 2i, para i ≥ 1.
  3. O conjunto de palavras em que o símbolo na posição i é diferente do símbolo na posição i+2, para i ≥ 1.
  4. O conjunto de palavras com número par de 0´s nas posições pares e número ímpar de 0´s nas posições ímpares.
  5. O conjunto de palavras de tamanho par com 1´s nas posições pares, acrescido das palavras de tamanho ímpar com 1´s nas posições ímpares.
  1. Faça um AFD para {0}{0,1}* ∪ {0,1}*{1}. Minimize o AFD.
  1. Minimize todos os AFD´s do exercício 2.
  1. Monte um AFD para a união e outro AFD para a interseção das linguagens dos exercícios 1.d) e 1.e)
  1. Construa AFDs para as linguagens:
  1. L1 = {w ∈{0,1}* | o tamanho de w é divisível por 3}
  2. L2 = {0w0 | w ∈{0,1}* }
  3. L1 ∩ L2

Autômatos Finitos NÃO-DETERMINÍSTICOS

  1. Construa AFN´s para as seguintes linguagens sobre {a,b,c}:
  1. O conjunto de palavras com, no mínimo, 3 ocorrências de abc.
  2. O conjunto de palavras com, no mínimo, 3 ocorrências de a´s ou 3 ocorrências de b´s ou 3 ocorrências de c´s.
  3. O conjunto de palavras com sufixo abc e bca.
  4. O conjunto de palavras em que existem duas ocorrências de abc com um número ímpar de símbolos entre elas.
  5. {w ∈{0,1}* | |w| ≥ 4  e o segundo e o penúltimo símbolos são ambos 1}
  6. {w ∈{0,1}* | 00 não aparece nos últimos 4 símbolos de w}
  7. {w ∈{0,1}* | entre dois 1´s de w há sempre um número par de 0´s, exceto nos últimos 4 símbolos}
  8. {w ∈{0,1}* | w tem uma subpalavra constituída de dois 1´s separados por um número par de símbolos}

  1. Sejam as linguagens da forma Ln = {xyx | x,y ∈ {a,b}* e |x| = n}. Determine o menos número de estados para um AFN e para um AFD que reconheçam Ln, nos seguintes casos:
  1. n = 1
  2. n = 2
  3. n é arbitrário
  1. Mostre que para todo AFN existe um AFN equivalente com um único estado inicial (mostre como construir um AFN só com um estado inicial a partir de um AFN qualquer).
  1. Mostre que sim ou não: para todo AFN existe um AFN equivalente com um único estado final
  1. Seja o AFNλ M = ({0,1,2},{a,b,c},δ,0,{2}), sendo δ dado por:

δ

A

b

C

λ

0

{0}

{1}

1

{1}

{2}

2

{2}

  1. Determine fλ(e) para e = 0,1,2.
  2. Determine um AFN M´ equivalente a M, retirando as transições λ.
  3. Determine um AFD M´´ equivalente a M´, retirando o não-determinismo.
  1. Construa AFNE´s para as linguagens do exercício 1, com um mínimo de transições possível.
  1. Mostre que para todo AFNλ existe um outro AFNλ equivalente com um único estado inicial e um único estado final.

...

Baixar como (para membros premium)  txt (4.5 Kb)   pdf (171.7 Kb)   docx (12.7 Kb)  
Continuar por mais 3 páginas »
Disponível apenas no TrabalhosGratuitos.com