Mapa Mental - Teoria Computacional

Prévia do material em texto

Linguagens Regulares Palíndromos Definidas por expressões Cadeias que são iguais regulares e reconhecidas por quando lidas da autômatos finitos esquerda para a direita ou vice-versa Gramáticas regulares possuem regras simples com produções Podem ser lineares representados pela forma wwR, onde é a Exemplos incluem cadeias com reversa de W padrões fixos e repetições simples Não possuem São a base para construção de separadores entre as duas metades da cadeia compiladores e analisadores léxicos Exemplos incluem sequências simétricas de símbolos e números Teoria Autômatos Gramáticas e Derivações Máquinas abstratas Computacional Gramáticas definem regras para que reconhecem gerar cadeias em uma linguagem linguagens formais formal Autômatos finitos Derivações mostram passo a passo podem ser como uma cadeia é produzida determinísticos ou Símbolos terminais e não não determinísticos terminais compõem as regras de Estados e transições produção definem Exemplos incluem expressões comportamento do aritméticas e cadeias palíndromas autômato Aplicações incluem Máquina de Turing e Computabilidade análise léxica e Modelo abstrato que captura a noção de reconhecimento de algoritmo e computação geral padrões Capaz de simular qualquer algoritmo Linguagens Livres de Contexto computacionalmente realizável Decidibilidade e Reduções Geradas por gramáticas com regras que Base para estudo de problemas decidíveis e indecidíveis na computação Problemas decidíveis têm podem ter símbolos não terminais Fundamental para a teoria da computação e algoritmos que sempre terminam com Permitem estruturas mais complexas, limites do que pode ser computado resposta correta como expressões matemáticas aninhadas Problemas indecidíveis não possuem São reconhecidas por autômatos de algoritmo que resolva todos pilha, que usam memória adicional casos Importantes para análise sintática em Reduções transformam um problema compiladores e linguagens de em outro para analisar programação decidibilidade Conhecer decidibilidade é fundamental para entender limites computacionais