Linguagens Livres de Contexto

Prévia do material em texto

60
Unidade II
Unidade II
5 LINGUAGENS LIVRES DE CONTEXTO: PARTE 1
As linguagens livres de contexto são geradas por gramáticas livres de contexto.
A gramática livre de contexto foi definida por Chomsky (1956). Trata-se de um dispositivo mais 
poderoso que aquele das linguagens regulares, visto que apresenta regras que permitem expressar como 
os elementos de uma forma sentencial se organizam em grupos hierárquicos complexos. 
De fato, considere o seguinte exemplo:
A limpava menina casa a vassoura uma com.
Trata-se de uma sentença não gramatical, dado que os seus elementos constituintes não estão 
agrupados corretamente. 
A organização adequada dos elementos da frase é apresentada na figura a seguir.
a menina limpava a casa com uma vassoura
a menina limpava a casa com uma vassoura
a menina limpava a casa com uma vassoura
a casa com uma vassoura
uma vassoura
Figura 29 
As gramáticas livres de contexto representam um importante formalismo para o processamento das 
linguagens naturais, bem como das artificiais, em particular das linguagens de programação. 
O estudo das linguagens livres de contexto é aplicado no projeto e na implementação do analisador 
sintático, módulo funcional do compilador.
Exemplo: apresenta-se uma gramática livre de contexto para uma pequena linguagem de 
programação (Sebesta, 2003).
G = (V, S, P, <programa>)
61
LINGUAGENS FORMAIS E AUTÔMATOS
Onde:
• V = {<programa>, <lista_inst>, <inst>, <comando>, <var>, <expressão>}
• S = {A, B, C, +, -, begin, end}
• <programa> é o símbolo inicial
• P = {<programa> → begin <lista_inst> end
 <lista_inst> → <inst> | <commando>; <lista_inst>
 <inst> → <var> = <expressão>
 <var> → A | B | C
 <expressão> → <var> + <var> | <var> - <var> | <var>
5.1 Gramática livre de contexto: dispositivo gerador de uma linguagem livre 
de contexto
Seja G = (V, S, P, S). Diz-se que G é livre de contexto, se as produções apresentarem o seguinte padrão: 
A→ b, onde A ∈ V e b ∈ (V ∪ T)*
A expressão acima indica que no lado esquerdo da produção deve existir um e, apenas um, símbolo 
não terminal e, no lado direito da produção, podem figurar quaisquer cadeias de símbolos, sejam 
terminais, não terminais e até mesmo isoladamente, a cadeia vazia. 
Uma linguagem L definida sobre um alfabeto S é livre de contexto se pode ser gerada por uma 
gramática livre de contexto.
A seguir são apresentados alguns exemplos de Gramáticas Livres de Contexto. Em cada um 
destes exemplos observe o formato das produções: no lado esquerdo da produção figura um e, 
apenas um, símbolo não terminal e, no lado direito, quaisquer sequências de símbolos terminais e 
não terminais.
Exemplo: é conhecido o duplo balanceamento dos símbolos “(“ e “)”, nas expressões 
lógico-aritméticas das linguagens de programação, bem como o duplo balanceamento dos símbolos 
“{“ e “}” na estruturação de blocos de comandos. Considere a seguinte linguagem L com duplo 
balanceamento e definida a partir do alfabeto S: 
S = {a, b} e L = {w | w =an bn, n ≥ 0}
A gramática G, geradora, é:
G = (V,S, P, S) = ({S}, {a,b}, P, S)
P = {S → aSb | e}
62
Unidade II
Confira: 
S ⇒ e
S ⇒aSb ⇒ aeb = ab
S ⇒aSb ⇒ aaSbb ⇒ = aaebb = aabb
S ⇒aSb ⇒ aaSbb ⇒aaaSbbb ⇒ aaaebbb = aaabbb 
Exemplo: considere a gramática G = (V, S, P, S), tal que:
• V = {S, A, O, Y}
• S = {x, y, z, +, *, -, /}
• P = {S → (AOA)
 A → Y | S
 O → + | - | * | /
 Y→ a|b|c}
Tem-se que: 
S ⇒ (AOA) ⇒ (YOA) ⇒ (aOA) ⇒ (a*A) ⇒ (a*S) ⇒ (a*(AOA)) ⇒ (a*(YOA)) ⇒ (a*(b OA)) ⇒ (a*(b OA)) ⇒ 
(a*(b /A)) ⇒ (a*(b /Y)) ⇒ (a*(b /c))
Observe que há linguagens livres de contexto que não são regulares. Por outro lado, todas as 
linguagens regulares são livres de contexto.
Exemplo: as regras 1 a 6 pertencem ao conjunto de produções P da gramática 
G = ({E, T, F}, {id, , +, *, (, ) }, P, E)
1: E à E + T 
2: E à T
3: T à T * F 
4: T à F
5: F à (E) 
6: F à id
63
LINGUAGENS FORMAIS E AUTÔMATOS
Pede-se:
a) Mostre que G gera a cadeia (id + id * id) * (id + id)
 G ⇒ T⇒ T * F ⇒F * F ⇒ (E) * F ⇒ (E + T) * F ⇒ (T * F + T) * F ⇒ 
 (F * F + T) * F ⇒ (id * id + T) * F ⇒ (id * id + F) * F ⇒ (id * id + id) * F ⇒
 (id* id + id) * (E) ⇒(id * id + id) * (E + T) ⇒ (id *id + id) * (T + T) ⇒ 
 ⇒ (id *id + id) * (F + T) ⇒ (id *id + id) * (id + T) ⇒ (id *id + id) * (id + F) ⇒
 ⇒ (id *id + id) * (id + id) 
b) Por que essa gramática é classificada como livre de contexto?
 Porque as produções são da forma: A → a, onde A ∈ V e a ∈ (V ∪ T)*
 V = conjunto dos símbolos não terminais e T = conjunto dos símbolos terminais.
Árvores de derivação
Uma árvore de derivação é uma representação gráfica de uma derivação que filtra a ordem na qual 
as produções são aplicadas para substituir não terminais. 
Formalmente, uma árvore de derivação é um sistema de representação de sequências de derivações 
em que uma gramática livre de contexto G = (V, S, P, S) consiste em um grafo orientado e ordenado, 
acíclico, com as seguintes propriedades: 
1. Todo nó é rotulado com um elemento de (V ∪ S ∪ e).
2. O rótulo da raiz é S, o símbolo inicial da gramática.
3. Os rótulos dos nós internos são elementos de V, o conjunto dos símbolos não terminais da gramática.
4. Se um nó tem rótulo A, e A1, A2, ..., An são descendentes diretos de A, ordenados da esquerda para 
a direita, então existe uma produção da gramática da forma A → A1A2.... An.
5. Se um nó tem um rótulo e, então este nó deve ser simultaneamente uma folha e descendente 
único de seu ancestral direto.
Exemplo: seja a gramática G = ({S, B}, {a, b}, P, S), onde P= {S → aB | aSB; B→ b}.
64
Unidade II
A derivação para a cadeia aabb é: 
S ⇒aSB⇒aaBB ⇒aabB⇒aabb
A árvore de derivação dessa cadeia é representada na figura a seguir:
S
S
B
B
a
a
b b
Figura 30 – Exemplo de árvore de derivação
Gramáticas ambíguas
Uma gramática livre de contexto é ambígua se existir uma palavra que possua duas ou mais árvores 
de derivação.
Exemplo: considere-se a gramática G = ({E}, {x, +, *}, P, E), onde P = {E → E + E | E * E | x}.
A cadeia x + x * x é gerada pela gramática G.
Tem-se que:
E ⇒ E + E ⇒ E + E ⇒ x + E ⇒ x + E * E ⇒ x + x * E ⇒ x + x * x
A árvore de derivação correspondente é:
E
+
*
E
x
E
E
x
E
x
Figura 31 – Árvore de derivação para a sentença x+x*x
65
LINGUAGENS FORMAIS E AUTÔMATOS
Por outro lado, a mesma sentença, x + x * x pode ser derivada como se segue: 
E ⇒ E * E ⇒ E + E * E ⇒ x + E * E ⇒ x + x * E ⇒ x + x * E ⇒ x + x * x
A árvore de derivação correspondente é:
E
*
+
E
x
E
E
x
E
x
Figura 32 – Árvore de derivação para a sentença x+x*x
Exemplo: mostre que a seguinte gramática G = (V, T, P, S) é ambígua.
V = {S}
T = {(, )}
P = {S → SS | e | (S) }
De fato, a palavra ( ) apresenta as seguintes derivações distintas:
(1) S ⇒SS⇒(S) S ⇒ ( ) S ⇒ ( )
(2) S ⇒SS⇒S (S) ⇒ S ( ) ⇒ ( )
Exemplo: considere a seguinte gramática livre de contexto:
G =({S}, {a, b}, P, S), onde:
P = {S→ SS | aSa | bSb |e}
Essa gramática é ambígua porque existe pelo menos uma palavra que apresenta mais de uma árvore 
de derivação possível. Verifique, como exercício, as árvores de derivação para as palavras aaaa e bbbb.
Uma linguagem é uma linguagem inerentemente ambígua se qualquer gramática livre de contexto 
que a define é ambígua.
66
Unidade II
6 AUTÔMATOS DE PILHA: DISPOSITIVOS RECONHECEDORES DE 
LINGUAGENS LIVRES DE CONTEXTO
As linguagens que são livres de contexto no seu sentido estrito não podem ser reconhecidas por um 
autômato finito.
Considere-se, como exemplo, a linguagem L definida sobre o alfabeto S = {a, b}, de forma que:
L = {w | w é um palíndromo}
Um dispositivo reconhecedor dessa linguagem deveria inicialmente ler a primeira metade da 
cadeia, armazená-la em uma pilha, de forma que, ao processar a segunda metade da cadeia, 
pudesse compará-la, símbolo a símbolo, com a cadeia recém-armazenada. Naturalmente, 
o autômato finito não poderia processar essa linguagem, pois se trata de um dispositivo sem 
memória auxiliarorganizada em pilha.
O autômato finito também não pode processar as linguagens com duplo balanceamento. Seja a 
linguagem L = {an bn | n ≥ 1}. Os autômatos finitos não têm como identificar o número de ocorrências 
do símbolo a na cadeia de entrada e comparar com o número de ocorrências do símbolo b.
O dispositivo reconhecedor das linguagens livres de contexto é o autômato de pilha não 
determinístico. Cumpre observar que os autômatos finitos determinísticos são capazes de reconhecer 
apenas um subconjunto das linguagens livres de contexto. 
Um autômato com pilha não determinístico apresenta os seguintes componentes:
Fita de entrada 
Análoga àquela do autômato finito, sua função é armazenar a cadeia a ser analisada. A fita de 
entrada é também dividida em células, cujo número é igual ao número de símbolos da cadeia de entrada. 
Dispõe de um cursor, que se movimenta apenas da esquerda para a direita. Os símbolos presentes na 
fita de entrada não podem ser alterados, ou seja, a operação que se efetua sobre a mesma é apenas de 
leitura, e não de gravação.
Unidade de controle 
Possui um número finito e predefinido de estados. As transições de estados do autômato de pilha se 
fazem mediante as especificações previstas por uma relação de transição. Essa relação associa o estado 
corrente do autômato a um novo estado. Essa mudança de estado é especificada a partir da leitura 
do símbolo corrente da cadeia de entrada, ou pode ser em vazio; pode ser determinada pela leitura e 
remoção de um símbolo no topo da pilha e geralmente implica a inserção de um novo símbolo na pilha. 
Em outras palavras, os símbolos a serem lidos da cadeia de entrada, a serem lidos do topo da pilha e a 
serem gravados nessa estrutura de dados, podem coincidir com a cadeia vazia, e. 
67
LINGUAGENS FORMAIS E AUTÔMATOS
Memória auxiliar organizada em pilha 
Os símbolos a serem consultados, removidos e armazenados na pilha, em geral, não coincidem com 
os símbolos do alfabeto de entrada. Os símbolos da pilha apresentam um alfabeto próprio.
a
A
AMáquina de
estados
a b b
Reconhecimento: 
aceita/rejeita
Pilha
Figura 33 – Autômato de pilha. Conteúdo da pilha após a leituras da subcadeia aa 
A partir da ilustração anterior é possível inferir que, uma vez lidos os dois primeiros símbolos a”, 
foram inseridos dois símbolos A na pilha. 
Considere a figura seguinte:
a
Máquina de
estados
a b b
Reconhecimento: 
aceita/rejeita
Pilha
Figura 34 – Autômato de pilha: conteúdo da pilha após as leituras da subcadeia aabb 
Pode-se inferir que, após a leitura dos dois símbolos b, foram removidos os símbolos A, 
recém-inseridos na pilha. Através da inserção e remoção de elementos na pilha, é possível constar 
que a cadeia analisada apresenta de fato o balanceamento entre os símbolos a e b. 
A figura a seguir apresenta uma transição entre dois estados de um autômato de pilha. Observe 
que as transições são rotuladas por uma tripla. O primeiro elemento da tripla é o elemento a 
ser lido da cadeia de entrada. O segundo elemento coincide com o símbolo a ser consultado e 
removido do topo da pilha e finalmente o terceiro elemento coincide com o símbolo a ser inserido 
na pilha após a transição.
68
Unidade II
p q
(a, X, Y)
Figura 35 - Transição de um autômato de pilha
Representação algébrica do autômato de pilha 
Formalmente, um autômato de pilha pode ser definido como uma sêxtupla M:
M = (Q, S, G, g, q0, F)
Onde:
• Q é um conjunto finito de estados;
• S é um alfabeto (finito e não vazio) de entrada;
• G é um alfabeto (finito e não vazio) de pilha;
• g é uma relação de transição g: (Q × (S ∪ {e}) × G*) × (Q × G*);
• q0 é o estado inicial;
• F ⊆ Q é o conjunto de estados finais.
Os dispositivos que fazem uso de pilha podem operar segundo uma das seguintes possibilidades: 
• Pilha Stack: além das operações de empilhamento e desempilhamento de elementos no topo 
da pilha (push e pop), permite que os demais elementos da mesma sejam endereçados diretamente, 
somente para consulta;
• Pilha Pushdown: permite o acesso apenas ao elemento armazenado no topo da pilha, através 
das operações de empilhamento e desempilhamento (push e pop). Não permite o endereçamento dos 
demais elementos da pilha.
A configuração de um autômato de pilha é definida pelo seu estado corrente, pela parte da cadeia 
de entrada ainda não analisada e pelo conteúdo da pilha. A configuração inicial de um autômato de 
pilha é aquela em que o autômato se encontra no estado inicial q0, o cursor se encontra posicionado 
sob a célula mais à esquerda da fita de entrada e o conteúdo da pilha é Z0. 
Exemplo: considere o autômato de pilha M = (Q, S, G, g, q0, F), tal que:
• Conjunto finito de estados Q = {q0, qf};
69
LINGUAGENS FORMAIS E AUTÔMATOS
• Conjunto de estados finais F = {qf};
• Alfabeto (finito e não vazio) de entrada ∑ = {a, b};
• O alfabeto de pilha é G = {a};
• A função de transição é dada por:
 g(q0, a, e) = (q0, a)
 g(q0, b, e) = (q0,a)
 g(q0, a, e) = (qf, e)
 g(qf, a, a) = (qf, e)
 g(qf, b, a) = (qf, e)
