Bonifácio Mapero

Danilo Tomás
Fidelto Alberto Inguane
Filipe Lino Lemos
Gerosalina Ernesto Gaita
Hosório Calieque
Issufo Salimo Pereira
Ivo Augusto Calanga

Linguagens Livres de Contexto

(Curso de Engenharia Informática com Habilitações em Telecomunicações)

Universidade Rovuma
Nampula
2023
 Bonifácio Mapero
Danilo Tomás
Fidelto Alberto Inguane
Filipe Lino Lemos
Gerosalina Ernesto Gaita
Hosório Calieque
Issufo Salimo Pereira
Ivo Augusto Calanga

Linguagens Livres de Contexto

Trabalho de carácter avaliativo a ser

apresentado a Faculdade de Engenharias
e Ciências Tecnológicas, na cadeira de
Linguagens Formais e Autómatos,
lecionada pelo: Dr. António Jone.

Universidade Rovuma
Nampula
2023
ÍNDICE
1. INTRODUÇÃO...................................................................................................................3
1.1. Objectivo Geral............................................................................................................4
1.2. Objectivos Específicos.................................................................................................4
1.3. Metodologia.................................................................................................................4
2. LINGUAGENS LIVRES DE CONTEXTO........................................................................5
2.1. Autômatos com Pilha (Pushdown Automata)..............................................................5
2.1.1. A linguagem aceita por um Autômato com Pilha.................................................6
2.1.2. Autômato com Pilha Determinístico.....................................................................6
2.2. Propriedades das Linguagens Livres de Contexto.......................................................7
2.2.1. Lema do Bombeamento........................................................................................7
2.2.2. Operações sobre as Linguagens Livres de Contexto............................................8
2.3. Algoritmo de Early.....................................................................................................10
3. CONCLUSÃO...................................................................................................................11
4. REFERÊNCIAS BIBLIOGRÁFICAS..............................................................................12
 4

1. INTRODUÇÃO

Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma

linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres
de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada
linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto. É
importante distinguir as propriedades da linguagem (propriedades intrínsecas) de propriedades
de uma gramática específica (propriedades extrínsecas).
 5

1.1. Objectivo Geral

 Abordar assuntos relacionados as Linguagens Livres de Contexto a partir do
formalismo operacional ou reconhecedor.
1.2. Objectivos Específicos
 Falar dos autômatos com pilha;
 Identificar as propriedades das Linguagens Livres de Contexto;
 Falar do algoritmo de Early.
1.3. Metodologia

O presente trabalho de pesquisa consistiu em um levantamento bibliográfico de

publicações de artigos científicos retirados em alguns sites na internet.
 6

2. LINGUAGENS LIVRES DE CONTEXTO

As Linguagens Livres de Contextos compreendem uma abordagem mais ampla do que

as Linguagens Regulares tratando, de forma apropriada, as questões de balanceamentos entre
parênteses e blocos de programas. Os seus algoritmos são simples e possuem uma boa
eficiência (Prado, 2011).

Tais linguagens são importantes para definir linguagens de programação.

2.1. Autômatos com Pilha (Pushdown Automata)

Os aceitadores ou reconhecedores das Linguagens Livres de Contexto são os

Autômatos com Pilha. Os Autômatos com Pilha podem ser determinísticos ou não
determinísticos. Os mais usuais são os Autômatos com Pilha não determinísticos. Esses
Autômatos possuem uma memória auxiliar para o processamento da entrada. Essa memória é
definida como sendo uma pilha que não possui limite máximo de armazenamento, portanto,
sendo infinita. Por ser uma pilha o último símbolo gravado na pilha é o primeiro a ser lido
(Prado, 2011).

Enquanto os Autômatos Finitos eram definidos como sendo M = (Q, Σ, δ, q0, F), onde

Q – conjunto finito de estados

Σ – alfabeto de entrada, conjunto finito de símbolos
δ – função de transição ou função programa definido por δ: Q x Σ → Q
q 0 – estado inicial (q 0 ∈ Q)
F – conjunto de estados finais (F ∈ Q)

