Linguagens Livres de Contexto

1. Linguagens Sensíveis a Contexto

1.1. Linguagens do Tipo 0 são reconhecidas por uma Máquina de Turing

1.1.1. Podem ser geradas por uma gramática irrestrita

1.1.2. Linguagens Enumeráveis Recursivamente representa o conjunto de todas as linguagens reconhecidas mecanicamente

1.1.3. Uma gramática irrestrita é uma gramática sem restrições nas produções

1.2. Linguagens do Tipo 1 requerem um contexto para a sua aplicação

1.2.1. Podem ser desenvolvidas a partir dos formalismos gerador e reconhecedor

1.3. Gramática sensível ao contexto tem restrição de regra de produção: P É DA FORMA α → β

2. Máquina de Turing

2.1. Modelo proposto por Alan Turing

2.2. Aceita como formalização de um procedimento efetivo

2.3. Sequência finita de instruções realizadas mecanicamente em um tempo finito

2.4. Consiste em 3 partes: fita, unidade de controle e função transição

3. Notação natural

4. Recursividade

4.1. Quebra as palavras em letras, facilitando a leitura

5. AUTOMATOS COM PILHA

5.1. Automato de Estados Finitos Não determinísticos com pilha.

5.1.1. A pilha é independente da fita de entrada (infinita)

5.1.2. Trabalha em sistema de leitura LIFO (Last In, First Out)

5.1.3. Base fixa, topo variável

5.2. Não determinismo aumenta o poder computacional dos Automatos com Pilha