A representação gráfica do autômato de pilha M é apresentada a seguir:
q0 qf
a
(a, e, a)
(b, e, a)
(a, a, e)
(b, a, e)
Figura 36 – Exemplo de um autômato de pilha
O reconhecimento da cadeia de entrada aab pode ser descrito como na figura seguinte:
a a b a a b a a b a a b
⇑ → ⇑ → ⇑ → ⇑
q0 a qf a qf a qf a
 Pilha Pilha Pilha Pilha
Figura 37 
Exemplo: considere a seguinte gramática G = (V, S, P, S), com:
• S = {a, b, c} 
• V = {S}
• P = {S →a S a | b S b | c) 
70
Unidade II
A linguagem gerada pela gramática G é 
L(G) = {x = wcwR | x ∈ {a, b}*} 
O autômato que aceita essa linguagem é:
M = (Q, S, G, g, p, {q})
Tal que:
• Conjunto finito de estados Q = {p, q};
• Alfabeto (finito e não vazio) de entrada S = {a, b, c};
• O alfabeto de pilha é G= {a, S, b};
• O estado inicial é p;
• F ⊆ Q é o conjunto de estados finais, com F = {q}.
• A relação de transição g é dada por:
 g = {((p, e, e), (q, S))}, 
 ((q, e, S), (q, aSa)), 
 ((q, e, S), (q, bSb)), 
 ((q, e, S), (q,c)), 
 ((q, a, a), (q, e)),
 ((q, b, b), (q,e)), 
 ((q, c, c), (q,e))}
A seguir, ilustra-se a sequência de movimentos do autômato, de sua configuração inicial até sua 
configuração final, para a cadeia abbcbba, através da tabela a seguir:
Tabela 10 
Estado 
corrente
Símbolo corrente na 
cadeia de entrada 
(em negrito)
Topo da pilha
(em negrito) Transição Próximo
estado
p abbcbba e ((p, e, e), (q, S)) q
q abbcbba$ S ((q,e,S), (q,aSa)) q
q abbcbba aSa ((q,a,a), (q,e)) q
q  bbcbba  Sa ((q,e,S), (q,bSb)) q
71
LINGUAGENS FORMAIS E AUTÔMATOS
Estado 
corrente
Símbolo corrente na 
cadeia de entrada 
(em negrito)
Topo da pilha
(em negrito) Transição Próximo
estado
q  bbcbba  bSba ((q,b,b), (q,e)) q
q   bcbba  Sba ((q,e,S), (q,bSb)) q
q   bcbba  bSbba ((q,b,b), (q,e)) q
q    cbba  Sbba ((q,e,S), (q,c)) q
q    cbba  cbba ((q,c,c), (q,e)) q
q     bba    bba ((q,b,b), (q,e)) q
q      ba      ba ((q,b,b), (q,e)) q
q       a       a ((q,a,a), (q,e)) q
q        e        e q
Teoremas sobre as linguagens livres de contexto
Teorema: se L é uma linguagem livre do contexto, então existe M, autômato com pilha que aceita L(M).
Corolário: autômato com pilha × número de estados.
Se L é uma linguagem livre do contexto, então:
a) existe M, autômato com pilha, com controle de aceitação por estados finais, com somente três 
estados, tal que L = L(M).
b) existe M, autômato com pilha, com controle de aceitação por pilha vazia, com somente um estado, 
tal que L = L(M).
Teorema: para qualquer linguagem livre de contexto, existe um autômato com pilha que sempre 
para, qualquer que seja a entrada. 
Teorema: se L é aceita por um autômato de pilha, então L é linguagem livre de contexto.
6.1 O lema do bombeamento para linguagens livres de contexto
Assim, como para as linguagens regulares, enuncia-se o lema do bombeamento para as linguagens 
livres de contexto, o qual permite que as propriedades das mesmas sejam analisadas. 
Lema dobombeamento 
Se L é uma linguagem livre de contexto, então existe uma constante n tal que, para qualquer 
palavra w de L, onde |w| ≥ n, w pode ser definida como w = uxvyz, onde |xvy| ≤ n, |xy| ≥ 1 e, para 
todo i ≥ 0, u xi v yiz é palavra de L. 
72
Unidade II
Exemplo de aplicação
Questão 1. O conjunto das linguagens livres de contexto é fechado para a operação de união, mas 
não o é para as operações de intersecção ou complemento. Verifique se as seguintes linguagens são 
livres de contexto. 
L(w) = { w = am bn | m ≠ n }
L(w) = {a, b}* – {an bn | n ≥ 0 }
L(w) = {an bn cn | n ≥ 0 }
Questão 2. Para cada uma das linguagens a seguir, construa um autômato de pilha. 
L = {w | w = an bn cm, n > 0, m > 0}
L = {w | w = an bm cn dl, n > 0, m > 0, l > 0}
L = {w | w = an bn cm dm, n > 0, m > 0}
7 ALGORITMOS DE ANÁLISE SINTÁTICA
Um analisador sintático de uma linguagem gerada por uma gramática verifica se é possível construir 
uma árvore de derivação para uma dada cadeia de entrada.
Segundo Aho et al. (2008), existem três estratégias gerais de análise sintática para o processamento 
de gramáticas: universal, descendente e ascendente.
Os métodos de análise universal podem analisar qualquer gramática, no entanto, são muito 
ineficientes. São exemplos desses algoritmos o algoritmo de Cocke-Younger-Kasami e o de Early. 
Os compiladores, em geral, empregam, em vez dos métodos universais, aqueles conhecidos como 
determinísticos ascendentes e determinísticos descendentes.
Os analisadores determinísticos descendentes constroem a árvore de derivação para a palavra de 
entrada (a ser reconhecida) a partir da raiz (símbolo inicial da gramática), gerando os ramos em direção 
às folhas (símbolos terminais que compõem a palavra).
Naturalmente, os analisadores ascendentes constroem a árvore de derivação das folhas para a raiz.
Os métodos ascendentes e descendentes mais eficientes funcionam apenas para subclasses de 
gramáticas, e ambos analisam a cadeia de entrada da esquerda para a direita.
73
LINGUAGENS FORMAIS E AUTÔMATOS
A seguir são apresentados os algoritmos de Cocke-Younger-Kasami e são feitas considerações sobre 
algoritmos determinísticos ascendentes.
Algoritmo de Cocke Younger Kasumi
O algoritmo de Cocke-Younger-Kasami foi proposto em 1965. Trata-se de um algoritmo ascendente 
e emprega a forma normal de Chomsky. 
Uma gramática livre de contexto é dita na forma normal de Chomsky se todas as suas produções 
são da forma:
A → BC ou A → a
Onde A, B, C ∈ V e a ∈ S. 
Seja G = (V, S, P, S) uma gramática na forma normal de Chomsky, onde S = {a1, a2, ... an}, e suponha 
w = a1a2...an uma entrada a ser verificada. O algoritmo emprega uma tabela triangular, conforme 
ilustra a figura seguinte:
 
   
     
       
a1 a2 ... an
S
r
Figura 38 - Tabela triangular para os algoritmos de Cocke-Younger-Kasami
O algoritmo de Cocke-Younger-Kasami (CYK) é composto pelas etapas apresentadas a seguir. 
Empregar-se-á o símbolo Xrs para nomear as células da tabela triangular de derivação, a saber: o índice 
“r” indica a coluna e o índice “s” diz respeito à linha.
a) Inicialmente, investigam-se todas as regras que geram os símbolos terminais, ou seja, regras da 
forma: A → a. Para cada regra r que apresenta esse padrão, deve-se preencher cada célula Xr1 
(da primeira linha) com o símbolo não terminal A.
b) A partir da segunda linha até a última linha n, cada célula de cada coluna deve ser preenchida. 
Lembrando que a tabela é triangular, deve-se variar o contador de linhas s, de 2 a n, e o contador 
de colunas r de 1 até n-s+1. O preenchimento de cada célula Xrs se faz mediante a investigação de 
todas as regras da forma: A → BC. O objetivo dessa etapa é o de identificar todos os não terminais 
que serão armazenados na célula Xrs que gerem a subcadeia arar+1...as. Assim, A ∈ Xrs, se existe 
uma regra A → BC, tal que B se apresente na mesma coluna r, situado em linhas abaixo da linha 
corrente s, e o não terminal C se apresente nas colunas à direita da coluna r, nas linhas abaixo da 
74
Unidade II
linha s. Assim sendo, esses não terminais da célula Xrs são obtidos através do conjunto de iterações 
descrito pelo seguinte pseudocódigo:
Xrs = ∅; Para k variando de 1 até s-1, faça:
Xrs = Xrs ∪ {A | A → BC ∈ P, B ∈ Xrk e C ∈ X(r+k)(s-k)}
A condição de aceitação da entrada implica o símbolo inicial da gramática (raiz da árvore de derivação 
de toda palavra) se apresentar na célula X1n. Nessa situação, a entrada é aceita pelo algoritmo.
Exemplo: seja a gramática G = (V, S, P, S), tal que:
• V = {S, A}
• S = {a, b}
• P = {S → AB; S → b; A → a; B → S A}
Pede-se verificar se a cadeia aabaa é gerada pela gramática G, empregando-se o algoritmo de 
Cocke-Younger-Kasami.
Inicialmente, constrói-se uma tabela triangular. Para melhor compreensão do algoritmo, apresentam-se 
as células da tabela triangular nomeadas:
X15
X14 X24
X13 X23 X33
X12 X22 X32 X42
X11 X21 X31 X41 X51
a a b a a
Figura 39 – Tabela triangular com células nomeadas
A primeira etapa do algoritmo diz respeito às produções da forma A → a e ao preenchimento das 
células X11, X21, X31, X41 e X51. 
O preenchimento das células prossegue na seguinte ordem: X12, X22, X32 e X42, sucedidas pelas células 
X13, X23 e X33, X14, X24 e, finalmente, X15. 
A fim de melhor ilustrar a ordem do preenchimento das células, apresenta-se a tabela a seguir, onde 
se elencam os valores de r, s e k durante as diversas iterações previstas no algoritmo. Apresentam-se 
também o conteúdo das células Xrk, Xr+k, s-k e o conteúdo resultante da célula Xrs.
75
LINGUAGENS FORMAIS E AUTÔMATOS
Tabela 11 
N = 5 (comprimento da cadeia de entrada)
s r k Xrk Xr+k, s-k Xrs
2 1 1 X11 =A X21 = A X12 = -
2 1 X21 - X31 = - X22= -
3 1 X31 = S X41 = A X32= B
4 1 X41 = A X51 = A X42 = - 
3 1 1 X11=A X22= -
X13 = -
2 X12=- X31 = S
2 1 X21 = A X32 = B
X23 = S
2 X22 = - X41 = A
3 1 X31 = S X42 = -
X33 = -
2 X32 = B X51 = A
4 1 1 X11 = A X23 = S
X14 -2 X12 - X32 = B
3 X13 = - X41 = A
2 1 X21 = A X33 = -
X24 = B2 X22 = - X42 = -
3 X23 = S X51 = A
5 1 1 X11 = A X24= B
X15 = S
2 X12 = - X33 = -
3 X13 = - X42 - 
4 X14 = - X51 = A
A seguir, apresenta-se a sequência de preenchimento das células na tabela triangular. 
1. Preenchimento das células: X11, X21,...X51.
X15
X14 X24
 X13  X23  X33
     