O Autômato com Pilha pode ser definido como abaixo.

Um Autômato com Pilha Não Determinístico (APND) é definido pela sétupla: M = (Q,
Σ, Γ, δ, q 0, z, F), onde:

Q – conjunto finito de estados

Σ – alfabeto de entrada, conjunto finito de símbolos
Γ – conjunto finito de símbolos, chamado de alfabeto da pilha
δ – função de transição ou função programa definido por
QxΓ∗¿¿
δ :Q x ( Σ ∪ {λ })x ( Γ ∪ { λ })→2
q 0– estado inicial (q 0 ∈ Q )
z – símbolo inicial da pilha (z ∈ Γ)
 7

F – conjunto de estados finais (F ∈ Q)

Exemplo 1

Seja a função de transição δ(q 1, a, b) = {(q 2, cd), (q 3, λ)}

Então:

Se em algum momento, o AP estiver no estado q1, o símbolo lido é a e o símbolo

desempilhado é b (o topo da pilha continha b)
Então: vai para o estado q 2e cd é empilhado
vai para o estado q 3e nada é empilhado

Assume-se que a inserção de um conjunto de símbolos (por exemplo o cd do exemplo

anterior) na pilha é feita símbolo por símbolo, da direita para a esquerda.

2.1.1. A linguagem aceita por um Autômato com Pilha

De acordo com Prado (2011), um Autômato com Pilha Não Determinístico (APND) é
definido pela sétupla:

M = (Q, Σ, Γ, δ, q 0, z, F)

A linguagem aceita por M é o conjunto:

L(M) = {w ∈ Σ*: (q 0, w, z) ⊦*M( p , λ , u), p ∈ F, u ∈ Γ*}

Ou seja, a linguagem aceita por um autômato é o conjunto de todas as cadeias/palavras

que podem colocar o autômato em um estado final quando atingir o fim da string. O conteúdo
da pilha é irrelevante para essa definição.

2.1.2. Autômato com Pilha Determinístico

Prado (2011) afirma que, um Autômato com Pilha Determinístico, M = (Q, Σ, Γ, δ, q0,
z, F) é um Autômato com Pilha Não Determinístico sujeito as seguintes restrições, para todo q
∈ Q, a ∈ Σ ∪ {λ} e b ∈ Γ:

(1) δ (q ,a ,b) contém ao menos um elemento

(2) se δ (q , λ ,b) não é vazio, então δ (q ,c , b) deve ser vazio para todo c ∈ Σ
 8

Exemplo 2

Seja L={ww R∨w ∈{a , b }+} e M = ({q 0,q 1,q 2}, {a,b}, {a,b,z},δ, q 0, z, {q 2}) com as
funções de transição:

δ(q 0,a,a) = {(q 0,aa)}

δ(q 0,b,a) = {(q0,ba)}
δ(q 0,a,b) = {(q 0,ab)}
δ(q 0,b,b) = {(q 0,bb)}
δ(q 0,a,z) = {(q 0,az)}
δ(q 0,b,z) = {(q 0,bz)}
δ(q 0,λ,a) = {(q 1,a)}
δ(q 0,λ,b) = {(q 1,b)}
δ(q 1,a,a) = {(q 1,λ)}
δ(q 1,b,b) = {(q 1,λ)}
δ(q 1,λ,z) = {(q 2,z)}

M é não determinístico, já que δ (q 0 , λ , a) = {(q 1 , a)} e δ (q 0 ,a , a)={(q0 , aa)}≠

vazio ....

L é dita ser uma Linguagem Livre de Contexto Determinística se e somente se existe

um Autômato com Pilha Determinístico M tal que L = L(M).

2.2. Propriedades das Linguagens Livres de Contexto

2.2.1. Lema do Bombeamento

Se L é uma Linguagem Livre de Contexto, então existe uma constante m ≥ 0 tal que
para qualquer palavra w ∈ L com | w | ≥ m, w pode ser decomposta como w = uvxyz com |
vxy | ≤ m, | vy | ≥ 1 tal que uv i xy i z é palavra de L, i ≥ 0 (Prado, 2011).

