Hierarquia de Chomsky

Prévia do material em texto

Fernando Simeone
A Hierarquia 
de Chomsky
Sumário
• Introdução 
• Linguagens Regulares (3) 
• Linguagens Livre de Contexto (2) 
• Linguagens Recursivamente Enumeráveis (0) 
• Linguagens Sensíveis ao Contexto (1) 
• A Hierarquia de Chomsky
Introdução
Introdução
Introdução
• Linguagens
Introdução
• Linguagens
• Gramáticas
Introdução
• Linguagens
• Gramáticas
• Reconhecedores
Hierarquia de Chomsky
Linguagens Regulares (3)
Linguagens Livre de Contexto (2)
Linguagens Sensíveis ao Contexto (1)
Linguagens Recursivamente Enumeráveis (0)
Linguagens 
Regulares3
T I P O
Hierarquia de Chomsky
Linguagens Regulares (3)
Linguagens Livre de Contexto (2)
Linguagens Sensíveis ao Contexto (1)
Linguagens Recursivamente Enumeráveis (0)
Linguagens Regulares
!
• Linguagens: Linguagens Regulares 
• Gramáticas: Gramáticas Regulares 
• Reconhecedores: Autômatos Finitos
!
L = { a(ba)* } 
aba, ababa, abababa 
!
L = { (a + b)*(aa + bb) } 
aa, bb, aaa, abaa
Linguagens Regulares
G = (V, T, P, S) 
!
Regras de Produção: 
 A ⟶ wB 
 A ⟶ Bw 
 A ⟶ w 
 A ⟶ λ 
Sendo que w ϵ T*, e A, B ϵ V.
Gramáticas Regulares
Gramáticas Regulares
Gramáticas Regulares
 L = { a(ba)* }
(aba, ababa, abababa)
Gramáticas Regulares
G = ({S, A}, {a, b}, P, S) 
 S ⟶ aA 
 A ⟶ baA | λ
 L = { a(ba)* }
(aba, ababa, abababa)
Gramáticas Regulares
G = ({S, A}, {a, b}, P, S) 
 S ⟶ aA 
 A ⟶ baA | λ
 L = { a(ba)* }
(aba, ababa, abababa)
 L = { (a + b)*(aa + bb) }
(aa, bb, aaa, abaa)
Gramáticas Regulares
G = ({S, A}, {a, b}, P, S) 
 S ⟶ aA 
 A ⟶ baA | λ
 L = { a(ba)* }
(aba, ababa, abababa)
G = ({S, A}, {a, b}, P, S) 
 S ⟶ Aaa | Abbe 
 A ⟶ Aa | Ab | λ 
 L = { (a + b)*(aa + bb) }
(aa, bb, aaa, abaa)
Autômatos Finitos
• L = a(ba)*
Autômatos Finitos
• L = a(ba)*
S A qf
B
a λ
ab
Autômatos Finitos
• L = a(ba)*
S A qf
B
a λ
ab
a b a b a
a b b a a
Exemplos:
Autômatos Finitos
• L = a(ba)*
S A qf
B
a λ
ab
a b a b a ✓ Aceita
a b b a a
Exemplos:
x Não aceita
Autômatos Finitos
• L = a(ba)*
S A qf
B
a λ
ab
a b a b a ✓ Aceita
a b b a a
Exemplos:
Linguagens 
Livres de Contexto2
T I P O
Hierarquia de Chomsky
Linguagens Regulares (3)
Linguagens Livre de Contexto (2)
Linguagens Sensíveis ao Contexto (1)
Linguagens Recursivamente Enumeráveis (0)
!
• Linguagens: Linguagens Livres de Contexto 
• Gramáticas: Gramáticas Livres de Contexto 
• Reconhecedores: Autômatos Com Pilha
Linguagens Livres de Contexto
Linguagens Livres de Contexto
!
L = { anbn | n ≥ 0 } 
ab, aabb, aaabbb 
!
L = Expressões aritméticas (+, *, [, ]) 
x + x, x + x * x, x * [x + x]
Gramáticas Livres de Contexto
G = (V, T, P, S) 
!
Regras de Produção: 
 A ⟶ 𝛂 