A A S A A
a a b a a
Figura 40 
76
Unidade II
2. Preenchimento das células X12, X22, X32 e X42.
X15
X14 X24
 X13  X23  X33
    B  
A A S A A
a a b a a
Figura 41 
3. Preenchimento das células X13, X23 e X33.
X15
X14 X24
  S  
    B  
A A S A A
a a b a a
Figura 42 
4. Preenchimento das células X14, X24 e X15.
S
  B
   S  
    B  
A A S A A
a a b a a
Figura 43 
Como o símbolo inicial ocorre na última célula (X15) calculada, infere-se que a cadeia aabaa é gerada 
pela gramática G.
Analisador sintático ascendente
Os analisadores sintáticos ascendentes analisam a cadeia de entrada da esquerda para a direita e 
constroem a árvore de derivação das folhas para a raiz. Pode-se pensar na análise ascendente como o 
processo de “reduzir” uma cadeia w para o símbolo inicial da gramática.
77
LINGUAGENS FORMAIS E AUTÔMATOS
Os analisadores sintáticos ascendentes podem ser construídos através de diferentes métodos.
Constrói-se um autômato de pilha como se segue:
Seja G = (V, S, P, S) uma gramática livre de contexto e seja o autômato de pilha M = (Q, S, g, q0, F, G), 
onde Q = {q0, qf}, G = V e F = {qf}.
 Tem-se que g, a relação de transição, é obtido como se segue:
