itc aula6

Prévia do material em texto

05/10/2012
1
HIERARQUIA DE CHOMSKY
INTRODUÇÃO À TEORIA DA 
COMPUTAÇÃO
1
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Hierarquia de Chomsky
� A hierarquia de Chomsky define importantes tipos 
de gramáticas formais e a hierarquia entre elas
� É a classificação hierárquica de gramáticas formais, 
descrita em 1959 pelo linguista Noam Chomsky.
2
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
2
Hierarquia de Chomsky 
� Níveis 2 e 3 são 
utilizados na descrição 
de linguagem de 
programação e na 
implementação de 
interpretadores e 
compiladores
� Gramática com 
estrutura de frase = 
Gramática Irrestritas
3
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Fonte: wikipédia
Hieraquia de Classes de Linguagens
� Hierarquia de Chomsky é a classificação hierárquica 
de linguagens
4
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Fonte: (Menezes,1999)
05/10/2012
3
Hierarquia de Chomsky
� Correspondência entre as classes de linguagens,
gramáticas e reconhecedores
5
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem Gramática Reconhecedor
Tipo 0: enumerável recursivamente irrestrita máquinas de Turing
Tipo 1: sensível ao contexto sensível ao 
contexto
autômato limitado 
linearmente
Tipo 2: livre do contexto livre do 
contexto
autômatos com pilha
Tipo 3: regular regular autômatos finitos
Linguagens Regulares (LR)
� As Linguagens Regulares ou Tipo 3, segundo a
Hierarquia de Chomsky, representa a classe de
linguagens mais simples
� Possibilita o desenvolvimento algoritmos de
reconhecimento ou de geração de:
� Pouca complexidade,
� Grande eficiência e de
� Fácil implementação.
6
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
4
Linguagens Regulares (LR)
� O estudo das Linguagens Regulares ou Tipo 3, pode
ser abordado através de formalismos:
� Operacional ou reconhecedor (máquina):
� Autômato Finito, (Determinístico, Não-Determinístico ou com
Movimentos Vazios)
� Axiomático ou gerador (gramática):
� Gramática Regular
� Denotacional:
� Expressão Regular
� Também considerado formalismo gerador
7
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Regular
� Uma Gramática Regular é qualquer gramática linear
� Seja G = ( V, T, P, S ) uma gramática e sejam A e B
elementos de V e w uma palavra de T*, então G é:
� Gramática Linear à Direira (GLD) se todas as produções são da forma:
� A � w B ou A � w
� Gramática Linear à Esquerda (GLE) se todas as produções são da forma:
� A � B w ou A � w
� Gramática Linear Unitária à Direira (GLUD) se todas as produções são
como na GLD e | w | ≤ 1.
� Gramática Linear Unitária à Esquerda (GLUE) se todas as produções são
como na GLE e | w | ≤ 1:
8
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
5
Linguagem Livre do Contexto (LLC)
� A Classe das Linguagens Livres do Contexto ou Tipo
2 contém propriamente a Classe das Linguagens
Regulares.
� Seu estudo é de fundamental importância na
informática pois:
� Compreende um universo mais amplo de linguagens
(comparando-se com as regulares)
� Trata questões como parênteses balanceados, construções
bloco-estruturadas, entre outras, típicas de linguagens de
programação como Pascal, C, Algol, etc.
9
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagem Livre do Contexto (LLC)
� Continuação:
� Os algoritmos reconhecedores e geradores que implementam as
Linguagens Livres do Contexto são relativamente simples e
possuem uma boa eficiência;
� Exemplos típicos de aplicações dos conceitos e resultados
referentes às Linguagens Livres do Contexto são analisadores
sintáticos, tradutores de linguagens e processadores de texto em
geral
10
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
6
Linguagens Livres do Contexto
� O estudo das Linguagens Livres do Contexto ou Tipo
2, pode ser abordado através de formalismos:
� Operacional ou reconhecedor (máquina):
� Autômato com Pilha: autômato cuja estrutura básica é análoga à do
Autômato Finito, adicionando uma memória auxiliar tipo pilha (a
qual pode ser lida ou gravada) e a facilidade de não-determinismo
� Axiomático ou gerador (gramática):
� Gramática Livre do Contexto: gramática onde as regras de produção
são definidas de forma mais livre que na Gramática Regular
11
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Gramática Livre do Contexto
� Deve-se ao fato de representar a mais geral classe de
linguagens cuja produção é da forma A → α
� Ou seja, em uma derivação, a variável A deriva α sem
depender ("Livre") de qualquer análise dos símbolos
que antecedem ou sucedem A ("Contexto") na palavra
que está sendo derivada
� Assim toda Linguagem Regular é Livre do Contexto
12
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
7
Linguagens Enumeráveis Recursivamente (LER)
e Linguagens Sensíveis ao Contexto (LSC)
� Para as Linguagens Sensíveis ao Contexto (tipo 1)
serão estudados os formalismos:
� Operacional ou reconhecedor: Máquina de Turing com Fita Limitada
� Axiomático ou gerador – Gramática Sensível ao Contexto
� Para as Linguagens Enumeráveis Recursivamente
(tipo 0) serão estudados os formalismos:
� Operacional ou reconhecedor: Máquina de Turing
� Axiomático ou gerador – Gramática Irrestrita
13
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Naturais (LN) 
� Qualquer linguagem desenvolvida naturalmente
pelo ser humano, como resultado da facilidade inata
para a linguagem possuída pelo intelecto humano
� Exemplos: Línguas faladas e as línguas de sinais (LIBRAS)
� Processamento de linguagem natural (PLN) é uma
subárea da inteligência artificial e da linguística que
estuda os problemas da geração e compreensão
automática de línguas humanas naturais, com
aplicações em diversas áreas
14
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
8
Linguagens Naturais (LN) 
� Noam Chomsky definiu classes como (potenciais)
modelos para linguagens naturais
� Interesse especial nas LLC, pois:
� permitem uma representação simples da sintaxe
� adequadas para a estruturação formal e para a
� análise computacional
� Existem problemas não-solucionáveis
� Exemplo: determinar se uma gramática é ambígua, ou seja, se
existem duas ou mais árvores de derivação distintas para
uma mesma palavra
15
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens de Programação
� É um conjunto de regras sintáticas e semânticas
usadas para definir um programa de computador
� A Teoria das Linguagens Formais fornece meios para
modelar e desenvolver ferramentas
� Descrição de linguagens (léxica/sintática)
� Processos de análise
� Propriedades e limitações algorítmicas
16
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
9
Linguagens de Programação X Hierarquia de Chomsky
� Nem sempre os problemas são tratados
adequadamente na Hierarquia de Chomsky
� Existem linguagens que não são LLC
� Mas, formalismos sensíveis ao contexto é excessivo
� Conhecimento das linguagens sensíveis ao Contexto é
relativamente limitado, uma vez que existem diversos
problemas não-solucionáveis das LLC
� Múltiplas ocorrências de um mesmo trecho de programa, como por
exemplo: declaração de um identificador e suas referências de uso
� alguns casos de validação de expressões com variáveis de tipos
diferentes
17
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Universo de Todas as Linguagens
18
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Fonte:(Menezes,1999)
05/10/2012
10
Universo de Todas as Linguagens
� O universo de todas as linguagens é uma classe de
linguagens muito rica, entretanto:
� Existem conjuntos que não são LER, logo, não é
possível desenvolver uma Máquina de Turing que as
reconheça
19
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Linguagens Recursivas
� A classe das Linguagens Recursivas é uma subclasse
das Linguagens Enumeráveis Recursivamente
� Logo, existe pelo menos uma Máquina de Turing que
pára para qualquer entrada (aceitando/rejeitando)
20
Profa. Ellen Souza - https://sites.google.com/site/ellenuast
05/10/2012
11
Exercício de Revisão
1. Que linguagens são representadas pela Expressões
Regulares apresentadas a seguir:
� aa
� ab*
� (a+b)*
� (a+b)+
� (a+b)*aa(a+b)*
� a*ba*ba*
� (a+b)*(aa+bb)
� (a+λ)(b+ba)*
2. Que palavras são reconhecidas pelas linguagens abaixo?
� L1 = { a
n
b
n
| n ≥ 0 }
� L2 = {a
n
b
m
| n ≥ 0, m ≥0}
� L3 = {w | w possui aa ou bb como subpalavra }
� L4= {w1 : w ∈ {0,1}*}
21
Profa. Ellen Souza - https://sites.google.com/site/ellenuast