Fundamentos da Teoria da Computação

Fundamentos da Teoria da Computação

1. Conceitos

   • Alfabeto
     • um conjunto finito de unidades fundamentais a partir do qual construímos estruturas.
       • {a, b, c}
   • Linguagem
     • um certo conjunto de cadeias de caracteres construídas a partir do alfabeto.
       • {aba, abc, cab, bac}
   • Palavras
     • são as cadeias que são permitidas na linguagem.
       • aba
   • Cadeia vazia ou nula
     • cadeia sem nenhuma letra. Notação: ʌ (palavra nula)
   • Linguagem sem nenhuma palavra
     • ϕ (conjunto vazio)
       • {}
   • Estados
     • Estado Inicial
       • estado em que o problema se encontra quando começa a ser resolvido.
     • Estado Final
       • estado em que o problema encontra-se quando foi resolvido ou chegou-se a um estado em que não há saída.

2. Automatos

   • Um autômato finito (determinísticos e não determinísticos) é uma quíntupla M=(Q, Σ, δ, q o, F),
     • Q
       • conjunto finito de estados;
     • Σ
       • um alfabeto
     • qo
       • estado inicia
     • F
       • conjunto de estados finais
     • δ
       • função de transição de estados
   • AFND - Automato Finito Não Deterministico
     • Pode estar em vários estados ao mesmo tempo
     • A partir de 1 única letra pode ir para um ou vários estados ao mesmo tempo
     • Pode estar em um estado e passar para outro sem necessariamente ler uma letra
   • AFD - Automato Finito Deterministico
     • Está em um único estado de cada vez
     • A partir de 1 letra pode ir somente para um estado
     • Necessita de uma letra para avançar para outro estado
   • AFND X AFD
     • Todo AFND pode ser convertido em um AFD capaz de reconhecer a mesma linguagem em ambos
     • Para se chegar ao resultado basta seguir uma série de passos
       • A partir do AFND, crie para cada conjunto de estados um novo estado onde o rótulo é o próprio conjunto
       • Complete as transições de cada novo estado acompanhando o comportamento de cada estado individualmente e tomando a união dos estados acessados
       • Adicione como estados finais aqueles estados que tem como rótulo um estado final
       • Elimine os estados nunca acessados a partir do estado inicial
       • Complete a quíntupla do AFD seguindo
         • Q do AFD são os estados resultantes dos passos até este ponto
         • O alfabeto não é alterado
         • A contrução do δ já foi mencionada
         • O estado inicial não se altera
         • Os estados finais são a união de todos os estados finais do δ resultante

Images and files in the map