• g(p, a, e) = (q0, a), para cada a ∈ ∑. Observe-se que se trata de uma transição de inserção de 
símbolo na pilha.
• g(p, e, aR) = (q0, A), para cada A → a. Trata-se da substituição do lado direito da regra pelo lado 
esquerdo. Encontra-se na pilha o reverso da forma sentencial a.
• g(p, e, S) = (qf, e). Observe-se que se trata de uma transição com remoção de símbolo da pilha.
Exemplo: considerem as seguintes regras:
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T →F
(5) F → (E)
(6) F → x
O autômato de pilha pode ser obtido como se segue:
(g0) g(q0, a, e) = (q0, a), para cada a ∈ ∑
(g1) g(q0, e, T+E) = (q0, E)
(g2) g(q0, e,T) = (q0, E)
(g3) g(q0, e, F*T) = (q0, T)
(g4) g(q0, e, F) = (q0, T)
(g5) g(q0, e, )E( ) = (q0, F)
(g6) g(q0, e, x) = (q0, F)
(g7) g(q0, e, E) = (qf, e)
78
Unidade II
Pode-se verificar que a cadeia de entrada x*x + x é aceita pelo autômato M projetado:
Tabela 12 
Etapa Estado Entrada Pilha Transição
Usada Regra
0 q0 x*x + x e
1 q0 *x+x x g0
2 q0 *x+x F g6 6 :F→x
3 q0 *x+x T g4 4 :T → F
4 q0 x+x *T g0
5 q0 +x x*T g0
6 q0 +x F*T g6 6: F→x
7 q0 +x T g3 3: T → T * F
8 q0 +x E g2 2: E → T
8 q0 x +E g0
9 q0 e x+E g0
10 q0 e F + E g6 6 F→x
11 q0 e T + E g4 4 T → F
12 q0 e E g1 1 E → E + T
13 qf e e g7
Observe que a seguinte árvore de derivação foi gerada para a cadeia x*x + x.
E
E
T
*T
x
F
F
x
+ T
F
x
Figura 44 - Árvore de derivação para a sentença x*x+x
É possível perceber que o autômato projetado é não determinístico.
Os compiladores “de produção”, ou seja, aqueles presentes nos ambientes de desenvolvimento 
disponíveis no mercado, devem empregar algoritmos determinísticos.
79
LINGUAGENS FORMAIS E AUTÔMATOS
A seguir, apresenta-se a estrutura de um autômato de análise sintática LR (Aho et al., 2008):
Algoritmo de 
análise
ba ...... c $
Ação Transição
X
Y
...
$
Saída
Figura 45 – Estrutura de um autômato de análise sintática LR
O algoritmo de análise emprega uma tabela de análise que apresenta linhas que se referem ao estado 
do processamento de uma cadeia de entrada e colunas de dois tipos: referentes a ações e referentes 
a transições.
As colunas referentes às ações são associadas aos símbolos terminais da gramática passíveis de 
serem encontrados na cadeia de entrada. Uma coluna adicional diz respeito ao símbolo indicador de fim 
de cadeia de entrada ($). 
Assim, para cada par (estado, símbolo terminal da cadeia de entrada), corresponde uma possível 
ação, ora de empilhamento, ora de aplicação de regra. 
A ação de empilhamento é indicada pelo símbolo ej, onde j é um número inteiro que indica qual 
estado deve ser empilhado juntamente com o símbolo da cadeia de entrada recém-lido. Pela ação de 
empilhamento, o símbolo terminal da entrada é inserido na pilha, sucedido pelo estado indicado.
A ação de aplicação de regra, indicada pelo símbolo rj, assinala qual regra j deverá ser aplicada, para 
que o conteúdo da pilha seja removido e se proceda a uma adequada inserção de um novo símbolo. 
Trata-se de uma ação de substituição de uma forma sentencial presente no lado direito da regra pelo não 
terminal no lado esquerdo da produção. Os estados justapostos aos símbolos terminais e não terminais 
na pilha são também removidos, permanecendo, porém, um estado à esquerda do símbolo não terminal 
recém-armazenado na pilha. Essa configuração da pilha, representada pelo par (estado, símbolo não 
terminal), determina a inserção de um novo estado na pilha, que é obtido a partir da consulta à tabela 
de análise, nas colunas referentes a transições. De fato, sempre que houver uma ação de aplicação de 
regra, o par (estado, símbolo não terminal) determina a transição para um estado que se realiza através 
da inserção do mesmo no topo da pilha. 
O algoritmo inicializa-se com a cadeia de entrada a ser analisada e a pilha com o estado 
q0 armazenado.
O autômato é finalizado quando atinge o par (estado, $), onde $ indica fim da cadeia de entrada, cuja 
ação especificada é aquela especial denominada ac, ou seja, de aceitação da cadeia de entrada.
80
Unidade II
Qualquer combinação de estado, símbolo que resulte em uma célula vazia na tabela de análise, 
corresponde a uma configuração de rejeição da cadeia de entrada.
A gramática com regras para expressões aritméticas é aqui novamente apresentada.
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → x
Apresenta-se a seguir a tabela de análise para a gramática de expressão:
Tabela 13 - Tabela para a gramática de expressão
S Ação Transição
x + * ( ) $ E T F
0 e5 e4 1 2 3
1 e6 ac
2 r2 e7 r2 r2
3 r4 r4 r4 r4
4 e5 e4 8 2 3
5 r6 r6 r6 r6
6 e5 e4 9 3
7 e5 e4 10
8 e6 e11
9 r1 r7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Fonte: Aho et al., 2008.
81
LINGUAGENS FORMAIS E AUTÔMATOS
A seguir, apresenta-se a sequência de movimentos do autômato para o processamento da cadeia de 
entrada x * (x + x).
Tabela 14 
Pilha Entrada Ação
0 x*(x + x)$ 
O par (0, x) aponta na tabela para a ação de empilhamento 
e5: empilha símbolo x, recém-lido na cadeia de entrada e o 
estado 5
0x5  *(x+x)$
O par (5, *) está associado à ação de redução r6: F → x. Assim, 
o símbolo x é substituído na pilha pelo símbolo F. Naturalmente 
o estado 5 também é removido. O par (0,F) desdobra-se na 
transição para o estado 3, conforme a tabela de análise. O 
estado 3 é armazenado na pilha
0F3  *(x+x)$  *
O par (3, *) está associado à ação de redução r4: T → F. Assim, 
o símbolo F é substituído na pilha pelo símbolo T. Naturalmente 
o estado 3 também é removido. O par (0,T) desdobra-se na 
transição para o estado 2, conforme a tabela de análise. O 
estado 2 é armazenado na pilha
0T2  *(x+x)$ O par (2, *) está associado à ação e7. O símbolo * e o estado 7 
são armazenados na pilha
0T2*7   (x+x)$ O par (7, ( ) está associado à ação e4. O símbolo ( e o estado 4 
são inseridos na pilha
0T2*7(4    x+x)$ O par (4,x) está associado à ação e5. O símbolo x e o estado 5 
são armazenados na pilha
0T2*7(4x5    +x)$
O par (5, +) está associado à ação de redução r6: F → x. Assim, 
o símbolo x é substituído na pilha pelo símbolo F. Naturalmente 
o estado 5 também é removido. O par (4,F) desdobra-se na 
transição para o estado 3, conforme a tabela de análise. O 
estado 3 é armazenado na pilha
0T2*7(4F3    +x)$
O par (3, +) resulta na ação de redução r4: T → F. Assim, o 
símbolo F e, consequentemente, o estado 3 são removidos 
da pilha e o símbolo T é inserido na pilha. Seguidamente, 
ocorre a inserção do estado 2, imposta pela ação de transição 
associada ao par 4,T
0T2*7(4T2    +x)$
O par (2, +) resulta na ação de redução r2: E→ T. Assim, o 
símbolo T e, consequentemente, o estado 2 são removidos da 
pilha e o símbolo E é inserido na pilha. Seguidamente, ocorre a 
inserção do estado 8, imposta pela ação de transição associada 
ao par 4,E
0T2*7(4E8    +x)$ O par (8, +) resulta na ação e6. O símbolo + e o estado 6 são 
inseridos na pilha
0T2*7(4E8+6     x)$ O par (6, x) resulta na ação e5. O símbolo x e o estado 5 são 
inseridos na pilha
0T2*7(4E8+6x5      )$
O par (5, )) resulta na ação de redução r6: F→ x. Assim, o 
símbolo x e, consequentemente, o estado 5 são removidos da 
pilha e o símbolo F é inserido na pilha. Seguidamente, ocorre a 
inserção do estado 3, imposta pela ação de transição associada 
ao par 6,F
0T2*7(4E8+6F3      )$
O par (3, )) resulta na ação de redução r4: T→ F. Assim, o 
símbolo F e, consequentemente, o estado 3 são removidos da 
pilha e o símbolo T é inserido na pilha. Seguidamente, ocorre a 
inserção do estado 9, imposta pela ação de transição associada 
ao par 6,T
0T2*7(4E8+6T9      )$
O par (9, )) resulta na ação de redução r1: E→E + T. Assim, a 
forma sentencial E8+6T9 é removida da pilha e substituída 
pelo símbolo E. Seguidamente, ocorre a inserção do estado 8, 
imposta pela ação de transição associada ao par 4,E
82
Unidade II
Pilha Entrada Ação
0T2*7(4E8      )$ O par (8, )) resulta na ação e11. O símbolo ) e o estado 11 são 
inseridos na pilha
0T2*7(4E8 )11       $
O par (11,$) resulta na ação de redução r5: F→ (E). Assim, a 
forma sentencial (4E8)11 é removida da pilha e o símbolo F é 
inserido na pilha. Seguidamente, ocorre a inserção do estado 10, 
imposta pela ação de transição associada ao par 7,F
0T2*7F10       $
O par (10,$) resulta na ação de redução r3: T→ T*F. Assim, a 
forma sentencial T2*7F10 é removida da pilha e o símbolo T é 
inserido na pilha. Seguidamente, ocorre a inserção do estado 2, 
impostapela ação de transição associada ao par 0,T
0T2       $
O par (2,$) resulta na ação de redução r2: E→ T. Assim, a forma 
sentencial T2 é removida da pilha e o símbolo E é inserido na 
pilha. Seguidamente, ocorre a inserção do estado 1, imposta 
pela ação de transição associada ao par 0,E
0E1       $
Finalmente o par (1, $) está associado ao estado de aceitação 
ac, ou seja, a cadeia de entrada x*(x+x) pode ser reduzida ao 
símbolo inicial E
 Lembrete
Se, por um lado, para toda gramática livre de contexto existe um 
autômato de pilha não determinístico, nem sempre esse autômato 
corresponderá a um reconhecimento eficiente. Os métodos mais eficientes 
funcionam apenas para subclasses de gramáticas.
8 LINGUAGENS SENSÍVEIS AO CONTEXTO, LINGUAGENS RECURSIVAS E 
LINGUAGENS RECURSIVAMENTE ENUMERÁVEIS
Apreende-se dos tópicos trabalhados até aqui que:
• As linguagens do tipo 3 (ou regulares) são geradas pelas gramáticas regulares, sejam elas lineares 
à direita ou à esquerda, e são aceitas pelos autômatos finitos.
• As linguagens do tipo 2 (ou livres de contexto) são geradas pelas gramáticas livres de contexto 
e são aceitas por uma classe importante de reconhecedores chamados autômatos de pilha.
Este tópico discorre sobre as linguagens que não são nem regulares, nem livres de contexto. Trata-se, 
portanto, das linguagens sensíveis ao contexto no sentido estrito, as linguagens recursivas e as 
linguagens recursivamente enumeráveis.
As linguagens sensíveis ao contexto e as linguagens irrestritas são geradas pelas gramaticas sensíveis 
ao contexto e irrestritas, respectivamente, e têm como dispositivo aceitador a máquina de Turing. As 
linguagens irrestritas são também denominadas linguagens recursivamente enumeráveis.
83
LINGUAGENS FORMAIS E AUTÔMATOS
As linguagens recursivas são mais abrangentes que as linguagens sensíveis ao contexto, mas não 
é possível caracterizá-las a partir da formulação de restrições ao formato das produções gramaticais 
gerais. Sua caracterização é baseada no modelo de reconhecimento da máquina de Turing.
8.1 Gramáticas sensíveis a contexto e as linguagens sensíveis a contexto
Seja G = (V, S, P, S), diz-se que G é sensível ao contexto se suas produções são da forma:
a→b
Onde a ∈ (V ∪ S)+, b ∈ (V U S)* e |a| ≤ |b|, excetuando-se para a regra S → e. Neste último caso, 
S não pode estar do lado direito de qualquer produção.
As linguagens sensíveis a contexto são definidas a partir das gramáticas sensíveis a contexto.
Define-se linguagem estritamente sensível ao contexto como uma linguagem sensível ao 
contexto, mas não livre de contexto. Exemplo: uma linguagem sensível a contexto, definida pelo alfabeto 
S = {a, b, c}, é:
L(w) = {w | w = an bn cn, n > 0}
Observe-se que uma memória auxiliar organizada em pilha não seria suficiente para verificar se os 
números de ocorrências dos símbolos a, b e c são iguais entre si. Para tanto, seria necessário ao menos 
uma máquina de estados com duas pilhas.
De fato, é possível demonstrar para as linguagens livres de contexto, pela aplicação do Lema do 
Bombeamento, que essa linguagem não pode ser gerada por uma gramática livre de contexto.
Os autores Ramos, José Neto e Vega (2009) trabalham a gramática sensível a contexto geradora 
dessa linguagem conforme o seguinte:
G = (V, S, P, S), com V = {S, A, B, C}, S = {a, b, c}, sendo S o símbolo inicial da gramática e
P = {S → aSBC, 
S → aBC, 
CB → BC, 
aB → ab, 
bB → bb, 
bC → bc, 
cC → cc }
84
Unidade II
Considere as seguintes derivações:
S ⇒ aBC ⇒ abC ⇒ abc
S⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC ⇒ aabBCC ⇒ aabbCC ⇒ aabbbcC ⇒ aabbcc
S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaBCBCBC ⇒ aaaBBCCBC ⇒ aaaBBCBCC ⇒ aaaBBBCCC ⇒ aaabbBCCC ⇒ 
aaabbbCCC ⇒ aaabbbcCC ⇒ aaabbbccC ⇒ aaabbbccc
Exemplo: uma linguagem sensível a contexto, definida sobre o alfabeto S = {a, b } é:
L = {ww | w é palavra de {a, b}*}
Menezes (2008) apresenta a gramática que gera essa linguagem.
Tem-se que:
G = (V, S, P, S), com V = {S, X, Y, A, B, <aa>, <ab>, <ba>, <bb>}, S = {a, b}, sendo S o símbolo inicial 
da gramática e o conjunto das produções P é dado por:
P = {S → XY | aa | bb | e, 
X→ XaA | XbB | aa<aa> | ab<ab> | ba<ba> | bb<bb>, 
Aa → aA, Ab → bA, AY → Ya, 
Ba → aB, Bb → bB, BY → Yb, 
<aa>a → a<aa>, <aa>b → b<aa>, <aa>Y → aa, 
<ab>a → a<ab>, <ab>b → b<ab>, <ab>Y → ab, 
<ba>a → a<ba>, <ba>b → b<ba>, <ba>Y → ba, 
<bb>a → a<bb>, <bb>b → b<bb>, <bb>Y → bb}
Um exemplo de palavra gerada por esta gramática é “abaaba”; de fato, tem-se que:
S ⇒ XY⇒ XaAY⇒ ab<ab>aAY⇒ ⇒ aba<ab>AY⇒ aba<ab>Ya ⇒ abaaba.
Há que se observar que, com exceção da produção S → e, as gramáticas do tipo 2 podem ser sempre 
convertidas para um formato que as torne um caso particular das gramáticas do tipo 1. Assim sendo 
toda linguagem livre de contexto é também uma linguagem sensível ao contexto (Ramos, 2009).
85
LINGUAGENS FORMAIS E AUTÔMATOS
 Observação
