Informática Teórica
Engenharia da Computação
Teoria da Computação
Contexto do que vamos começar a estudar
No início do nosso curso falamos que iríamos
estudar os seguintes modelos de computação:
Autômatos finitos
2. Autômatos com pilha
3. Máquinas de Turing
1.

Estudamos os AFs e vimos que são máquinas
reconhecedoras de linguagens
Teoria da Computação
Contexto do que vamos começar a estudar

As linguagens também podem ser definidas
formalmente por gramáticas, que é um método de
descrever formalmente uma linguagem.
Teoria da Computação
Contexto do que vamos começar a estudar

Curioso: independentemente do desenvolvimento
desses modelos de computação, o linguista Noam
Chomsky buscou formalizar a noção de gramática
e linguagem.

Isso resultou na definição da conhecida
Hierarquia de Chomsky, uma hierarquia de classes
de linguagem definidas por gramáticas de
complexidade crescente.
Teoria da Computação
Hierarquia de Chomsky
1.
2.
3.
1.
2.
3.
Gramáticas lineares à direita
Gramáticas livre de contexto
Gramáticas irrestritas
Autômatos finitos
Autômatos com pilha
Máquinas de Turing
(Tem-se também: gramáticas sensíveis ao contexto –
autômatos linearmente limitados)
Teoria da Computação
Hierarquia de Chomsky
Tipo 0:
Irrestritas
Tipo 1:
Sensível ao contexto
Tipo 2:
Livre de contexto
Tipo 3:
Regulares
Teoria da Computação

Agora nós vamos estudar as linguagens livre de
contexto e consequentemente:
1.
Gramáticas livre de contexto
Autômatos com pilha
2.