Sendo que 𝛂 ϵ (T ∪ V)*.
Gramáticas Livres de Contexto
G = (V, T, P, S) 
!
Regras de Produção: 
 A ⟶ 𝛂 
Sendo que 𝛂 ϵ (T ∪ V)*.
Exemplos: 
 A ⟶ aAb 
 B ⟶ aaA
Gramáticas Livres de Contexto
Gramáticas Livres de Contexto
 L = { anbn | n ≥ 0 } 
(ab, aabb, aaabbb)
Gramáticas Livres de Contexto
 L = { anbn | n ≥ 0 } 
(ab, aabb, aaabbb)G = ({S}, {a, b}, P, S) 
 S ⟶ aSb 
 S ⟶ λ 
Gramáticas Livres de Contexto
 L = { anbn | n ≥ 0 } 
(ab, aabb, aaabbb)G = ({S}, {a, b}, P, S) 
 S ⟶ aSb 
 S ⟶ λ 
 L = Expressões aritméticas 
( x + x, x + x * x, x * [x + x] )
Gramáticas Livres de Contexto
G = ({E}, {+, *, [, ], x}, P, E) 
 E ⟶ E + E | E * E | [E] | x
 L = { anbn | n ≥ 0 } 
(ab, aabb, aaabbb)G = ({S}, {a, b}, P, S) 
 S ⟶ aSb 
 S ⟶ λ 
 L = Expressões aritméticas 
( x + x, x + x * x, x * [x + x] )
Autômatos com Pilha
• L = { anbn | n ≥ 0 }
Autômatos com Pilha
• L = { anbn | n ≥ 0 }
S qf
B
(a, λ, B)
(b, B, λ)
(b, B, λ)
(λ, λ, λ) (λ, λ, λ)
Autômatos com Pilha
• L = { anbn | n ≥ 0 }
a a b b
a b b a
Exemplos:
S qf
B
(a, λ, B)
(b, B, λ)
(b, B, λ)
(λ, λ, λ) (λ, λ, λ)
Autômatos com Pilha
• L = { anbn | n ≥ 0 }
a a b b ✓ Aceita
a b b a
Exemplos:
S qf
B
(a, λ, B)
(b, B, λ)
(b, B, λ)
(λ, λ, λ) (λ, λ, λ)
Autômatos com Pilha
• L = { anbn | n ≥ 0 }
x Não aceita
a a b b ✓ Aceita
a b b a
Exemplos:
S qf
B
(a, λ, B)
(b, B, λ)
(b, B, λ)
(λ, λ, λ) (λ, λ, λ)
Linguagens 
Recursivamente 
Enumeráveis0
T I P O
Linguagens Recursivamente Enumeráveis (0)
Hierarquia de Chomsky
Linguagens Sensíveis ao Contexto (1)
Linguagens Livre de Contexto (2)
Linguagens Regulares (3)
Linguagens Recursivamente 
Enumeráveis
!
• Linguagens: Ling. Recursivamente Enumeráveis 
• Gramáticas: Gramáticas Irrestritas 
• Reconhecedores: Máquinas de Turing
!
L = { anbncn | n ≥ 0 } 
abc, aaabbbccc, aabbcc 
!
L = { u[u] | u ϵ {a, b}* } 
aa[aa], aab[aab], baba[baba]
Linguagens Recursivamente 
Enumeráveis
Gramáticas Irrestritas
Gramáticas Irrestritas
G = (V, T, P, S) 
!
Regras de Produção: 
 u ⟶ w 
Sendo que u ϵ (T ∪ V)+ e w ϵ (T ∪ V)*.
Gramáticas Irrestritas
G = (V, T, P, S) 
!
Regras de Produção: 
 u ⟶ w 
Sendo que u ϵ (T ∪ V)+ e w ϵ (T ∪ V)*.
Exemplos: 
 A ⟶ aAb 
 B ⟶ λ 
 bAc ⟶ aA