Exemplo 3

Seja a Linguagem L={an bn c n∨n≥ 0 }.

Aplicando o Lema do Bombeamento, w=uvxyz=ar b r c r com ¿ vxy∨≤ r ,∨vy∨≥ 1 e

para i≥ 0 , uv i xy i z tem de ser uma palavra de L. Supondo que vy possui os símbolos a e c, x
 9

deve conter símbolos b. Só que uv i xy i z não é palavra de L, já que tem desbalanceamento no

número de a, b e c.

2.2.2. Operações sobre as Linguagens Livres de Contexto

Conforme Prado (2011), a Classe das Linguagens Livres de Contexto é fechada para
as operações de União e Concatenação.

Prova - União

Sejam L1 e L2 duas Linguagens Livres de Contexto geradas, respectivamente, pelas

Gramáticas Livres de Contexto G1=(V 1 ,T 1 , S1 , P 1) e G2=(V 2 ,T 2 , S2 , P 2). Considere
L3=L1 ∪ L2, então G3=(V 3 ,T 3 , S 3 , P3 ) (S2 ∉V 1 ∪V 2) tal que

V 3=V 1 ∪ V 2 ∪ {S 3 },
T 3=T 1 ∪ T 2 e
P3=P1 ∪ P2 ∪ {S 3 → S1|S 2 }

Suponha w ∈ L1, então w ∈ L3, já que S3⇒ S1⇒* w.

Suponha v ∈ L2, então v ∈ L3, já que S3⇒ S2⇒* v.
Portanto L3= L(G3) é uma Linguagem Livre de Contexto.

Pode-se provar também usando Autômatos com Pilha Não Determinísticos. Sejam L1
e L2 duas Linguagens Livres de Contexto aceitas, respectivamente, pelos Autômatos com
Pilha Não Determinísticos
M 1=(Q1 , Σ 1 , Γ 1 , δ 1 , q 01 , z1 , F1 ) e M 2=(Q2 , Σ 2 , Γ 2 , δ 2 , q02 , z 2 , F 2 ). Seja M 3=( Q3 , Σ 3 , Γ 3 , δ 3 ,q 03 , z 3 , F 3 )com q
, tal que

Q3=Q1 ∪ Q2 ∪{q 03 }
Σ 3=Σ 1 ∪ Σ 2 ,
Γ 3 =Γ 1 ∪ Γ 2 ∪ { z3 }
F 3=F1 ∪ F1

Dessa forma, M 3 reconhece L1 ∪ L2.

Prova – Concatenação

Retomando a prova para União acima usando Gramática Livre de Contexto, pode-se
definir G4 =(V 4 ,T 4 , S 4 , P4 ) (S 4 ∉ V 1 ∪V 2 ) tal que
 10

V 4 =V 1 ∪ V 2 ∪ {S 4 },
T 4=T 1 ∪ T 2 e
P4 =P1 ∪ P2 ∪ {S 4 → S1|S 2 }

Então L(G4 ) = L(G1)L(G2) que possui como prefixo uma cadeia de L1 e como sufixo
uma cadeia de L2.

Se construir G5= (V 5, T 5, S5, P5) ( S5∉ V 1) tal que

V 5= V 1∪ { S5, },
T 5= T 1
P5= P1∪ { S5 → S1 S 5|λ}

Então L(G5) = L(G1)*

Prado (2011) afirma ainda que, a Classe das Linguagens Livres de Contexto não é
fechada para as operações de Intersecção e Complemento.

Prova – Intersecção

Façamos a prova com um contra-exemplo.

Considere as Linguagens Livres de Contexto L1= { a n b n cm | n ≥ 0, m ≥ 0} e L2 = {

a b c | n ≥ 0, m ≥ 0}. Seja L = L1 ∩ L2 = {a b c | n ≥ 0} não é uma Linguagem Livre de
n m m n n n

Contexto.

Prova – Complemento

Sabe-se que L1 ∩ L2=L1 ∪ L2 . Como para a intersecção a operação não é fechada,

então também não o é para o complemento.

