Ajude a dar forma ao GoConqr. O que a gente deve adicionar?

Mapa mental

Linguagens formais, Autômatos e Computabilidade

Jubileu Silva Português

Conteúdo do mapa

Linguagens formais, Autômatos e Computabilidade

  1. Linguagens e grámatica

    • Linguagens regulares
      • Autômatos
        • Autômato Finito
          • Deterministico
            • - Dependendo do estado corrente e do simbolo lido - Pode assumir um unico estado
          • Não-deterministico
            • - Dependendo do estado corrente e do simbolo lido - Pode assumir um conjunto de estados alternativos
          • Com movimentos varios
            • - Dependendo do estado corrente e sem ler qualquer simbolo - Pode assumir um conjunto de estados
      • Expressão Regular
      • Grámatica Regular
      • Hierarquia de Chomsky
      • Sistemas de Estados Finitos
    • Linguagens Livre de Contexto
      • Hierarquia de Chomsky
      • Gramática Livre de Contexto
      • Autômato com Pilha
      • Arvore de Derivação
      • Gramática Ambigua
      • Simplificação de Grámatica
        • Simbolos inuteis
          • Exclusão de variaveis ou terminais não-usados
        • Produções Vazias
          • Da forma A -> Ɛ
        • Produções que substituem variaveis
          • Da forma A -> B
      • Forma Normal
        • Forma normal de Chomsky
          • A -> BC ou A -> a
        • Forma normal de Greibach
          • A -> aα α Palavra de Variaveis
  2. Maquina de Turing

    • • São dispositivos mais genéricos que os autômatos vistos até o momento e, portanto, têm a capacidade de trabalhar e processar um número maior de linguagens. • Sua aparência básica é similar a dos autômatos. • Embora as máquinas de Turing sejam primitivas, não existe nenhum modelo computacional mais poderoso até os dias atuais. Existem apenas aperfeiçoamentos deste modelo. • As máquinas de Turing foram propostas como modelos matemáticos para representar procedimentos. • Qualquer cômputo que possa ser descrito por uma máquina de Turing, poderá ser realizado mecanicamente (Tese de Church). • De outra parte, qualquer cômputo que possa ser realizado por um computador digital, poderá ser descrito por uma máquina de Turing.

Informações

Descrição
Mapa Mental sobre Linguagens formais, Autômatos e Computabilidade, criado por Jubileu Silva em 29-06-2020.
Criado por
Jubileu Silva
Visualizações
0
Avaliação

Mais sobre Máquinas de Turing

Fale Conosco

Sobre o que é sua mensagem?

O que a gente deve adicionar?