Gramáticas Irrestritas
Gramáticas Irrestritas
 L = { anbncn | n ≥ 0 } 
(abc, aaabbbccc)
Gramáticas Irrestritas
 L = { anbncn | n ≥ 0 } 
(abc, aaabbbccc)
G = ({S, A, C}, {a, b, c}, P, S) 
 S ⟶ aAbc | λ Cb ⟶ bC 
 A ⟶ aAbC | λ Cc ⟶ cc
Gramáticas Irrestritas
 L = { u[u] | u ϵ {a, b}* } 
( aa[aa], baba[baba] )
Gramáticas Irrestritas
• G = ({S, T, A, B}, {a, b [, ]}, P, S) 
S ⟶ aT[a] | bT[b] Ba ⟶ aB 
T[ ⟶ aT[A | bT[B | [ Bb ⟶ bB 
Aa ⟶ aA A] ⟶ a] 
Ab ⟶ bA B] ⟶ b] 
 L = { u[u] | u ϵ {a, b}* } 
( aa[aa], baba[baba] )
Máquina de Turing
• L ={ anbncn | n ≥ 0 }
Máquina de Turing
• L ={ anbncn | n ≥ 0 }
qf
q0
(B, B, ➞)
q1 q3 q4
q5
q2(a, X, ➞) (b, Y, ➞)
(a, a, ➞)
(Y, Y, ➞)
(b, b, ➞)
(Z, Z, ➞)
(c, Z,←)
(a, a, ←)
(b, b, ←)
(Y, Y, ←)
(Z, Z, ←)
(X, X, ➞)
(Z, Z, ➞)
(Y, Y, ➞)
(Y, Y, ➞)
(B, B, ➞)
(B, B, ➞)
B B B … B
Máquina de Turing
• L ={ anbncn | n ≥ 0 } a a b b c c
a b b a c c
Exemplos:
qf
q0
(B, B, ➞)
q1 q3 q4
q5
q2(a, X, ➞) (b, Y, ➞)
(a, a, ➞)
(Y, Y, ➞)
(b, b, ➞)
(Z, Z, ➞)
(c, Z,←)
(a, a, ←)
(b, b, ←)
(Y, Y, ←)
(Z, Z, ←)
(X, X, ➞)
(Z, Z, ➞)
(Y, Y, ➞)
(Y, Y, ➞)
(B, B, ➞)
(B, B, ➞)
B B B … B
Máquina de Turing
• L ={ anbncn | n ≥ 0 } a a b b c c
a b b a c c
Exemplos:
✓ Aceita
qf
q0
(B, B, ➞)
q1 q3 q4
q5
q2(a, X, ➞) (b, Y, ➞)
(a, a, ➞)
(Y, Y, ➞)
(b, b, ➞)
(Z, Z, ➞)
(c, Z,←)
(a, a, ←)
(b, b, ←)
(Y, Y, ←)
(Z, Z, ←)
(X, X, ➞)
(Z, Z, ➞)
(Y, Y, ➞)
(Y, Y, ➞)
(B, B, ➞)
(B, B, ➞)
B B B … B
Máquina de Turing
• L ={ anbncn | n ≥ 0 } a a b b c c
a b b a c c
Exemplos:
x Não aceita
✓ Aceita
qf
q0
(B, B, ➞)
q1 q3 q4
q5
q2(a, X, ➞) (b, Y, ➞)
(a, a, ➞)
(Y, Y, ➞)
(b, b, ➞)
(Z, Z, ➞)
(c, Z,←)
(a, a, ←)
(b, b, ←)
(Y, Y, ←)
(Z, Z, ←)
(X, X, ➞)
(Z, Z, ➞)
(Y, Y, ➞)
(Y, Y, ➞)
(B, B, ➞)
(B, B, ➞)
B B B … B
Linguagens 
Sensíveis ao Contexto1
T I P O
Linguagens Recursivamente Enumeráveis (0)
Linguagens Sensíveis ao Contexto (1)
Hierarquia de Chomsky
Linguagens Livre de Contexto (2)
Linguagens Regulares (3)
Linguagens Sensíveis 
ao Contexto!
• Linguagens: Linguagens Sensíveis ao Contexto 
• Gramáticas: GramáticasSensíveis ao Contexto 
• Reconhecedores: M. de Turing com fita limitada 
!
L = { anbncn | n > 0 } 
abc, aaabbbccc, aabbcc 
!
L = { ww | w ϵ {a, b}* } 
aa, aabb, abaaba
Linguagens Sensíveis 
ao Contexto
Gramáticas Sensíveis ao Contexto
G = (V, T, P, S) 
!
Regras de Produção: 
 u ⟶ w 