Seja L1 uma Linguagem Livre de Contexto e L2 uma Linguagem Regular. Então L1 ∩

L2 é uma Linguagem Livre de Contexto.

Prova

Seja M 1=(Q , Σ , Γ , δ 1 , q0 , z , F1 ) um Autômato com Pilha Não Determinístico que

aceita L1 e M 1=(Q , Σ , Γ , δ 2 , p 0 , z , F 2) um Autômato Finito Determinístico que aceita L2.

Seja M 3=(Q3 , Σ , Γ , δ 3 , q03 , z , F3 ) um Autômato com Pilha Não Determinístico que

aceita L = L1 ∩ L2
 11

Onde Q3 = Q x P,

q 03 = (q 01, p0),

F 3 = F 1 x F 2,

δ 3 é definido tal que ((q k , p1), x) ∈ δ 3 ((qi , p j ), a ,b), se e somente se (q k ,x) ∈ δ 1 (q i

,a,b) e δ 2 ( p j,a) = p1.

se a = λ, então p j= p1.

Assim uma cadeia é aceita por M 3 se e somente se ela é aceita por M 1 e por M 2 ou
seja, se ela está em L(M 1)∩ L(M 2)=L1 ∩ L2.

Exemplo 4

A linguagem L = {a n b n | n ≥ 0, n ≠ 100} é uma Linguagem Livre de Contexto.

Seja L1 = {a n b n | n ≥ 0} e L2 = {a 100 b100}, onde L1 é uma Linguagem Livre de

Contexto e L2 é uma Linguagem Regular, L2 também é Regular. Então L1 ∩ L2 = L é Livre
de Contexto.

2.3. Algoritmo de Early

Segundo Mari (sd), o algoritmo de Early foi desenvolvido em 1968, possivelmente o

mais rápido algoritmo para LLC. tempo de processamento proporcional a:

3
 em geral: |w|
2
 gramáticas não-ambíguas:|w|
 muitas gramáticas de interesse prático: |w|

O algoritmo de análise gramatical Earley é um tipo de programa que subdivide uma

entrada (input) para que um outro possa atuar sobre ela mais comumente usado em linguística
computacional, nomeado após seu inventor, Jay Earley. O algoritmo faz uso de programação
dinâmica (Wikipédia, 2023).

Os analisadores gramaticais Earley são interessantes porque podem analisar todas as

linguagens livre de contexto. O algoritmo Earley tem tempo de execução O (n ³) (onde n é o
comprimento da cadeia de caracteres analisada), no caso geral, tempo quadrático (O(n ²))
para gramáticas não ambígua, e tempo linear para quase toda as gramáticas LR(k ). Seu
 12

desempenho é relativamente bom quando as regras são escritas de forma recursiva

(Wikipédia, 2023).

3. CONCLUSÃO

Chegando ao final do trabalho pudemos concluir que, um autômato com pilha é um

autómato com uma memória auxiliar em forma de pilha, e eles podem ser determinísticos ou
não determinísticos. Os mais usuais são os Autômatos com Pilha não determinísticos.

Nota-se que as Linguagens Livres de Contexto têm como propriedades o lema de

bombeamento. As Linguagens Livres de Contexto obedecem as operações de união e
concatenação, e também não é fechada para as operações de Intersecção e Complemento.

Por fim, conclui-se que o algoritmo de análise gramatical Early é um tipo de programa
que subdivide uma entrada (input) para que um outro possa atuar sobre ela mais comumente
usado em linguística computacional. Os analisadores gramaticais Earley são interessantes
porque podem analisar todas as linguagens livre de contexto.
 13

4. REFERÊNCIAS BIBLIOGRÁFICAS

1. Mari, J. F. (sd). Reconhecimento das LLC - Algoritmo de Earley. Rio Paranaíba.

2. Prado, S. d. (2011). Linguagens Livres de Contexto . Brasil.

3. Wikipédia. (09 de Junho de 2023). Algoritmo Earley. Obtido de Wikipedia:

https://pt.wikipedia.org/w/index.php?title=Algoritmo_Earley&oldid=54628321