Em Ramos, José Neto e Vega (2009), no capítulo dedicado às linguagens 
sensíveis ao contexto, encontra-se uma seção destinada às denominadas 
gramáticas com derivações controladas. Seu uso permite, entre outras 
aplicações, que gramáticas livres de contexto, associadas a extensões 
gramaticais que gerenciam o uso das regras de produção, representem 
linguagens estritamente sensíveis a contexto.
A seguir são apresentados teoremas sobre as linguagens sensíveis ao contexto:
• Toda linguagem livre de contexto L é também uma linguagem sensível ao contexto.
• A classe das linguagens livres de contexto constitui um subconjunto próprio da classe das 
linguagens sensíveis ao contexto.
• O conjunto das gramáticas sensíveis ao contexto sobre um certo alfabeto S é enumerável. 
Encontra-se em Ramos, José Neto e Vega (2009) o algoritmo que enumera todas as gramáticas 
sensíveis ao contexto.
• Existem linguagens que não são sensíveis ao contexto.
• A classe das linguagens sensíveis ao contexto é fechada em relação à operação de união. Em 
outras palavras, se duas linguagens L1 e L2 são sensíveis a contexto, então: L= L1 ∪ L2 também é 
sensível a contexto.
• As linguagens sensíveis ao contexto são fechadas em relação à operação de concatenação. Em 
outras palavras, se duas linguagens L1 e L2 são sensíveis a contexto, então: L= L1.L2 também é 
sensível a contexto.
• As linguagens sensíveis ao contexto são fechadas em relação à operação de intersecção. Em 
outras palavras, se duas linguagens L1 e L2 são sensíveis a contexto, então: L= L1 ∩ L2 também é 
sensível a contexto.
 Observação
A classe das linguagens sensíveis a contexto não é fechada em relação 
à operação do Fecho de Kleene.
Em Ramos (2009), é observado que em 1988 provou-se ser verdadeiro que a classe das linguagens 
sensíveis a contexto é fechada em relação à operação de complementação (Ramos; José Neto; Vega, 2009).
86
Unidade II
8.2 Máquinas de Turing com fita limitada
As máquinas de Turing com fita limitada também são denominadas autômatos com limitação 
linear (em inglês, linear bounded automata). Tais máquinas conceituais são assim conhecidas pois 
efetuam o reconhecimento das linguagens sensíveis a contexto de tal forma que o comprimento da fita 
de entrada é função linear do tamanho da cadeia de entrada. Hopcroft (apud Ramos; José Neto; Veiga, 
2009) mostra que o reconhecimento é possível empregando a fita de trabalho com comprimento da 
cadeia acrescido de duas posições.
Uma máquina de Turing com fita limitada é um dispositivo não determinístico de reconhecimento 
de cadeias, de tal forma que;
• A fita de trabalho tem comprimento igual ao da cadeia de entrada acrescido de dois. O acréscimo 
de dois se dá visto que são usados os dois símbolos delimitadores, a saber: para o início e o 
término da cadeia;
• O cursor de acesso aos símbolos da fita de trabalho pode se deslocar, tanto para a direita como 
para a esquerda, segundo previsto no comando do controle finito.
• Através do cursor de acesso, pode-se ler os símbolos contidos na posição corrente da fita de 
trabalho e também gravar novos símbolos substituindo ossímbolos existentes.
Uma máquina de Turing com fita limitada é formalmente definida como
M = (Q, S, G, g, q0, <, >, F)
Onde:
• Q é o conjunto finito de estados.
• S é o alfabeto de entrada, formado por um conjunto finito de símbolos.
• G é o conjunto finito de símbolos que podem ser lidos e/ou escritos na fita de trabalho: G ⊇ S.
• q0 ∈ Q é o estado inicial.
• F ⊆ Q é o conjunto de estados finais.
• <, > ∉ S são símbolos respectivamente situados imediatamente à esquerda e imediatamente à 
direita da cadeia de entrada na configuração inicial, conhecidos como símbolos delimitadores.
• g é a função parcial de transição e compreende os seguintes mapeamentos:
87
LINGUAGENS FORMAIS E AUTÔMATOS
— g: Q × G → 2Q × G × {E, D}
— g: Q × {< } → 2Q × {< } × {D}
— g: Q × → 2Q × { > } × {E}
• E e D indicam o movimento do cursor para a esquerda e para a direita.
Cumpre observar que os símbolos < e > são empregados como delimitadores da cadeia a ser analisada 
na fita de trabalho.
Hopcroft (apud Ramos; José Neto; Veiga, 2009) enuncia os seguintes teoremas:
• Se L é uma linguagem sensível a contexto, então L é aceita por um autômato com limitação linear.
• Se L é uma linguagem aceita por um autômato com limitação linear, então L é uma linguagem 
sensível a contexto.
As gramáticas sensíveis ao contexto e as máquinas de Turing com fita limitada representam a 
mesma classe de linguagens, ou seja, a classe de linguagens sensíveis a contexto (Kuroda apud Ramos; 
José Neto; Veiga, 2009). Daí, seguem-se os seguintes teoremas enunciados:
• Seja L = L(M), sendo M uma máquina de Turing com fita limitada, então L-{ e } = L(G), sendo G 
uma gramática sensível ao contexto.
• Seja L = L(G), sendo G uma gramática sensível ao contexto, então L = L(M), sendo M uma máquina 
de Turing com fita limitada.
Antes de apresentar um exemplo de uma máquina de Turing com fita limitada, é importante expor, 
conforme Ramos, José Neto e Veiga (2009), que a configuração de uma máquina de Turing com fita 
limitada é dada por uma tripla (a, q, b), onde:
• a é a porção da cadeia que de entrada que se se encontra à esquerda do cursor de acesso.
• q é o estado corrente de reconhecimento da cadeia de entrada.
• b é a porção da cadeia de entrada que se encontra à direita.
• Tem-se que a ∈ G*{<}, e, analogamente, b ∈ G*{>}. 
Em outras palavras, a porção da cadeia de entrada à esquerda é formada pelo símbolo delimitador < 
e por demais símbolos já escritos na fita de trabalho; a porção da cadeia de entrada à direita é formada 
por símbolos na fita de trabalho que serão analisados, incluindo, obviamente, o símbolo delimitador >.
88
Unidade II
• Configuração inicial: depreende-se do parágrafo anterior que a configuração inicial é dada 
pela tripla (<, q0, γ), sendo γ a cadeia de entrada a ser analisada. γ ∈ S*, ou seja, no início do 
processamento a fita de entrada é constituída pelos símbolos do alfabeto de entrada.
• Configuração final: (λ, qf, µ), onde qf é um estado final, sendo λ e µ as cadeias de entrada à 
esquerda e à direita, respectivamente, quando um estado final é acessado. λ ∈ G*{<} e µ ∈ G*{>}. 
As configurações finais são caracterizadas quando:
— Não há transição que possa ser aplicada na configuração corrente.
— O estado corrente é final, não importando a posição do cursor de acesso.
A movimentação de uma configuração (a, qx, b) para uma configuração (a’, qy, b’) (ver tópico 3.4) 
é representada como:
(a, qx, b) - (a’, qy, b’)
A seguir, apresenta-se como exemplo uma máquina de Turing com fita limitada reconhecedora da 
linguagem sensível a contexto L(w) = {w | w = an bn cn, n > 0}. Mostra-se, em seguida, as sucessivas 
movimentações de configuração da máquina no reconhecimento da cadeia <aabbcc>. Exemplo 
(adaptado de Luckner, 2022):
Seja a linguagem sensível a contexto L(w) = {w | w = an bn cn, n > 0} e a máquina de Turing 
M = (Q, S, G, g, q0, <, >, F), onde Q = {q0, q1, q2, q3, q4, qa, qr}, S = {a, b, c} e G = {a, b, X}, q0 o estado 
inicial e qa o estado final de aceitação.
Ainda, a função g de transição é apresentada conforme a seguinte tabela:
Tabela 15
g < a b c X >
q0 — (q1, X, D) qr qr (q0, X, D) qa
q1 — (q1, a, D) (q2, X, D) qr (q1, X, D) qr
q2 — qr (q2, b, D) (q3, X, D) (q2, X, D) qr
q3 — qr qr (q3, c, D) (q3, X, D) (q4, >, E)
q4 (q0, <, D) (q4, a, E) (q4, b, E) (q4, c, E) (q4, X, E) —
As movimentações da configuração da máquina no reconhecimento da cadeia <aabbcc> são 
como se segue:
89
LINGUAGENS FORMAIS E AUTÔMATOS
(<, q0, aabbcc>) ├ (<X, q1, abbcc>) ├ (<Xa, q1, bbcc>) ├ (<XaX, q2, bcc >)
├ (<XaXb, q2, cc>) ├ (<XaXbX, q3, c>) ├ (<XaXbXc, q3, >)
├ (<XaXbX, q4, c>) ├ (<XaXb, q4, Xc>) ├ (<XaX, q4, bXc>)
├ (<Xa, q4, XbXc>) ├ (<X, q4, aXbXc>) ├ (<, q4, XaXbXc>)
├ (, q4, <XaXbXc>) ├ (<, q0, XaXbXc>) ├ (< X, q0, aXbXc>)
├ (<XX, q1, XbXc>) ├ (<XXX, q1, bXc>) ├ (<XXXX, q2, Xc>)
├ (<XXXXX, q2, c>) ├ (<XXXXXX, q3, >) ├ (<XXXXX, q4, X>)
├ (<XXXX, q4, XX>) ├ (<XXX, q4, XXX>) ├ (<XX, q4, XXXX>)
├ (<X, q4, XXXXX>) ├ (<, q4, XXXXXX>) ├ (, q4, <XXXXXX>)
├ (<, q0, XXXXXX>) ├ (<X, q0, XXXXX>) ├ (<XX, q0, XXXX>)
├ (<XXX, q0, XXX>) ├ (<XXXX, q0, XX>) ├ (<XXXXX, q0, X>)
├ (<XXXXXX, q0, >) ├ (<XXXXXX, qa, >)
8.3 Máquinas de Turing
Existem classes de linguagens que não são sensíveis a contexto e que, portanto, não podem ser 
reconhecidas pelas máquinas de Turing com fita limitada – mas ainda podem ser aceitas pelas máquinas 
de Turing com fita ilimitada (ou infinita).
A figura seguinte ilustra a estrutura de uma máquina de Turing.
Controle finito
< σ1 σ2 ... B B ...
Início da fita 
de trabalho
Cadeia a ser 
processada B: branco
Cursor
Função parcial de transição
Figura 46 – Máquina de Turing
90
Unidade II
A seguir, apresenta-se a definição formal da máquina de Turing de acordo com duas referências 
clássicas:
Em Ramos, José Neto e Vega (2009), uma máquina de Turing é definida como 
M = (Q, A, G, g, q0, <, B, F)
Onde:
• Q é o conjunto finito não vazio de estados.
• A é o alfabeto de entrada, formado por um conjunto não vazio de símbolos.
• G é o conjunto finito e não vazio de símbolos que podem ser lidos e/ou escritos na fita de 
trabalho. G ⊇ A.
• q0 ∈ Q é o estado inicial.
• F ⊆ Q é o conjunto de estados finais
• < ∈ G , < ∉ A, é o símbolo que indica a primeira posição da fita de entrada. Ele não pode ser 
gravado em nenhuma outra posição da fita.
• B ∈ T, B ∉ A: preenche todas as posições à direita da cadeia de entrada da fita.
• g é a função parcial de transição.
• g: Q × G → 2Q × G × {E, D}
• E e D indicam o movimento do cursor para a esquerda e para a direita.
A fita de trabalho da máquina de Turing não é finita, e sim ilimitada à direita, com o início marcado 
pelo símbolo especial <.
O cursor de acesso a princípio aponta para o símbolo imediatamente à direita deste delimitador. 
Cumpre observar que há autores que apresentam a máquina de Turing como ilimitada à direita 
e à esquerda.
Ao final da cadeia de entrada, as posições à direita do último símbolo são preenchidas com o 
símbolo B, ou seja, espaço vago.
Sobre a fita de trabalho podem ser executadas as operações de leitura e escrita. Ainda, o cursor pode 
movimentar-se à direita e à esquerda. Saliente-se que, na definição dos autores, o cursor não pode 
se movimentar à esquerda do símbolo de início da fita de trabalho. O símbolo gravado e o sentido do 
movimento são definidos pelo programa da unidade de controle.
91
LINGUAGENS FORMAIS E AUTÔMATOS
O programa é uma função de transição parcial e é tal que, dependendo do estado corrente da 
máquina e do símbolo lido, são determinados o próximo estado, o sentido do movimento do cursor 
e o símbolo a ser gravado na fita.
 Lembrete