Sendo que u ϵ (T ∪ V)+ e w ϵ (T ∪ V)*, e |u| ≤ |w|.
Gramáticas Sensíveis ao Contexto
G = (V, T, P, S) 
!
Regras de Produção: 
 u ⟶ w 
Sendo que u ϵ (T ∪ V)+ e w ϵ (T ∪ V)*, e |u| ≤ |w|.
Exemplos: 
 A ⟶ aAb 
 Cc ⟶ aAc 
 Aa ⟶ bB 
 B ⟶ λ
Gramáticas Sensíveis ao Contexto
Gramáticas Sensíveis ao Contexto
 L = { anbncn | n > 0 } 
(abc, aabbcc, aaabbbccc)
Gramáticas Sensíveis ao Contexto
G = ({S, A, C}, {a, b, c}, P, S) 
 S ⟶ aAbc | abc 
 A ⟶ aAbC | λ 
 Cb ⟶ bC 
 Cc ⟶ cc
 L = { anbncn | n > 0 } 
(abc, aabbcc, aaabbbccc)
A Hierarquia 
de Chomsky
Hierarquia de Chomsky
Linguagens Regulares (3)
Linguagens Livre de Contexto (2)
Linguagens Sensíveis ao Contexto (1)
Linguagens Recursivamente Enumeráveis (0)
Hierarquia de Chomsky
Linguagem Gramática Reconhecedor
[0] Linguagens 
Recursivamente Enumeráveis Gramáticas Irrestritas Máquina de Turing
[1] Linguagens Sensíveis ao 
Contexto
Gramáticas Sensíveis 
ao Contexto
Máquina de Turing 
com Fita Limitada
[2] Linguagens Livres de 
Contexto
Gramáticas Livres de 
Contexto Autômato com Pilha
[3] Linguagens Regulares Gramáticas Regulares Autômato Finito
0
Hierarquia de Chomsky
Gramáticas
A ⟶ aAb#
B ⟶ aaA
Cc ⟶ aAc#
Aa ⟶ bB
aCc ⟶ aA
A ⟶ abB#
A ⟶ Bab#
A ⟶ λ
0
1
Hierarquia de Chomsky
Gramáticas
A ⟶ aAb#
B ⟶ aaA
Cc ⟶ aAc#
Aa ⟶ bB
aCc ⟶ aA
A ⟶ abB#
A ⟶ Bab#
A ⟶ λ
0
1
2
Hierarquia de Chomsky
Gramáticas
A ⟶ aAb#
B ⟶ aaA
Cc ⟶ aAc#
Aa ⟶ bB
aCc ⟶ aA
A ⟶ abB#
A ⟶ Bab#
A ⟶ λ
0
1
2
Hierarquia de Chomsky
Gramáticas
A ⟶ aAb#
B ⟶ aaA
Cc ⟶ aAc#
Aa ⟶ bB
aCc ⟶ aA
3A ⟶ abB#
A ⟶ Bab#
A ⟶ λ
Referências
• MENEZES, P. B. Linguagens formais e 
autômatos. 4 ed. Sagra-Dcluzzato, 1998. 
• SUDKAMP, T. A. Languages and Machines: An 
Introduction to the Theory of Computer Science 
(3rd Edition). Boston, MA, USA: Addison-
Wesley Longman Publishing Co., Inc., 2005. 
ISBN 0321322215.
Obrigado 
Dúvidas ??