LFA

LFA

1. Linguagem Regulares

   • Linguagem Simples
   • Grande eficiência
   • Fácil Implementação
   • Sistema de estados finitos - Número finito e predefinido de estados
   • Formalismo
     • Deterministico
       • Depende do estado corrente e do símbolo lido
       • Pode assumir um único estado
     • Não deterministico
       • Pode assumir um conjunto de estados alternativos
     • Com movimento vazio
       • Dependendo do estado corrente e sem ler qualquer símbolo
       • Pode assumir um conjunto de estados
   • Expressão Regular
     • Definida a partir de um conjunto de linguagens e operações
   • Gramatica Regular
     • Linear a Direita
     • Linear a Esquerda
     • Linear Unitária a Direita
     • Linear Unitária a Esquerda

2. Linguagens Livre do Contexto

   • Ambiguidade
     • é dita ambígua se existe uma palavra que possua duas ou mais árvores de derivação
   • Simplificação
     • 1º - Retirada de produções vazias
     • 2º - Retirada de produções unitárias
     • 3º - Retirada de símbolos inúteis ou inacessíveis
   • Forma Normal de Chomsky
     • É dita estar na forma normal de chomsky se todas as produções são da forma: A -> BC ou A -> a
     • 1º Etapa - Simplificação
     • 2º Etapa - Lado direito de comprimento >= 2
     • 3º Etapa - Exatamente duas variáveis no lado direito das produções
   • Forma Normal de Greibach
     • 1º Etapa - Simplificação
     • 2º Etapa - Renomeia as Variáveis em Ordem Crescente
     • 3º Etapa - Transformação de produções para a forma Ar -> Asa, onde s <= r
     • 4º Etapa - Exclusão das recursos da forma Ar -> Ara
     • 5º Etapa - Um terminal no início, do lado direito de cada produção
     • 6º Etapa - Produções A -> aB*

3. Linguagens Sensíveis ao Contexto

   • Máquina de Turing
     • Ler um símbolo de um quadrado
     • Alterar um símbolo em um quadrado
     • Mover os olhos para outro quadrado
     • Fim dos cálculos
     • Fita
       • Dispositivo de entrada, saída e memória de trabalho
     • Unidade de controle
       • Reflete o estado corrente da máquina
       • Possui uma unidade de leitura e gravação
       • Acessa uma célula da fita de cada vez
       • Se movimenta para a esquerda ou para a direita
     • Programa, Função Programa ou Função de transição
       • Define o estado da máquina
   • Gramática
     • Máquina de Turing com Fita Limitada

4. Linguagens Recursivamente Enumeráveis

   • Decidibilidade
   • semi-decidibilidade