A configuração de uma máquina de Turing com fita limitada é dada por 
uma tripla (a, q, b), onde:
• a é a porção da cadeia que de entrada que se se encontra à esquerda 
do cursor de acesso.
• q é o estado corrente de reconhecimento da cadeia de entrada.
• b é a porção da cadeia de entrada que se encontra à direita.• Tem-se que a ∈ G*{<}, e, analogamente, b ∈ G*{>}.
Portanto, 
• Configuração inicial: a configuração inicial é dada pela tripla (<, q0, γ), 
sendo γ a cadeia de entrada a ser analisada. γ ∈ S*, ou seja, no início 
do processamento a fita de entrada é constituída pelos símbolos do 
alfabeto de entrada.
• Configuração final: (λ, qf, µ), onde qf é um estado final, sendo λ 
e µ as cadeias de entrada à esquerda e à direita, respectivamente, 
quando um estado final é acessado. λ ∈ G*{<} e µ ∈ G*{>}.
A movimentação de uma configuração (a, qx, b) para uma configuração 
(a’, qy, b’) é representada por:
(a, qx, b) ├ (a’, qy, b’)
Exemplo
Seja a máquina de Turing T tal que:
• Q = {q0, qf}
• A = {0, 1}
• G = {0, 1, #}
• F = {qf}
92
Unidade II
Ainda, a função de transição g é tal que:
• g(q0, <) = (q0, <, D)
• g(q0, 0) = (q0, 1, D)
• g(q0, 1) = (q0, 0, D)
• g(q0, B) = (qf , #, E)
Observe o reconhecimento da cadeia 01:
< 0 1 B < 0 1 B < 1 1 B
↑ ⇒ ↑ ⇒ ↑ ⇒
q0 q0 q0
< 1 1 B < 1 1 #
↑ ⇒ ↑
q0 qf
Figura 47 – Reconhecimento da cadeia 01
As movimentações da configuração da máquina no reconhecimento da cadeia 01 são:
(<, q0, 01B ├ (<1, q0, 1B>) ├ (<11, q0, B>) ├ (<1, qf, 1#)
Exemplo
Seja a máquina de Turing MT tal que:
• Q = {q0, q1, q2, q3, qf};
• A = {a, b};
• G = {a, b, A, B};
• q0 é o estado inicial e qf é o estado final;
• b, representa neste exemplo espaço em branco (em vez de B)
93
LINGUAGENS FORMAIS E AUTÔMATOS
Ainda, tem-se que:
• g(q0, <) = (q0, <, D) g(q0, a) = (q1, A, D)
• g(q0, B) = (q3, B, D)g(q0, b) = (qf, b, D)
• g(q1, a) = (q1, a, D)g(q1, b) = (q2, B, E)
• g(q1, B) = (q1, B, D)g(q2, a) = (q2, a, E)
• g(q2, A) = (q0, A, D)g(q2, B) = (q2, B, E)
• g(q3, B) = (q3, B, D)g(q3, b) = (qf, b, D)
Esta máquina reconhece a linguagem livre de contexto L = {an bn}.
Observe o reconhecimento da cadeia aabb:
< a a b b b b < a a b b b b 
q0 ⇒ q0 ⇒
< A a b b b b < A a b b b b
q1 ⇒ q1 ⇒
< A a B b b b < A a B b b b
q2 ⇒ q2 ⇒
< A a b b b b < A A B b b b
q0 ⇒ q1 ⇒
< A A B b b b < A A B B b b
q1 ⇒ q2 ⇒
< A A B B b b < A A B B b b
q2 ⇒ q0 ⇒
< A A B B b b < A A B B b b
q3 ⇒ q3 ⇒
< A A B B b b
qf
Figura 48 – Reconhecimento da cadeia aabb
94
Unidade II
As movimentações da configuração da máquina no reconhecimento da cadeia aabb são:
├ (<, q0, aabbbb) ├ (<A, q1, abbbb) ├ (<Aa, q1, bbbb)
├ (<A, q2, aBbbb) ├ (<, q2, AaBbbb) ├ (<A, q0, aBbbb)
├ (<AA, q1, Bbbb) ├ (<AAB, q1, bbb) ├ (<AA, q2, BBbb)
├ (<A, q2, ABBbb) ├ (<AA, q0, BBbb) ├ (< AAB, q3, Bbb)
├ (<AABB, q3, bb) ├ (<AABBb, qf, b)
A definição formal de máquina de Turing conforme Lewis e Papadimitriou (1998) diferencia-se da de 
Ramos, José Neto e Vega fundamentalmente na especificação da função g de transição. Nesta, a função 
de transição tem como contradomínio não um conjunto de triplas; em vez disso, o contradomínio da 
função de transição é um conjunto de pares ordenados, cujo segundo elemento da dupla é um elemento 
pertencente ao alfabeto A ou o indicador de movimento para esquerda ou para direita. 
Dessa forma, uma máquina de Turing se define como uma quíntupla (Q, A, q0, F, g), onde:
• Q é o conjunto de estados.
• A é o alfabeto, contendo o símbolo de espaço em branco b e o símbolo de início de fita <. Não 
contém os símbolos ← e → (indicadores de movimento do cursor para a esquerda e para a direita, 
respectivamente).
• q0 ∈ Q é o estado inicial.
• F ⊆ Q é o conjunto de estados de parada.
• g é a função de transição, com: g: (Q-F) × A → (Q × (A ∪ {← , →}), tal que:
— para todo q ∈ Q – F, se g(q, <) = (p, b), então b = →
— para todo q ∈ Q – F, se a ∈ A, se g(q, a) = (p, b) então b ≠ <
Exemplo
Considere a máquina de Turing M = (Q, A, g, q0, F) onde:
• Q = {q0, q1, q2, q3}
• A = {0, b, <, I, P }
• F = {q3}
95
LINGUAGENS FORMAIS E AUTÔMATOS
E ainda:
• g(q0, <) = (q0, →)
• g(q0, 0) = (q1, →)
• g(q1, 0) = (q2, →)
• g(q1, b) = (q3, I)
• g(q2, 0) = (q1, →)
• g(q2, b) = (q3, P)
Considere esta a cadeia de entrada a ser analisada: <000b. Observe a sequência do reconhecimento 
desde a configuração inicial até a configuração final da fita de trabalho.
< 0 0 0 b < 0 0 0 b
q0 ⇒ q0
< 0 0 0 b < 0 0 0 b
q1 ⇒ q2
< 0 0 0 b < 0 0 0 I
q1 ⇒ q3
Figura 49 – Reconhecimento da cadeia <000b
Exemplo
Considere a máquina de Turing tal que:
M = (Q, A, g, q0, F)
Onde:
• Q = {q0, q1, q2, q3, qf}
• A = {0, 1, b, <, I, P }
• F = {qf }
96
Unidade II
E ainda:
• g(q0, <) = (q0, →)g(q0, 0) = (q1, →)
• g(q1, 0) = (q2, →)g(q1, b) = (q3, I)
• g(q2, 0) = (q1, →)g(q2, b) = (q3, P)
• g(q3, P) = (q3, ←)g(q3, I) = (q3, ←)
• g(q3, 0) = (q3, 1)
• g(q3, 1) = (q3, ←)
• g(q3, <) = (qf, →)
< 0 0 0 b < 0 0 0 b < 0 0 0 b
q0 ⇒ q0 ⇒ q1
< 0 0 0 b < 0 0 0 b < 0 0 0 I
q2 ⇒ q1 ⇒ q3
< 0 0 0 I < 0 0 1 I < 0 0 1 I
q3 ⇒ q3 ⇒ q3
< 0 1 1 I < 0 1 1 I < 1 1 1 I
q3 ⇒ q3 ⇒ q3
< 1 1 1 I < 1 1 1 I
q3 ⇒ qf
Figura 50 – Reconhecimento da cadeia <000b
O modelo de máquina de Turing com fita ilimitada, ao contrário das máquinas conceituais autômato 
finito e autômato de pilha, não necessariamente está associada a um estado de parada obrigatório. 
Observe o seguinte exemplo:
97
LINGUAGENS FORMAIS E AUTÔMATOS
Exemplo
Considere a máquina de Turing tal que:
Q = {q0, q1}A = {x, y}G = {x, y}
A função g é definida como:
• g(q0, <)=(q0, <, D)g(q0, x)=(q1, x, D)g(q0, y)=(q0, x, D)
• g(q0, B)=(q0, B, D)g(q1, x)=(q0, y, D)g(q1, y)=(q0, y, E)
Considere, ainda, a configuração inicial (<, q0, xyB). Tem-se a seguinte sequência de reconhecimento:
(<x, q1, yB) ├ (<, q0, xyB) ├ (x, q1, yB) ├ (<q0, xyB) ├ (x, q1, yB) …
Seja L a linguagem aceita por uma máquina de Turing M. Se uma cadeia w pertencer a L, então 
M para e aceita w. Porém se w ∉ L, M pode parar, poderá entrar em loop infinito, não atingindo uma 
condição de parada.
Definição 
Uma linguagem L é dita recursiva se existir pelo menos uma máquina de Turing M tal que:
• para todo w ∈ L, M para e aceita w.
• para todo w ∉ L, M para e rejeita w.
Uma linguagem recursiva é também dita decidível, pois, para qualquer cadeia pertencente a A*, M 
sempre para, aceitando as sentenças de L e rejeitando as demais.
Em Ramos, José Neto e Vega (2009), observa-se a distinção entre os termos M, M máquina de Turing, 
aceita uma linguagem L e M reconhece L.
Diz-se que M aceita L se M é capaz de atingir uma configuração final para todas as cadeias que 
pertencem a L, não importando o que acontece quando uma cadeia pertencente a A*- L (ou seja, o 
complemento da linguagem L definida sobre o alfabeto A). M reconhece L se M gera saídas distintas 
indicando, para cada cadeia pertencente a A*, se ela pertence ou não a L.
Seguem mais alguns teoremas sobre linguagem recursiva:
• Toda linguagem sensível ao contexto é também recursiva.
• A classe das linguagens sensíveis ao contexto constitui subconjunto próprio da classe das 
linguagens recursivas. Em outras palavras, há linguagens que não são sensíveis a contexto, mas 
são recursivas.
98
Unidade II
• Existem linguagens que não são recursivas.
• A classe das linguagens recursivas é fechada em relação à operação de complementação.
• A classe das linguagens recursivas é fechada em relação à operação de intersecção.
• A classe das linguagens recursivas é fechada em relação à operação de complementação. Em 
outras palavras, o complemento de uma linguagem recursiva é uma linguagem recursiva.
• A classe das linguagens recursivas é fechada em relação à operação de concatenação.
São exemplos de linguagens recursivas:
- L(w) = {anbn | n >=0 }
- L(w) = { wwR | w ∈ {a, b}* }
8.3.1 Formalização do conceito de algoritmo
A máquina de Turing é aceita como uma formalização do conceito de algoritmo a partir da hipótese 
enunciada por Alonzo Church em 1936, mesmo ano em que Alan Turing propôs o modelo de sua máquina.
De acordo com a Enciclopédia de Filosofia de Stanford,
A tese de Church-Turing diz respeito ao um conceito de método eficaz, 
sistemático ou mecânico, como os usados em lógica, matemática e ciência 
da computação.“Eficaz” e seus sinônimos “sistemático” e “mecânico” 
são termos de arte nessas disciplinas: eles não carregam seu significado 
cotidiano. Um método ou procedimento M para alcançar algum resultado 
desejado é chamado de “eficaz” (ou “sistemático” ou “mecânico”) se:
1. M for descrito por um número finito de instruções exatas (cada instrução 
expressa por um número finito de símbolos);
2. M, caso não apresente erros, produzir o resultado desejado em um número 
finito de etapas;
3. M puder (na prática ou em princípio) ser elaborado por um ser humano 
sem o auxílio de uma máquina, apenas de lápis e papel;
4. M não demandar nenhuma inferência, intuição nem inventividade do ser 
humano que o executa (The Church…, 2017, tradução nossa).
99
LINGUAGENS FORMAIS E AUTÔMATOS
Cormen et al. (2022) definem algoritmo como
[…] qualquer procedimento computacional bem definido que toma algum 
valor ou conjunto de valores como entrada e produz algum valor ou conjunto 
de valores como saída. Portanto, um algoritmo é uma sequência de etapas 
computacionais que transformam a entrada na saída.
Na hipótese de Turing-Church, as máquinas de Turing são versões formais de algoritmos, e nenhum 
procedimento computacional pode ser considerado um algoritmo se não estiver apresentado na forma 
de uma máquina de Turing (José Neto, 2003). Estabelece-se, assim, a equivalência entre algoritmos e a 
máquina de Turing – ou seja, a máquina de Turing é o limite máximo que pode ser atingido por qualquer 
outro tipo dispositivo de computação.
A máquina de Turing pode executar cálculos de números inteiros. 
Exemplo
Função incrementa(n), definida como:
• incrementa(n) = n + 1 se n ≥ 0 e;
• incrementa(n) é indefinida para n < 0.
Adota-se representação unária, tal que I é a representação do número inteiro 0 e In
 é a representação 
do número inteiro n – 1, n > 1.
Tem-se que:
Q = {q0, qf }A = {b, <, I }F = {qf}
E ainda:
g(q0, <) = (q0, <, D)g(q0, I) = (q0, I, D)g(q0, b) = (qf, I, D)
< I I I b b < I I I b b < I I I b b
q0 ⇒ q0 ⇒ q0
< I I I b b < I I I b b < I I I I b
q0 ⇒ q0 ⇒ qf
Figura 51 – A função incrementa
100
Unidade II
Um outro enunciado da hipótese de Turing-Church, naturalmente equivalente ao anterior, é que uma 
função da teoria dos números é computável por um algoritmo se, e somente se, for computável por Turing.
8.3.2 Modelos equivalentes à máquina de Turing
Há provas formais que demonstram que o dispositivo da MT com fita infinita tem exatamente o 
poder computacional de qualquer outra versão estendida (Ramos; José Neto; Vega, 2009), tais como 
as seguintes:
• Múltiplas trilhas.
• Múltiplas fitas.
• Múltiplos cursores.
• Fita ilimitada em ambos os sentidos.
• Transições que deslocam o cursor um número variável de posições.
• Transições sem leitura ou gravação de símbolos.
• Máquinas de Turing multidimensionais.
• Máquinas de Turing com uma estrutura de memória auxiliar organizada em pilha.
• Máquinas de Turing não determinísticas.
Em uma máquina não determinística, várias escolhas podem existir para o próximo estado em 
qualquer ponto. Em outras palavras, dada uma mesma combinação de estado corrente e de símbolo na 
fita de trabalho, é possível especificar múltiplas transições. A computação de uma máquina de Turing 
não determinística é uma árvore cujos ramos correspondem a diferentes possibilidades para a máquina. 
Se algum ramo da computação leva ao estado de aceitação, a máquina aceita sua entrada.
Exemplo
• g(q1, a) = (q1, b, D)
• g(q1, a) = (q2, b, D)
• g(q1, a) = (q3, b, D)
• g(q1, a) = (q2, b, E)
101
LINGUAGENS FORMAIS E AUTÔMATOS
Formalmente, uma máquina de Turing não determinística é uma quíntupla (Q, A, q0, F, H), onde:
• Q é o conjunto de estados;
• A é o alfabeto, contendo o símbolo de espaço em branco b e o símbolo de início de fita <. Não 
contém os símbolos ← e → (indicadores de movimento do cursor para a esquerda e para a direita, 
respectivamente);
• q0 ∈ Q é o estado inicial;
• F ⊆ Q é o conjunto de estados de parada;
• H é um subconjunto do produto cartesiano ((Q-F) x A) × (Q x(A ∪ {← , →})).
Teorema: toda máquina de Turing não determinística tem uma máquina de Turing determinística que 
lhe é equivalente. As máquinas de Turing não determinísticas não afetam o poder das determinísticas; 
em vez disso, são equivalentes.
8.4 Gramáticas irrestritas e as linguagens recursivamente enumeráveis
As gramáticas irrestritas ou do tipo 0 apresentam as produções da forma:
a→b, onde a ∈ (V ∪ S)+ e b∈ (V ∪ S)*
Para a gramática irrestrita, as produções não apresentam restrições. Qualquer gramática G = (V, S, P, S) 
é uma gramática irrestrita.
Exemplo extraído de (Menezes, 2008): a linguagem {anbncn | n >=0} é gerada pela seguinte 
gramática irrestrita
G=({ S, C }, { a, b, c }, P, S)
Onde:
• P = { S → abc | e
• ab→ aabbC
• Cb → bC
• Cc→ cc}
102
Unidade II
A palavra aabbcc pode ser derivada como se segue:
S ⇒abc⇒ aabbCc ⇒ aabbcc
Teoremas:
• L é uma linguagem recursivamente enumerável se, e somente se, L for gerada por uma 
gramática irrestrita.
• Uma linguagem L sobre um alfabeto A qualquer é recursiva se, e somente se, L e o complemento 
de L forem recursivamente enumeráveis.
• A classe das linguagens recursivas está contida propriamente na classe das linguagens 
recursivamente enumeráveis.
As classes das linguagens recursivamente enumeráveis são passíveis de serem processadas pelas 
máquinas de Turing.
 Lembrete
De acordo com a hipótese de Church, nenhum procedimento 
computacional é considerado um algoritmo a não ser que possa ser 
apresentado na forma de uma máquina de Turing.
Nesta disciplina, das quatro classes de linguagens previstas na Hierarquia de Chomsky, procurou-se 
explanar de forma mais aprofundada as linguagens regulares e as linguagens livres de contexto.
Para cada uma dessas linguagens, foram apresentados seus dispositivos reconhecedores e geradores.
Os resultados da teoria da computação para as linguagens regulares e para algumas subclasses 
das linguagens livres de contexto garantem a existência de uma correspondência entre os dispositivos 
reconhecedores e os dispositivos geradores das linguagens com desempenho eficiente. Dessa forma, os 
algoritmos empregados em compiladores fazem uso dos dispositivos geradores e aceitadores próprios 
das linguagens regulares e livres de contexto.
O mesmo não pode ser dito com relação à componente sensível a contexto das linguagens de 
programação. Em vez de uma gramática sensível a contexto, é empregada a gramática de atributos, que 
é, na verdade, uma extensão da gramática livre de contexto (Aho et al., 2008).
A aceitação das linguagens sensíveis ao contexto e das linguagens recursivamente enumeráveis 
pode ser realizada pela máquina de Turing. Na prática, no entanto, as implementações eficientes 
desse modelo conceitual dependem de formulações determinísticas equivalentes e, para tanto, isso é 
atualmente objeto de estudo da teoria da computação.
103
LINGUAGENS FORMAIS E AUTÔMATOS
Em sua tese de livre-docência, José Neto (1993) introduziu o conceito de autômatos adaptativos, 
dispositivos com poder equivalente ao da máquina de Turing. Esses dispositivos apresentam a capacidade 
de representar, formalizar e, portanto, reconhecer linguagens dependentes de contexto – e até mesmo 
conjuntos recursivamente enumeráveis. Em Ramos, José Neto e Vega (2009), os dispositivos adaptativos 
são apresentados.
 Saiba mais
Para saber mais sobre a conceituação do autômato e do transdutor 
adaptativo, modalidades de dispositivos de reconhecimento e transdução 
sintática, leia:
JOSÉ NETO, J. Contribuições à metodologia de construção de 
compiladores. 1993. Tese (livre-docência) – Escola Politécnica, Universidade 
de São Paulo, São Paulo, 1993.
104
Unidade II
 Resumo
Nesta unidade foram apresentadas as linguagens livres de contexto, as 
linguagens sensíveis a contexto e as linguagens recursivamente enumeráveis.
A gramática livre de contexto foi definida por Noam Chomsky em 1956 
e trata-sede um dispositivo mais poderoso do que a gramática regular. De 
fato, as produções baseadas nela permitem expressar como os elementos 
de uma forma sentencial se organizam em grupos hierárquicos complexos.
Os algoritmos empregados em compiladores fazem uso dos dispositivos 
geradores e aceitadores das linguagens livres de contexto para o projeto e 
implementação do módulo funcional analisador sintático.
Exemplos de estruturas sintáticas em uma linguagem de programação 
são os diferentes comandos (if, while, classes, variáveis). Para representar 
e processar essas estruturas, deve-se empregar os estudos advindos das 
linguagens livres de contexto.
As linguagens livres de contexto são geradas pelas gramáticas 
livres de contexto.
Uma gramática livre de contexto é uma gramática G = (V, S, P, S), cujas 
produções são da forma A → a, onde A ∈ V e a ∈ (V ∪ ∑ )*.
São exemplos de linguagens livres de contexto aquelas que apresentam 
duplo balanceamento, tais como:
• L(w) = {w | w = an bn , n ≥ 0 }
• L(w) = {w | w = an bn cm dm , n ≥ 0, m > 0 }
Uma árvore de derivação é uma representação gráfica de uma derivação 
que filtra a ordem na qual as produções são aplicadas para substituir 
símbolos não terminais.
Cumpre observar que toda linguagem regular é livre de contexto, mas 
nem toda linguagem livre de contexto é regular. Portanto, uma linguagem 
livre de contexto, em sentido estrito, não pode ser reconhecida por um 
autômato finito.
105
LINGUAGENS FORMAIS E AUTÔMATOS
O dispositivo reconhecedor de uma linguagem livre de contexto 
é o autômato de pilha. Um autômato de pilha pode ser representado 
por uma sêxtupla M:
M = (Q, S, G, g, q0, F)
Onde:
• Q é um conjunto finito de estados;
• S é um alfabeto (finito e não vazio) de entrada;
• G é um alfabeto (finito e não vazio) de pilha;
• g é uma relação de transição g : (Q × (S ∪ {e}) × G*) × (Q × G*);
• q0 é o estado inicial;
• F ⊆ Q é o conjunto de estados finais.
Dois resultados importantes: se L é uma linguagem livre de contexto, 
então existe M, autômato de pilha, com controle de aceitação por estados 
finais com somente três estados, tal que M aceite L; existe M, autômato de 
pilha com controle de aceitação por pilha vazia, com somente um estado, 
tal que M aceite L.
As linguagens livres de contexto geradas por gramáticas livres de 
contexto e as linguagens aceitas por autômatos de pilha são equivalentes. 
Tal atributo proporciona dois métodos diferentes para verificar se uma 
palavra pertence à linguagem gerada a partir das gramáticas.
Um analisador sintático de uma linguagem gerada por uma gramática 
verifica se é possível construir uma árvore de derivação para uma dada 
cadeia de entrada.
Segundo Aho et al. (2008), existem três estratégias gerais de análise 
sintática para o processamento de gramáticas: universal, descendente 
e ascendente.
Como exemplo de método universal, foi apresentado o algoritmo de 
Cocke-Youger-Kasami, que emprega a gramática na forma normal de Chomsky. 
Também foi apresentado o método de análise ascendente que emprega uma 
tabela de análise.
106
Unidade II
As máquinas de Turing são similares aos autômatos finitos e de pilha e 
apresentam fita de entrada e unidade de controle finito.
A fita de entrada de uma máquina de Turing é ilimitada à direita e 
permite que operações de leitura e escrita sejam efetuadas sobre ela. A 
unidade de controle apresenta um conjunto finito de estados, e o cursor 
que aponta para os símbolos armazenados na fita de entrada pode se 
movimentar à direita e à esquerda.
Para o par, símbolo da fita de entrada lido, estado atual de processamento, 
uma função de transição determina o próximo estado a ser alcançado pela 
máquina, o símbolo a ser gravado na fita e o movimento do cursor a ser 
realizado, seguidamente.
As linguagens sensíveis a contexto são definidas a partir das gramáticas 
sensíveis a contexto. Seja G = (V, S, P, S), diz-se que G é sensível ao contexto 
se suas produções são da forma a→b, onde a ∈ (V ∪ S)+, b ∈ (V ∪ T)* e 
|a| ≤ |b|, excetuando-se para a regra S → e. Neste caso, S não pode estar 
do lado direito de qualquer produção.
Um exemplo de uma linguagem sensível a contexto, definida sobre o 
alfabeto S = {a, b, c} é L(w) = {w | w = an bn cn, n > 0}.
L é uma linguagem sensível ao contexto se, e somente se, L for 
reconhecida por uma máquina de Turing com fita limitada.
Para a gramática irrestrita, as produções não apresentam restrições. 
Qualquer gramática G = (V, S, P, S) é uma gramática irrestrita.
L é uma linguagem recursivamente enumerável se, e somente se, L for 
gerada por uma gramática irrestrita.
107
LINGUAGENS FORMAIS E AUTÔMATOS
 Exercícios
Questão 1. (Furb 2022, adaptada) De acordo com Menezes (2005, p. 85), uma gramática utilizada 
em um compilador é, basicamente, um conjunto finito de regras que, quando aplicadas sucessivamente, 
geram palavras. O conjunto de todas as palavras geradas por uma gramática define a linguagem. A figura 
a seguir ilustra uma estrutura hierarquizada para os diferentes tipos de gramática de Chomsky.
Gramáticas com 
estrutura de frase
Gramáticas 
sensíveis ao contexto
Gramáticas 
livres de contexto
Gramáticas 
regulares
Tipo 0
Tipo 1
Tipo 2
Tipo 3
Figura 52
Com base na hierarquia de Chomsky e em seus conhecimentos, avalie as afirmativas.
I – As linguagens geradas por gramáticas livres de contexto são conhecidas como linguagens 
livres de contexto. Cada linguagem livre de contexto apenas pode ser gerada por uma única 
gramática livre de contexto.
II – A proposta de hierarquização de Chomsky agregou à ciência da computação um importante 
estudo sobre as linguagens. A partir dessa hierarquia, passamos a criar as linguagens de programação 
usando conjuntos ilimitados de regras.
III – A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, 
e aumentam as restrições até o tipo 3.
108
Unidade II
É correto apenas o que se afirma em:
A) III.
B) I.
C) II.
D) I e II.
E) II e III.
Resposta correta: alternativa A.
Análise das afirmativas
I – Afirmativa incorreta. 
Justificativa: as linguagens geradas por gramáticas livres de contexto são, de fato, conhecidas como 
linguagens livres de contexto. No entanto, diferentes gramáticas livres de contexto podem gerar a 
mesma linguagem livre de contexto.
II – Afirmativa incorreta. 
Justificativa: a hierarquia de Chomsky foi, realmente, importante para a ciência da computação e 
para o estudo das linguagens. No entanto, não passamos a criar linguagens de programação a partir 
de conjuntos ilimitados de regras. As linguagens de programação são definidas por um conjunto 
finito de regras.
III – Afirmativa correta. 
Justificativa: a classificação das gramáticas, de acordo com a hierarquia de Chomsky, começa pelo 
tipo 0, que apresenta o maior nível de liberdade em suas regras, e vai até o tipo 3, que apresenta o menor 
nível de liberdade. Portanto, as restrições vão aumentando conforme aumentamos o tipo da gramática, 
como podemos observar no diagrama.
109
LINGUAGENS FORMAIS E AUTÔMATOS
Questão 2. O algoritmo de Cocke-Younger-Kasami é capaz de estabelecer se uma cadeia de 
caracteres pode ser gerada por determinada gramática livre de contexto. Considere a gramática 
G = (V, S, P, S), onde:
V = {X, Y, K}
S = {w, z}
S = X (símbolo inicial da gramática)
P = {X → YK; K → Y; X → w; Y → z}
A respeito dessa gramática e do algoritmo, avalie as afirmativas.
A aplicação do algoritmo de Cocke-Younger-Kasami envolve a criação de uma tabela triangular de 
tamanho n x n, onde n é o comprimento da cadeia de caracteres a ser testada.
O algoritmo de Cocke-Younger-Kasami pode ser aplicado à gramática G, pois ela encontra-se na 
forma normal de Chomsky.
Todas as regras de produção de G têm o formato A → a, onde “A” representa uma variável e “a” 
representa um terminal. 
É correto apenas o que se afirma em:
A) III.
B) I.
C) II.
D) I e II.
E) II e III.
Resposta correta: alternativa B.
Análise das afirmativasI – Afirmativa correta. 
Justificativa: o passo inicial da aplicação do algoritmo é, justamente, a construção de uma tabela 
triangular, cujas células a serem preenchidas ocupam o espaço n x n, onde n é o comprimento da cadeia 
de caracteres a ser testada.
110
Unidade II
II – Afirmativa incorreta. 
Justificativa: o algoritmo de Cocke-Younger-Kasami é projetado especificamente para gramáticas 
que se encontram na forma normal de Chomsky. Uma gramática livre de contexto está na forma normal 
de Chomsky quando todas as suas regras de produção estão em uma das duas formas a seguir.
• A → BC, onde “A”, “B” e “C” são variáveis e B e C não são a variável inicial.
• A → a, onde “A” é uma variável e “a” é um terminal.
A regra de produção K → Y não se enquadra em qualquer uma dessas formas, já que existe apenas 
uma variável (Y) à direita. Logo, a gramática G não se encontra na forma normal de Chomsky.
III – Afirmativa incorreta. 
Justificativa: apenas as produções X → w e Y → z encontram-se no formato A →  a, onde “A” 
representa uma variável e “a” representa um terminal.
111
REFERÊNCIAS
Textuais
AHO, A. V. et al. Compiladores, princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson Addison 
Wesley, 2008. 
CHOMSKY, N. Three Models for the Description of Language. IRE Transactions on Information Theory, 
1956. Disponível em: https://tinyurl.com/4fjjkmrr. Acesso em: 2 abr. 2024.
THE CHURCH-Turing Thesis. Stanford Encyclopedia of Philosophy, on-line, 19 dez. 2023. Disponível 
em: https://tinyurl.com/bn3vy6ts. Acesso em: 2 abr. 2024.
CORMEN, T. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: GEN, 2022.
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação. 4. ed. Rio de Janeiro: LTC, 1999.
JOSÉ NETO, J. Introdução à compilação. 2. ed. Rio de Janeiro: Elsevier, 2016.
JOSÉ NETO, J. Adaptive Automata for Context-Dependent Languages. Sigplan notices, New York, v. 29, 
n. 9, 2003. Disponível em: https://tinyurl.com/ycxams76. Acesso em: 2 abr. 2024.
JOSÉ NETO, J. Contribuições à metodologia de construção de compiladores. 1993. Tese (Livre-docência) 
– Escola Politécnica, Universidade de São Paulo, São Paulo, 1993.
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elements of the Theory of Computation. 2. ed. Upper Saddle River: 
Prentice Hall, 1998.
LUCKNER, M. Automata Theory and Formal Languages: Class 9. Politechnika Warszawska, Varsóvia, 16 
jan. 2022. Disponível em: https://tinyurl.com/2jhjcsxx. Acesso em: 2 abr. 2024.
MENEZES, P. B. Linguagens formais e autômatos. Porto Alegre: Bookman, 2008.
RAMOS, M. V. M.; JOSÉ NETO, J.; VEGA, I. S. Linguagens formais. Porto Alegre: Bookman, 2009.
RAPOSO, E. P. Teoria da gramática: a faculdade da linguagem. Lisboa: Caminho, 1998.
ROSA, J. L. G. Linguagens formais e autômatos. Rio de Janeiro: LTC, 2010.
SEBESTA, R. W. Conceitos de linguagens de programação. 5. ed. Porto Alegre: Bookman, 2003.
112
Informações:
www.sepi.unip.br ou 0800 010 9000