LINGUAGENS E GRAMÁTICAS
Prof. Ronaldo R. Goldschmidt
[email protected]
LINGUAGENS E GRAMÁTICAS
LINGUAGENS E GRAMÁTICAS
Definição de Linguagem (Aurélio): “o uso da palavra
articulada ou escrita como meio de expressão e comunicação
entre pessoas”.
Definição insuficiente para permitir o desenvolvimento de
uma teoria formal sobre linguagens.
Linguagem é um dos conceitos mais fundamentais em
Computação e Informática.
Conceitos como alfabeto e cadeia de caracteres são
necessários para definir formalmente uma linguagem.
LINGUAGENS E GRAMÁTICAS
Def.: Um alfabeto Σ é um conjunto finito de símbolos (unidade
atômica) de algum tipo.
Exs.: Σ={a, b, c, ..., z} – alfabeto romano
Σ={0, 1} – alfabeto binário
Σ=∅ – alfabeto vazio
Σ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} – alfabeto hexa
Σ=N – o conjunto dos naturais não é um alfabeto
Obs.: Cada símbolo é considerado como uma unidade atômica, não
importando sua representação visual. Exemplos de símbolos: a,
abc, begin, if, 5, 1024, 2.017e4.
LINGUAGENS E GRAMÁTICAS
Obs.: Por simplicidade, em geral, os símbolos utilizados são letras,
números e outros caracteres especiais tais como $, “espaço”, #
ou *, por exemplo.
Obs.: No entanto, não há uma definição formal para “símbolo”. O seu
significado deve ser intuído como uma entidade abstrata, um
conceito primitivo, e aceitá-lo como base para a teoria que será
desenvolvida.
LINGUAGENS E GRAMÁTICAS
Ex.: Alfabeto da Linguagem de Programação Pascal
Conjunto de símbolos (da tabela ASCII) usados na construção
de programas:
• Letras
• Dígitos
• Caracteres especiais como “<”, “/”, dentre outros
• Espaço ou “Branco”
Obs.: O alfabeto binário {a, b} é usado com freqüência. Além
da simplicidade, possui analogia com a representação
interna de computadores reais (o domínio de valores de
um bit é binário).
LINGUAGENS E GRAMÁTICAS
Def.: Uma cadeia (de caracteres) sobre um alfabeto é uma
seqüência finita de símbolos deste alfabeto justapostos.
Ex.: Sendo Σ={a, b}, são exemplos de cadeias: aba, aaaa,
bababb, a, b.
Em uma linguagem de programação, uma cadeia corresponde
a um programa.
São sinônimos de cadeia: palavra, sentença ou string.
Def.: A cadeia sem símbolos é chamada de cadeia vazia.
Notação: ε (ou λ)
Obs: ∅ ≠ {εε}
LINGUAGENS E GRAMÁTICAS
Def.: O comprimento de uma cadeia sobre um alfabeto é o
número de símbolos contidos na cadeia. Notação: |ω| é
o comprimento de uma cadeia qualquer ω
Exs.: |abra| = 4
|εε|=0
|xpto123|=7
Obs: Uma cadeia ω pode ser considerada como uma função
ω:{1, 2, ..., |ω|} ∑ (chamada isomorfismo natural). O
valor ω(j) corresponde ao símbolo na j-ésima posição de
ω, onde 1 ≤ j ≤ |ω|.
Ex.: ω=abra ω(1)= ω(4) = a; ω(2)=b; ω(3)=r
LINGUAGENS E GRAMÁTICAS
Def.: Se ω e µ são cadeias, então ω.µ (ou simplesmente ωµ) é a
concatenação da cadeia ω com a cadeia µ.
Ex.: abra.cadabra = abracadabra
Obs.: Para toda cadeia ω, εω = ωε = ω (ε é o elemento neutro)
Obs.: |ω.µ| = |ω| + |µ|
Ex.: |abra.cadabra| = |abra| + |cadabra| = 4 + 7 = 11
|abracadabra| = 11
Obs.: A operação de concatenação é associativa porém não é
comutativa:
ω.(µ.δ)=(ω.µ).δ
ω.µ ≠ µ.ω
LINGUAGENS E GRAMÁTICAS
Ex.: Concatenação de palavras u=ab v=ba uv=abba
Ex.: Concatenações sucessivas:
u³=ababab
u0=εε
un+1 = un .u
abra3 = abraabraabra
an = aaaa...a (o símbolo a repetido n vezes)
Obs.: O segundo e o terceiro exemplos de concatenação
sucessiva compõem um exemplo de definição por
indução.
LINGUAGENS E GRAMÁTICAS
Def.: Define-se cadeia elementar (ou unitária) a qualquer
cadeia formada por um único símbolo.
Ex: α = a é uma cadeia elementar pois | α | = 1
Obs: Os símbolos do alfabeto da Língua Portuguesa são
construídos a partir da concatenação de um número
variável de caracteres (letras do alfabeto romano).
Nesse sentido e contexto, embora representados com
diversos caracteres, tais símbolos são considerados
cadeias elementares.
LINGUAGENS E GRAMÁTICAS
Ainda no caso do alfabeto da Língua Portuguesa:
consideremos que ele contenha todas as palavras de nosso
idioma (conjugações de todos os verbos, as formas
flexionadas de todos os adjetivos, substantivos, etc.).
Exemplo de cadeia:
α = “Exemplo de cadeia no alfabeto da Língua Portuguesa”
|α|=8
Note que o alfabeto da Língua Portuguesa, embora extenso, é
finito e pode gerar infinitas cadeias.
LINGUAGENS E GRAMÁTICAS
Verifique se são verdadeiras ou falsas as afirmativas abaixo,
justificando suas respostas.
a) Se ω = r.s e |ω| = n e |r| = m Então |s| = n - m
b) Se u2=u Então u=ɛ
c) |un| = n|u|, para n ≥ 0
d) Se ω = abc Então ω(4) não está definido
e) Se ω = abc Então ω2(4) = ɛ
LINGUAGENS E GRAMÁTICAS
Def.: Prefixo de ω é toda cadeia obtida a partir da remoção de
0 ou mais símbolos do final de ω.
Ex.: A cadeia abra possui 5 prefixos: abra, abr, ab , a, ε
Def.: Prefixo próprio de ω é todo prefixo de ω diferente de ω.
Ex.: A cadeia abra possui 4 prefixos próprios: abr, ab , a, ε
LINGUAGENS E GRAMÁTICAS
Def.: Sufixo de ω é toda cadeia obtida a partir da remoção de
0 ou mais símbolos do começo de ω.
Ex.: A cadeia abra possui 5 sufixos: abra, bra, ra, a, ε
Def.: Sufixo próprio de ω é todo sufixo de ω diferente de ω.
Ex.: A cadeia abra possui 4 sufixos próprios: bra, ra, a, ε
LINGUAGENS E GRAMÁTICAS
Def.: Subcadeia (ou Subpalavra) de ω é toda cadeia obtida a
partir da remoção de um prefixo e/ou um sufixo de ω.
Exs.: São exemplos de subcadeias de abra: br, a, ab, ra, ε
Def.: Uma cadeia reversa é uma cadeia em que os símbolos
são escritos em ordem inversa da cadeia original. Notação:
ωR
Obs.: Seja ω = a1a2...an, com ai ∈ Σ, i ≥ 0. Então, a reversa de
ω é ωR = an...a2a1
Ex.:
ω = abra e ωR = arba
LINGUAGENS E GRAMÁTICAS
Definição formal do reverso de uma cadeia ω dada por indução:
(i) Se ω é uma cadeia tal que | ω | = 0, então ωR = ω = ε
(ii) Se ω é uma cadeia tal que | ω | = n + 1 > 0, então ω = ua para
algum a ∈ Σ e ωR = auR
Obs.: A seguir uma ilustração de como uma prova por indução pode
depender de uma definição dada por indução.
Teorema: Para quaisquer cadeias ω e µ, (ωµ)R = µRωR
Ex: (dogcat)R = (cat)R (dog)R =tacgod
LINGUAGENS E GRAMÁTICAS
Para quaisquer cadeias ω e µ, (ωµ)R = µR ωR . Demonstração:
(i) Sup. | µ | = 0
Portanto, µ = ε
Logo: (ωµ)R = (ωε)R = ωR = εωR = ε R ωR = µR ωR
(ii) Hipótese de Indução: se | µ | ≤ n, então (ωµ)R = µR ωR
(iii) Passo Indutivo: Seja | µ | = n + 1. Então, µ = ua, para alguma cadeia u e a ∈ Σ
tal que | u | = n (note que | a | = 1)
Logo: (ωµ)R = (ω(ua))R, pois µ = ua
= ((ωu)a)R, pois a concatenação é associativa
= a(ωu)R, pela definição de cadeia reversa de (ωu)a
= auRωR, pela hipótese de indução
= (ua)RωR, pela definição de cadeia reversa de ua
= µR ωR , uma vez que µ = ua
LINGUAGENS E GRAMÁTICAS
Def.: Uma cadeia palíndroma é toda cadeia ω tal que ω = ωR.
Exs.:
arara, seres, salas, reviver, ovo, osso, radar, ama, anilina, mamam,
socos, tapas, somos, somavamos, ala, ata, radar, rapar, mirim,
reler, reviver, sacas, siris, ame a ema, assam a massa, etc...
Atenção: Convenção de tipo para símbolos, cadeias e alfabetos:
Símbolos Letras minúsculas do início do alfabeto romano (a, b, c)
ou dígitos.
Cadeias Letras minúsculas do final do alfabeto romano (w, x, y, z)
ou letras minúsculas do alfabeto grego (ω, µ, etc..)
Alfabetos Letras maiúsculas do alfabeto grego (Σ, Γ, Ω, etc...)
LINGUAGENS E GRAMÁTICAS
Def.: O conjunto de todas as cadeias, incluindo a cadeia
vazia, sobre um alfabeto Σ é denotado por Σ*
Obs.: O conjunto de todas as cadeias sobre um alfabeto Σ é
definido recursivamente por:
i) ε ∈ ∑*
e para qualquer ω ∈ ∑ , vale que ω ∈ ∑*
ii) para qualquer ω, µ ∈ ∑* , vale que ωµ ∈ ∑*
Ex: Se ∑ = {a, b}, então:
∑+ = {a, b, aa, ab, ba, bb, aaa, ...}
∑* = {ε, a, b, aa, ab, ba, bb, aaa, ...}
LINGUAGENS E GRAMÁTICAS
Def.: O conjunto de todas as cadeias, incluindo a cadeia
vazia, sobre um alfabeto Σ é denotado por Σ*
Obs.: Σ é um alfabeto finito com n elementos, mas Σ * é
infinito. Pode ser enumerado da seguinte forma:
i) Para cada k ≥ 0, todas as strings de comprimento k devem
ser enumeradas antes das de comprimento k+1
ii) As nk strings devem ser enumeradas lexicograficamente.
Ex: Se ∑ = {0, 1}, então:
∑* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}
LINGUAGENS E GRAMÁTICAS
Def.: Uma linguagem formal L sobre um alfabeto Σ é
qualquer subconjunto de Σ*, L ⊆ Σ*
Exs: Ø, Σ, Σ*, Σ+ são linguagens formais sobre qualquer Σ
Obs.: Como muitas linguagens são infinitas, utiliza-se a
seguinte representação implícita de conjuntos:
L = {ω ∈ Σ* / ω possui uma propriedade P}
Exs.: {ω ∈ Σ* / ω = ωR}, linguagem de palavras palíndromas
{aω / ω ∈ Σ*}, linguagem de palavras iniciadas por “a”,
{ω ∈ Σ*/ ω(1)=a}
LINGUAGENS E GRAMÁTICAS
Def.: Uma linguagem formal L sobre um alfabeto Σ é
qualquer subconjunto de Σ*, L ⊆ Σ*
Obs.: 2Σ* é o conjunto de todas as linguagens sobre um
alfabeto Σ.
Ex.: Linguagem Formal: Linguagem de Programação
Uma Linguagem de Programação como Pascal é formalmente
definida pelo conjunto de todos os programas (palavras) da
linguagem.
Obs: Sejam L uma linguagem formal sobre Σ e Σ ⊆ Ω.
Pergunta-se: L é linguagem formal sobre Ω ?
LINGUAGENS E GRAMÁTICAS
Relação entre símbolo, alfabeto, cadeia e linguagem
LINGUAGENS E GRAMÁTICAS
Relação entre símbolo, alfabeto, cadeia e linguagem
LINGUAGENS E GRAMÁTICAS
Relação entre símbolo, alfabeto, cadeia e linguagem
Obs: Distinção entre o símbolo “b” e a cadeia/sentença “b”
LINGUAGENS E GRAMÁTICAS
Atividades Práticas
• Lista de Exercícios II – Até o exercício 7
Exercício de Programação
Exercício 17 da Lista II: Elabore um programa em C que apresente o valor
decimal e o glifo correspondente da tabela ASCII do símbolo 32 ao símbolo 126
(caracteres imprimíveis).
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Obs: Linguagens são conjuntos (em essência)
União
L1 ∪ L2 = { s | s ∈ L1 ou s ∈ L2 }
Ex.: { ab, ac } ∪ { ab, bc } = { ab, ac, bc }
Interseção
L1 ∩ L2 = { s | s ∈ L1 e s ∈ L2 }
Ex.: { ab, ac } ∩ { ab, bc } = { ab }
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Obs: Linguagens são conjuntos (em essência)
Concatenação
L1.L2 = { st | s ∈ L1 e t ∈ L2 }
Ex.: { ab, ac }.{ ab, bc } = { abab, abbc, acab, acbc }
Observações:
• L1.∅ = ∅. L1 = ∅
(demonstração)
• Concatenação não é comutativa (contraexemplo)
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Fechamento de Kleene (Estrela de Kleene)
Seja A uma linguagem definida sobre um alfabeto Σ. Então A* é
uma linguagem obtida a partir de A como se segue:
A* = A0 ∪ A1 ∪ ... ∪ An ∪ ...
onde: A0 = { ε }
e
An = An-1.A, n ≥ 0
Ex.1: A = { a }
A* = { ε } ∪ { a } ∪ { aa } ∪ { aaa } ∪...
= { ε, a, aa, aaa, ... }
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Fechamento de Kleene (Estrela de Kleene)
Seja A uma linguagem definida sobre um alfabeto Σ. Então A* é
uma linguagem obtida a partir de A como se segue:
A* = A0 ∪ A1 ∪ ... ∪ An ∪ ...
onde: A0 = { ε }
e
An = An-1.A , n ≥ 0
Ex2.: A = { ab, b}
A* = { ε } ∪ { ab, b } ∪ { abab, abb, bab, bb } ∪...
= { ε, ab, b, abab, abb, bab, bb, ... }
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Fechamento de Kleene (Estrela de Kleene)
Seja A uma linguagem definida sobre um alfabeto Σ. Então A* é
uma linguagem obtida a partir de A como se segue:
A* = A0 ∪ A1 ∪ ... ∪ An ∪ ...
onde: A0 = { ε }
Ex3.: A = ∅
A* = { ε }
e
An = An-1.A , n ≥ 0
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Fechamento Positivo
A+ = A*.A ou A* = { ε } ∪ A+
Ex.: A = { a }
A+ = { ε, a, aa, aaa, ... }.{ a } = { a, aa, aaa, ... }
Complemento
A =
Ex.:
∑
*
A={a}
− A
A = { ε, a, aa, aaa, ... }-{ a } = {ε, aa, aaa, ... }
LINGUAGENS E GRAMÁTICAS
Operações com Linguagens (Construção de Outras Linguagens)
Quociente
L1/L2 = { x | xy ∈ L1 e y ∈ L2 }
Exs.: { abb, acb }/{ b } = { ab, ac }
{ abb, acb }/{ b, bb } = { ab, ac, a }
Sendo:
L1 = { aib | i ≥ 0 } = {b, ab, aab, aaab, ...} L2 = { b }
L3 = { aib | i ≥ 1 } = {ab, aab, aaab, ...}
L1/ L2 = {ɛ, a, aa, aaa, aaaa, ...} = { ai | i ≥ 0 }
L1/ L3 = {ɛ, a, aa, aaa, ...} = { ai | i ≥ 0 }
LINGUAGENS E GRAMÁTICAS
Sendo:
L1 = { aib | i ≥ 0 } = {b, ab, aab, aaab, ...} L2 = { b }
L3 = { aib | i ≥ 1 } = {ab, aab, aaab, ...}
L4 = { aibci | i ≥ 0 } = {b, abc, aabcc, aaabccc, ...}
L5 = { bci | i ≥ 0 } = {b, bc, bcc, bccc, ...}
L6 = { ci | i ≥ 1 } = {c, cc, ccc, ...}
L4/ L5 =
L5/ L4 =
L1/ L5 =
L4/ L1 =
L6/ L2 =
LINGUAGENS E GRAMÁTICAS
Atividades Práticas
• Lista de Exercícios II – Exercício 8
Exercício de Programação
Exercício 18 da Lista II: Elabore um programa em C que receba como entrada
duas linguagens finitas L1 e L2, ambas não vazias (e sem a cadeia vazia) e
apresente como saídas as seguintes linguagens: L1 ∪ L2, L1 ∩ L2, L1.L2.
LINGUAGENS E GRAMÁTICAS
Observação:
Na teoria de autômatos, um problema em geral se caracteriza
pela decisão se uma determinada cadeia pertence ou não a
uma linguagem específica.
Em termos coloquiais, um problema pode ser expresso como
pertinência a uma linguagem.
Em termos formais, sendo L uma linguagem formal sobre Σ,
então o problema L consiste em: dada uma cadeia ω em Σ*,
definir se ω está ou não em L.
LINGUAGENS E GRAMÁTICAS
Métodos de Representação Finita de Linguagens:
• Gramáticas
• Reconhecedores
• Enumerações
Obs: Os dois primeiros são formas duais de representação.
Obs: A notação usada para representar uma linguagem é
chamada de metalinguagem.
Exs:
L={ω ∈ Σ* / ω é palíndroma}
L={ara, arara, ...}
LINGUAGENS E GRAMÁTICAS
Toda Linguagem possui:
• Sintaxe – Estruturas para representação de construções
Ex: arara ∈ L={ω ∈ Σ* / ω é palíndroma}, Σ={a,r}
• Semântica – Significado associado às construções
arara
LINGUAGENS E GRAMÁTICAS
Como uma linguagem de programação é o conjunto (infinito) de
todos os programas dessa linguagem, ela requer uma definição
adequada para ser implementada computacionalmente (gramática).
Uma gramática é um sistema formal baseado em regras de
substituição que, quando aplicadas sucessivamente, podem gerar,
de forma exaustiva, o conjunto de cadeias que compõem uma
determinada linguagem. Assim, o conjunto de todas as palavras
geradas por uma gramática define a linguagem associada.
As gramáticas usadas para linguagens naturais como o Português
são análogas às usadas para linguagens artificiais como o Pascal e
o C.
LINGUAGENS E GRAMÁTICAS
Consideremos a oração em Português: “O menino atravessou a rua
distraidamente”. Esta oração está sintaticamente correta, pois obedece às seguintes
regras:
• Frase = Sujeito + Predicado + Complemento
• Sujeito = Artigo + Substantivo
• Predicado = Verbo + Objeto Direto
• Objeto Direto = Artigo + Substantivo
• Artigo = {o, a}
• Substantivo = {menino, rua}
• Verbo = {atravessou}
• Complemento = {distraidamente}
E as orações: “A rua atravessou o menino distraidamente” e “O rua atravessou a
menino distraidamente”?
LINGUAGENS E GRAMÁTICAS
Repare que “artigo”, “substantivo” e “verbo” são exemplos de
classes gramaticais da Língua Portuguesa. Normalmente
independente da oração para classificarmos os símbolos. No
exemplo:
•Artigo = {o, a}
• Substantivo = {menino, rua}
• Verbo = {atravessou}
“Sujeito”, “predicado”, “objeto direto” são exemplos de funções
sintáticas que os símbolos, isolados ou em conjunto, assumem na
oração. A caracterização da função sintática depende do símbolo (ou
conjunto de símbolos) e do papel que ele exerce na oração.
LINGUAGENS E GRAMÁTICAS
Um site que permite a análise de sentenças (parser) da Língua
Portuguesa é o VISL:
http://beta.visl.sdu.dk/visl/pt/parsing/automatic/trees.php
Exemplo:
LINGUAGENS E GRAMÁTICAS
Def.: Uma Gramática de Chomsky, Gramática Irrestrita ou simplesmente
Gramática é uma quádrupla ordenada:
G=(V,T,P,S) , na qual:
• V e T conjuntos finitos não vazios e disjuntos de símbolos variáveis e
terminais, respectivamente.
• P:(V∪T)+ (V∪T)* é uma Relação de Produções (Regras de Substituição),
sendo conjunto um conjunto finito e não vazio.
• S, um símbolo destacado de V (chamado símbolo inicial)
Regras de Produção – Formato
(α,β) ou α β
α β1| β2| ...| βn
LINGUAGENS E GRAMÁTICAS
Derivação: Substituição de uma subpalavra de acordo com uma regra
de produção.
Formalmente: Sendo G=(V, T, P, S) uma gramática, uma Derivação é
um par da relação de derivação ⇒: (V∪T)+ (V∪T)*, representado
por: <α, β> ou α ⇒G β
⇒G é indutivamente definida como segue:
• Para toda regra de produção S → β, o seguinte par pertence a ⇒G :
S ⇒G β
• Para todo par η ⇒G ρασ de ⇒G, se α → β é uma regra de
produção, então o seguinte par pertence a ⇒G: η ⇒G ρ β σ
LINGUAGENS E GRAMÁTICAS
Ex: Seja uma gramática G=(V, T, P, N) definida por
V={N,D}
T={0,1,2,...,9}
P={ND, NDN, D0|1|2|...|9}
Uma derivação da palavra 243 pode ser dada por:
N⇒G
DN⇒G
2N⇒G
2DN⇒G
24N⇒G
24D⇒G
243
(NDN)
(D2)
(NDN)
(D4)
(ND)
(D3)
Pergunta-se: Existem outras derivações para a mesma palavra?
LINGUAGENS E GRAMÁTICAS
Derivação: Substituição de uma subpalavra de acordo com uma
regra de produção.
Sucessivos passos de derivação são definidos como segue:
⇒* Fecho transitivo e reflexivo da relação ⇒, ou seja, zero ou
mais passos de derivações sucessivos.
⇒+ Fecho transitivo da relação ⇒, ou seja, um ou mais passos de
derivações sucessivos.
⇒i Exatos i passos de derivações sucessivos, sendo i um número
natural.
LINGUAGENS E GRAMÁTICAS
Voltando ao exemplo anterior: G=(V, T, P, N) definida por
V={N,D}
T={0,1,2,...,9}
P={ND, NDN, D0|1|2|...|9}
Como vimos, uma derivação da palavra 243 pode ser dada por:
N⇒
DN⇒
2N⇒
2DN⇒
24N⇒
24D⇒
243
(NDN)
(D2)
(NDN)
(D4)
(ND)
(D3)
Portanto, temos que: S ⇒* 243 ou S ⇒+ 243 ou S ⇒6 243
LINGUAGENS E GRAMÁTICAS
Def.: Seja G=(V, T, P, S) uma gramática. A Linguagem Gerada
por G é composta por todas as palavras de símbolos terminais
deriváveis a partir de S.
Notação: L(G) ou GERA(G) = {w ∈ T* / S⇒+w}
Ex:
Sendo V={N,D}
T={0,1,2,...,9}
P={ND, NDN, D0|1|2|...|9}
G=(V, T, P, N) é uma gramática capaz de gerar qualquer número
natural válido em uma linguagem de programação.
LINGUAGENS E GRAMÁTICAS
Analisando o exemplo anterior, onde:
G=(V, T, P, N) é uma gramática geradora de números naturais.
V={N,D}
T={0,1,2,...,9}
P={ND, NDN, D0|1|2|...|9}
A seguinte interpretação indutiva pode ser dada:
• Base da Indução: todo dígito é um número natural (regras ND
e D0|1|2|...|9).
• Passo de Indução: Se x é um número natural, então a
concatenação de x com qualquer dígito também é um número
natural (regra NDN).
LINGUAGENS E GRAMÁTICAS
Existem representações alternativas para gramáticas. Uma das mais comuns é:
G = (V, Σ, P, S), onde:
V contém todo o vocabulário (todos os símbolos)
Σ contém os símbolos terminais
P contém as produções
S é o símbolo inicial
N = V - Σ (corresponde ao conjunto de símbolos variáveis da definição adotada
na disciplina)
Exemplo: a gramática geradora de números naturais vista no exemplo anterior
G = (V, Σ, P, S)
V = {S, D, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
P = {SD, SDS, D0|1|2|...|9}
LINGUAGENS E GRAMÁTICAS
Def.: Duas gramáticas G1 e G2 são ditas equivalentes se ambas
geram a mesma linguagem, ou seja:
Gera (G1) = Gera(G2)
Obs: Em geral, adotaremos as seguintes convenções:
• A, B, C, ..., S, T para símbolos variáveis
• a, b, c, ..., s, t para símbolos terminais
• u, v, w, x, y, z para palavras com somente símbolos terminais
• α, β, ... para palavras com símbolos terminais ou variáveis
LINGUAGENS E GRAMÁTICAS
Consideremos as seguintes gramáticas e respectivas linguagens:
• G0 = ({S},{a,b},{S→aS, S→bS, S→ ε},S),
L0=Gera(G0)={a, b}*
• G1 = ({S},{a,b},{S→aS, S→bS, S→ a|b},S),
L1=Gera(G1)={a, b}+
• G2 = ({S,X},{a,b},{S→aX, X→aX, X→bX, X→ε},S),
L2 formada por cadeias iniciadas pelo símbolo a.
• G3 = ({S,X},{a,b},{S→aX, X→aX, X→bX, X→b},S),
L3 formada por cadeias iniciadas pelo símbolo a e terminadas por b.
• G4 = ({S,X},{a,b},{S→XbXbX, X→aX, X→ε},S),
L4 formada por cadeias que contenham exatamente dois símbolos b.
• G5 = ({S,X},{a,b},{S→bX, X→aX, X→ε},S),
L5 contém cadeias iniciadas com o símbolo b, sendo este o único símbolo b
existente nessas cadeias.
Para cada uma, apresente um exemplo de sentença e de derivação associada
LINGUAGENS E GRAMÁTICAS
Consideremos as seguintes gramáticas e respectivas linguagens:
• L0=Gera(G0)={a, b}*, L1=Gera(G1)={a, b}+, L2 formada por cadeias iniciadas
pelo símbolo a. L3 formada por cadeias iniciadas pelo símbolo a e terminadas por
b. L4 formada por cadeias que contenham exatamente dois símbolos b. L5 contém
cadeias iniciadas com o símbolo b, sendo este o único símbolo b existente nessas
cadeias.
Analise as relações
inclusão entre elas.
de
LINGUAGENS E GRAMÁTICAS
Uma gramática G = (V, T, P, S) está bem formada se atender às
seguintes condições mínimas:
• V, T, P devem ser conjuntos finitos e não vazios;
•Σ=V∪T
•V∩T=∅
•S∈V
Uma gramática pode estar bem formada mas não gerar todas as
cadeias de uma linguagem. Exemplos: G = (V, T, P, S), onde:
a) V = {S, X}, T = {a, b}, P = {X→aX | b}, S}
b) V = {S}, T = {a, b}, P = {S→aS | b}, S}, mas G não gera bba
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky
Estudo sistemático das linguagens formais teve forte impulso no final
da década de 1950 com publicação de dois artigos do linguista Noam
Chomsky.
Os artigos apresentavam resultados sobre a classificação hierárquica
das linguagens, conhecida como Hierarquia de Chomsky.
Tal hierarquia tem como mérito agrupar as linguagens em classes, de
tal forma que elas possam ser hierarquizadas segundo sua
complexidade relativa.
Como consequência, conhecida a classe de uma determinada linguagem
pode-se antecipar propriedades fundamentais dessa linguagem, assim
como vislumbrar modelos de implementação mais adequados à sua
realização.
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky
Possui quatro classes distintas de linguagens: tipos 0, 1, 2 e 3
Cada tipo é caracterizado por restrições sobre o formato das produções
α→β definidas pelo conceito geral de gramática.
Tipo 0 – Linguagens Recursivamente Enumeráveis
ou Irrestritas
Tipo 1 – Linguagens Sensíveis ao Contexto
Tipo 2 – Linguagens Livres de Contexto
Tipo 3 – Linguagens Regulares
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky – Linguagens Regulares (Tipo 3)
Tipo de linguagem mais simples da hierarquia.
Qualquer gramática G=(V,T,P,S) geradora de linguagens regulares possui
produções α→β que atendam às seguintes restrições:
•α∈V
• (β
β ∈ T) ou (β
β ∈ V) ou (β
β ∈ T.V) ou (β
β = ɛ), de forma não exclusiva ou
• (β
β ∈ T) ou (β
β ∈ V) ou (β
β ∈ V.T) ou (β
β = ɛ), de forma não exclusiva
Exemplos:
G1=({S,A}, {0,1,2,3}, {S→
→0S, S→
→1S, S→
→A, A→
→2, A→
→3}, S)
→S2, S→
→S3, S→
→A, A→
→1, A→
→0}, S)
G2=({S,A}, {0,1,2,3}, {S→
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky – Linguagens Livres de Contexto (Tipo 2)
Qualquer gramática G=(V,T,P,S) geradora de linguagens livres de
contexto possui produções α→β que atendam às seguintes restrições:
• α ∈ V (só possuem um símbolo não terminal do lado esquerdo)
• β ∈ (V ∪ T)* (qualquer combinação de símbolos do lado direito)
Exemplo:
G3=({S}, {0,1}, {S→
→0S1, S→
→ɛ}, S)
G3 é livre de contexto.
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky – Linguagens Sensíveis ao Contexto (Tipo 1)
Qualquer gramática G=(V,T,P,S) geradora de linguagens sensíveis ao
contexto possui produções α→β que atendam às seguintes restrições:
• α ∈ (V∪
∪T)*.V. (V∪
∪T)*
• β ∈ (V∪
∪T)*
• | β | ≥ | α | (O comprimento da cadeia do lado direito de cada produção
seja no mínimo igual ao comprimento da cadeia do lado esquerdo)
Obs: Não há possibilidade de reduzir o comprimento das formas
sentenciais durante derivações em gramáticas deste tipo.
Exemplo:
G4=({S,X,Y}, {a,b,c}, {S→
→aXb, S→
→aXa, Xa→
→bc, Xb→
→cb}, S)
G4 é sensível ao contexto e não é livre de contexto.
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky – Linguagens Irrestritas (Tipo 0)
Qualquer gramática G=(V,T,P,S) geradora de linguagens sensíveis ao
contexto possui produções α→β que atendam apenas a uma restrição:
• α ∈ (V∪
∪T)*.V. (V∪
∪T)* (lado esquerdo deve conter pelo menos um
símbolo não terminal)
• β ∈ (V∪
∪T)*
Exemplo:
G5=({S,X,Y}, {a,b,c}, {S→
→aXb, S→
→aXa, Xa→
→c, Xb→
→c, X→
→ɛ}, S)
G5 é irrestrita e não é sensível ao contexto (devido às produções Xa→
→c,
Xb→
→c, X→
→ɛ): |α
α| ≥ |β
β|
As gramáticas G1, G2, G3 e G4 são todas irrestritas.
LINGUAGENS E GRAMÁTICAS
Hierarquia de Chomsky – Linguagens, Gramáticas e Reconhecedores
Tipo
Classe de
Linguagem
Modelo de
Gramática
Modelo de Reconhecedor
0
Recursivamente
Enumeráveis
Irrestrita
Máquina de Turing
1
Sensíveis ao
Contexto
Sensível ao
Contexto
Máquina de Turing com Fita
Limitada
2
Livres de
Contexto
Livre de
Contexto
Autômato de Pilha
3
Regulares
Linear (direita
ou esquerda)
Autômato Finito
Obs: As propriedades, características estruturais e modelos de reconhecimento mais adequados para
cada uma das classes da Hierarquia de Chomsky serão estudados mais à frente.
LINGUAGENS E GRAMÁTICAS
Atividades Práticas
• Lista de Exercícios II - Completar
Leituras Recomendadas
• Cap. 2 – Paulo Blauth Menezes
• Seções 2.1 a 2.3 – Marcus Ramos
• Seções 1.7 e 1.8 – Papadimitriou
• Seção 1.5 – Hopcroft & Ullman