Aula 2 - Linguagens e Hierarquia de Chomsky

Prévia do material em texto

Prof. Ricardo Mesquita
Linguagens e Hierarquia de Chomsky
Sumário
 Introdução
 Linguagens Regulares
 Linguagens Livres de Contexto
 Linguagens Sensíveis a Contexto
 Linguagens Recursivamente Enumeráveis
 A Hierarquia de Chomsky
Prof. Ricardo Mesquita2
Observações
 Na aula de hoje faremos uma apresentação sobre os tipos de 
linguagens e suas respectivas gramáticas geradoras.
 Este conteúdo refere-se à disciplina de Linguagens 
Formais.
 Da mesma forma, mencionaremos autômatos finitos, 
autômatos de pilha e máquina de Turing, cujo teor refere-se à 
disciplina de Teoria da Computação.
 Assim, esta aula tem caráter de breve revisão deste conteúdo.
 Oportunamente, será indicada a abordagem para 
Compiladores
Prof. Ricardo Mesquita3
Linguagens Regulares
Prof. Ricardo Mesquita4
Linguagens Regulares
Observações:
A linguagem está em sua representação por expressões regulares
O + aqui representa opção e não o símbolo aritmético
A representação está 
sendo feita usando-se 
expressões regulares
Prof. Ricardo Mesquita5
Gramáticas Regulares
G = (N, T, P, S)
Regras de Produção obedecem
o seguinte formato:
A → wB
A → Bw
A → w
A →
onde w T*, e A e B  N.
Atenção:
Aqui não temos a representação 
de uma gramática específica!!
Apenas encontram-se 
demonstrados os tipos possíveis
de regras de produção em uma 
gramática!
Prof. Ricardo Mesquita6
Gramáticas Regulares
Prof. Ricardo Mesquita7
Autômatos Finitos
Prof. Ricardo Mesquita8
Linguagens Livres de Contexto
Prof. Ricardo Mesquita9
Linguagens Livres de Contexto
Prof. Ricardo Mesquita10
Gramáticas Livres de Contexto
Observação: 
As linguagens de programação são definidas com gramáticas livres 
de contexto!
Prof. Ricardo Mesquita11
Gramáticas Livres de Contexto
Prof. Ricardo Mesquita12
Autômatos com Pilha
Prof. Ricardo Mesquita13
Linguagens Sensíveis ao Contexto
Prof. Ricardo Mesquita14
Linguagens Sensíveis ao Contexto
Prof. Ricardo Mesquita15
Gramáticas Sensíveis ao Contexto
G = (V, T, P, S)
G é sensível a contexto se suas regras de produção são da forma:
→ , com
𝛼 ∈ (𝑉 ∪ 𝑇)+
𝛽 ∈ (𝑉 ∪ 𝑇)∗
|𝛽| ≥ |𝛼|
Uma característica marcante:
Gramáticas Sensíveis ao contexto admitem 
sequências do tipo u  (𝑉 ∪ 𝑇)+ no lado 
esquerdo das produções!
Prof. Ricardo Mesquita16
Gramáticas Sensíveis ao Contexto
 Exemplo:
G=({a, b, c, S, B, C},{a, b, c}, P, S)
P = { S → aSBC,
S → aBC,
CB → BC,
aB → ab,
bB→ bb,
bC→ bc,
cC → cc }
Prof. Ricardo Mesquita17
Gramáticas Sensíveis ao Contexto
Prof. Ricardo Mesquita18
Linguagens Recursivamente Enumeráveis
Prof. Ricardo Mesquita19
Linguagens Recursivamente Enumeráveis
Prof. Ricardo Mesquita20
Gramáticas Irrestritas
 G = (V, T, P, S) é dita irrestrita se nenhuma restrição adicional 
é aplicada às suas regras de produção, ou seja, suas regras de 
produção seguem a forma geral: 
𝛼 → 𝛽, 𝛼 ∈ (𝑉 ∪ 𝑇)+, 𝛽 ∈ (𝑉 ∪ 𝑇)∗
 Note que as gramáticas regulares, livres de contexto e sensíveis a 
contexto são casos particulares das gramáticas irrestritas.
Prof. Ricardo Mesquita21
Gramáticas Irrestritas
Prof. Ricardo Mesquita22
Gramáticas Irrestritas
Prof. Ricardo Mesquita23
Máquina de Turing
24
Hierarquia de Chomsky
Prof. Ricardo Mesquita25
Hierarquia de Chomsky
Prof. Ricardo Mesquita26
Hierarquia de Chomsky
Prof. Ricardo Mesquita27
Dúvidas?
Prof. Ricardo Mesquita28