Parte 4

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
4 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
Compreender a diferença entre as gramáticas e suas derivações é de suma importância 
para a execução dos autômatos, base de todas as linguagens de computação, já a teoria 
da ambiguidade nos mostra a importância de definirmos de forma assertiva as 
linguagens utilizadas para menor impacto nas linguagens de programação que serão 
geras a partir das gramáticas. 
Introdução 
 Abordaremos o conceito de gramáticas regulares e ambiguidade, com 
demonstrações de execução bem como tabelas e autômatos das definições que serão 
apresentadas, sua importância e a correta aplicação dos conceitos trazem as bases para as 
linguagens de programação, compreender o conceito de ambiguidade reduz a 
probabilidade de incompatibilidade com as linguagens de programação. 
 
 
4.1. Gramáticas regulares 
No conceito de gramáticas é possível definir tanto linguagens regulares como linguagens 
não regulares. Contudo é possível estabelecer restrições nas regras de produção, de forma 
a definir exatamente a classe das linguagens regulares. Possuímos mais uma forma de 
restringir as regras de produção de forma a definir uma gramática regular, para isso 
demonstraremos a seguir quatro destas formas chamadas gramáticas lineares. 
Seja G = (V, T, P, S) uma gramática e A e B elementos de V e w uma palavra de T*, 
então G é uma gramática linear se todas as suas produções se encontram em uma e em 
somente uma das seguintes formas: 
Gramática linear à direita (GLD) – todas as regras da produção são da forma: 
 A ⟶ wB ou A⟶ w 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Gramática linear à esquerda (GLE) – todas as regras de produção são da forma: 
 A ⟶ Bw ou A⟶ w 
Gramática linear unitária à direita (GLUD) – todas as regras de produção são como na 
gramática linear à direita e adicionalmente: 
 | w | ≤ 1 
Gramática linear unitária à esquerda (GLUE) – todas as regras de produção são como na 
gramática linear à esquerda e adicionalmente: 
 | w | ≤ 1 
Nota-se que as gramáticas lineares possuem forte restrição no formato das produções: 
• O lado esquerdo possui exatamente uma variável; 
• O lado direito de uma produção é constituído por no máximo uma variável. 
Adicionalmente esta variável, se existir, sempre antecede linear à esquerda ou 
sucede linear à direita qualquer subpalavra eventualmente vazia de terminais. 
Devemos verificar se é possível definir uma gramática que satisfaça simultaneamente as 
quatros formas lineares. 
Para demonstramos a equivalência das gramáticas lineares utilizaremos L uma 
linguagem: 
 L é gerada por uma GLD se, e somente se, 
 L é gerada por uma GLE se, e somente se, 
 L é gerada por uma GLUD se, e somente se, 
 L é gerada por uma GLUE. 
Isto é, as diversas formas das gramáticas lineares são formalismos equivalentes. 
Uma gramática G é dita uma gramática regular GR, se G é uma gramática linear. Vamos 
demonstrar uma linguagem gerada por uma gramática. 
Seja G = (V, T, P, S) uma gramática, a linguagem gerada pela gramática G, denotada 
por: 
 L(G) ou GERA(G) 
É tal que: 
 L(G) = {w ∈ T* | S ⟹+ w} 
 
Vamos ver os tipos de gramáticas regulares, usaremos para exemplificar a(ba)*, a 
linguagem a(ba)* é gerada pelas seguintes gramáticas regulares: 
Linear à direita: G = ({S, A}, {a, b}, P, S) e P possui as seguintes regras de produção: 
 S⟶aA 
 A⟶baA | 𝜺 
Linear à esquerda: G = ({S}, {a, b}, P, S) e P possui as seguintes regras de produção: 
 S⟶Sba | a 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Linear unitária à direita: G = ({S, A, B}, {a, b}, P, S) e P possui as seguintes regras de 
produção: 
 S⟶aA 
 A⟶bB | 𝜺 
 B⟶aA 
Linear unitária à esquerda: G = ({S, A}, {a, b}, P, S) e P possui as seguintes regras de 
produção: 
 S⟶Aa | a 
 A⟶Sb 
Outro exemplo de gramática regular: (a + b)*(aa + bb), assim a linguagem (a + b)*(aa 
+ bb) é gerada pelas seguintes gramáticas regulares: 
Linear à direita: G = ({S, A}, {a, b}, P, S) e P possui as seguintes regras de produção: 
 S⟶aS | bS | A 
 A⟶aa | bb 
Linear à esquerda: G = ({S, A}, {a, b}, P, S} e P possui as seguintes regras de produção: 
 S⟶Aaa | Abb 
 A⟶Aa | Ab | 𝜺 
Devemos observar que nas gramáticas lineares à esquerda e à direita possuem 
particularidades para compreendermos suponhamos | w | ≥ 1. Se uma gramática tiver 
simultaneamente produções do tipo produções do tipo A⟶wB (linear à direita) e do tipo 
A⟶Bw (linear à esquerda), então a linguagem correspondente gerada poderá não ser 
regular, ou seja, esta não é uma gramática regular. Por exemplo, já abordamos que uma 
linguagem que possua duplo balanceamento não é regular. Em particular a seguinte 
linguagem não é regular: 
 {an bn | n ∈ N} 
Contudo é possível desenvolver uma gramática, com produções lineares à direita e à 
esquerda, que gera esta linguagem. Veremos dois teoremas que mostram que a classe das 
gramáticas regulares denota exatamente a classe das linguagens regulares. 
Gramática regular ⟶ linguagem regular 
Se L é uma linguagem gerada por uma gramática regular, então L é uma linguagem 
regular. 
Prova – por indução 
Para mostrar que uma linguagem é regular, é suficiente construir um autômato finito que 
a reconheça. Suponha G = (V, T, P, S) uma gramática linear unitária à direita, então o 
AFN𝜺: 
 M = (∑, Q, 𝜹, q0, F) 
Tal que (suponha qf ∉ V): 
 ∑ = T 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 Q = V ∪ {qf} 
 F = {qf} 
 q0 = S 
 𝜹 é construída como ilustrado na tabela abaixo (suponha A e B variáveis e a 
terminal) simulando as derivações de G, ou seja: 
 
 ACEITA(M) = GERA(G) 
 
 
Tabela 1.1 Transições construídas a partir das produções 
tipo da produção transição gerada 
A⟶ 𝜺 𝜹(A, 𝜺) = {qf} 
A⟶a 𝜹(A, a) = {qf} 
A⟶B1 | ... | Bn 𝜹(A, 𝜺) = {B1, ..., Bn} 
A⟶aB1 | ... | aBn 𝜹(A, a) = {B1, ..., Bn} 
Fonte: Paulo Blauth Menezes, 2011. 
 
A demonstração que, de fato, ACEITA(M) = GERA(G) é por indução no número de 
derivações, como segue (suponha 𝜶 elemento de (T ∪ V)* e w elemento de T*): 
a) Base de indução – Suponha que S⟹1 𝜶, então, se: 
a.1) 𝜶 = 𝜺, existe uma regra S⟶ 𝜺, por construção de M, 𝜹(S, 𝜺) = {qf} 
a.2) 𝜶 = a, existe uma regra S⟶a, por construção de M, 𝜹(S, a) = {qf} 
a.3) 𝜶 = A, existe uma regra S⟶A, por construção de M, 𝜹(S, 𝜺) = {A} 
a.4) 𝜶 = aA, existe uma regra S⟶aA, por construção de M, 𝜹(S, a) = {A} 
 
b) Hipótese de indução – Suponha que S⟹n 𝜶, n > 1, então, se: 
b.1) 𝜶 = w, então 𝜹*(S, w) = {qf} 
b.2) 𝜶 = wA, então 𝜹*(S, w) = {A} 
 
c) Passo de indução – Suponha que S⟹n+1 𝜶, obrigatoriamente ocorre somente a 
hipótese b.2 acima, então: 
 
 S⟹n wA⟹1 𝜶 
 
c.1) 𝜶 = w𝜺 = w, existe uma regra A⟶ 𝜺, logo: 
 𝜹*(S, w𝜺) = 𝜹(𝜹*(S, w), 𝜺) = 𝜹(A, 𝜺) = {qf} 
c.2) 𝜶 = wb = w, existe uma regra A⟶b, logo: 
 𝜹*(S, wb) = 𝜹(𝜹*(S, w), b) = 𝜹(A, b) = {qf} 
c.3) 𝜶 = wB, existe uma regra A⟶B, logo: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 𝜹*(S, w𝜺) = 𝜹(𝜹*(S, w), 𝜺) = 𝜹(A, 𝜺) = {B} 
c.4) 𝜶 = wbB, existe uma regra A⟶bB, logo: 
 𝜹*(S, wb) = 𝜹(𝜹*(S, w), b) = 𝜹(A, b) = {B} 
 
Para construirmos um AFN𝜺 a partir de uma gramática regular, podemos considerar a 
seguinte gramática linear à direita: 
 G = ({S, A, B}, {a, b}, P, S) 
Onde P é tal que: 
 S⟶aA 
 A⟶bB | 𝜺 
 B⟶aA 
O AFN𝜺 M que reconhece a linguagem gerada pela gramática G é: 
 M = ({a, b}, {S, A, B, qf}, 𝜹, S, {qf}) 
 
Para melhor entendimento observe a figura abaixo e a tabela: 
 
Figura 1.1 Autômato Finito construído a partir de uma gramática regular 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Tabela 1.2 Transições construídas a partir das produções 
produção transição 
S⟶aA𝜹(S, a) = {A} 
A⟶bB 𝜹(A, b) = {B} 
A⟶ 𝜺 𝜹(A, 𝜺) = {qf} 
A⟶aA 𝜹(B, a) = {A} 
Fonte: Paulo Blauth Menezes, 2011. 
Linguagem Regular ⟶ Gramática regular 
Se L é linguagem regular, então existe G, gramática regular que gera L. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Prova – por indução 
Se L é uma linguagem regular, então existe um AFD M = (∑, Q, 𝜹, q0, F) tal que 
ACEITA(M) = L. A ideia central da demonstração é construir uma gramática linear à 
direita G a partir de M tal que: 
 GERA(G) = ACEITA(M) 
Ou seja, cuja derivação simula a função programa estendida, seja a gramática regular: 
 G = (V, T, P, S) 
Tal que, suponhamos S ∉ Q: 
 V = Q ∪ {S} 
 T = ∑ 
 P é construído como vemos na tabela abaixo, supondo qi, qk elementos de 
Q, qf elemento de F e a elemento de ∑: 
 
Tabela 1.3 Transições construídas a partir das produções 
transição produção 
- S⟶q0 
- qf ⟶ 𝜺 
𝜹(qi, a) = qk qi ⟶ aqk 
Fonte: Paulo Blauth Menezes, 2011. 
 
A demonstração de que, de fato GERA(G) = ACEITA(M) é por indução no tamanho da 
palavra como segue supondo w elemento de ∑*: 
Base de indução – seja w tal que | w | = 0, por definição vale que S⟶q0 é produção. Se 
𝜺 ∈ ACEITA(M), então q0 é o estado final e por definição vale que q0⟶ 𝜺 é produção. 
Logo: 
 S⟹q0⟹ 𝜺 
Hipótese de indução – seja w tal que | w | = n (n ≥ 1) e 𝜹*(q0, w) = q, assim se: 
 b.1) q não é estado final então suponha que S⟹n wq 
 b.2) q é estado final então suponha que S⟹n wq⟹ w (este caso não é 
importante para o passo de indução). 
Passo de indução – seja w tal que | wa | = n + 1 e 𝜹*(q0, wa) = p, então: 
 𝛿(𝛿*(q0, w), a) = 𝛿(q, a) = p 
Portanto, obrigatoriamente ocorre somente a hipótese b.1, demonstrada acima, se: 
 c.1) p não é estado final, então S⟹n wq⟹1 wap 
 c.2) p é estado é final, então S⟹n wq⟹1 wap⟹1 wa 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Para construção de uma gramática regular a partir de um AFD consideramos o autômato 
finito determinístico: 
 M = ({a, b, c}, {q0, q1, q2}, 𝜹, q0, {q0, q1, q2}) 
A figura abaixo se refere a gramática regular correspondente é construída: 
 G = ({q0, q1, q2, S}, {a, b, c}, P, S) 
 
Figura 1.2 Diagrama do autômato finito determinístico 
 
 
Fonte: Paulo Blauth Menezes, 2011. 
E P é dado pela tabela abaixo: 
 
Tabela 1.4 Produções construídas a partir de transições 
transição produção 
- S⟶q0 
- q0 ⟶ 𝜺 
- q1 ⟶ 𝜺 
- q2 ⟶ 𝜺 
𝜹(qo, a) = q0 q0 ⟶ aq0 
𝜹(qo, a) = q1 q0 ⟶ bq1 
𝜹(q1, b) = q1 q1 ⟶ bq1 
𝜹(q1, c) = q2 q1 ⟶ cq2 
𝜹(q2, c) = q2 q2 ⟶ cq2 
Fonte: Paulo Blauth Menezes, 2011. 
 
 
 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Você sabia? 
Ficou curioso em aprofundar seu conhecimento sobre Gramática Regular? Vamos 
assistir a um vídeo sobre o assunto. Assista ao vídeo Gramática Regular e 
Transformações – com o Prof. José Rui. Disponível em: 
< https://www.youtube.com/watch?v=CzaVNvWMXz0&t=11s>. Acesso em: 18 abr. 
2023. 
 
4.2. Ambiguidade 
Como vimos diversas vezes uma gramática pode gerar a mesma cadeia de diversas formas 
diferentes. 
Esta cadeia terá árvores sintáticas diferentes e por consequência vários significados 
diferentes. Sendo que o resultado pode ser indesejável para certas aplicações, por exemplo 
em linguagens de programação onde um programa deve ter apenas uma única 
interpretação. 
Já que uma gramática pode gerar a mesma cadeia de diversas maneiras diferentes, 
dizemos que a cadeia é derivada ambiguamente naquela gramática. E se esta gramática 
gera alguma cadeia ambiguamente dizemos que a gramática é ambígua. Por exemplo, 
consideraremos a gramática G5: 
 
<EXPR> ⟶ <EXPR> + <EXPR> | <EXPR> * <EXPR> | (<EXPR>) | a 
 
Esta gramática gera a cadeia a+a*a ambiguamente. 
 
Figura 1.3 Duas árvores sintáticas para a cadeia a+a*a na gramática G5 
 
Fonte: Michael Sipser, 2007. 
 
Como podemos ver essa gramática não captura as relações de precedência usuais e, 
portanto, pode agrupar o + antes do * ou vice-versa. Neste momento formalizamos a 
noção de ambiguidade, ao dizermos que uma gramática gera uma cadeia ambiguamente, 
significa que a cadeia tem duas árvores sintáticas diferentes e não duas derivações 
diferentes. Duas derivações podem diferenciar-se na sua estrutura, portanto vamos focar 
sobre a estrutura definindo um tipo de derivação que substitui variáveis em ordem fixada. 
Uma derivação de uma cadeia w em uma gramática G é uma derivação à esquerda, se a 
cada passo a variável à esquerda restante é aquela a ser substituída. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Já uma cadeia w é derivada ambiguamente na gramática livre do contexto G se ela tem 
duas ou mais derivações à esquerda. A gramática G é ambígua se ela gera alguma cadeia 
ambiguamente. 
 
 
 
Você sabia? 
Como vimos a ambiguidade ocorre quando uma gramática gera a mesma cadeia de 
várias formas diferentes? Assista ao vídeo Ambiguidade em GLCs. Disponível em: 
< https://www.youtube.com/watch?v=gM6_X-zedyQ>. Acesso em: 16 abr. 2023. 
 
 
 
Considerações finais 
 Entender a diferença entre gramáticas e suas derivadas é de suma importância na 
implementação de autômatos, que é a base de todas as linguagens de computador, pois a 
teoria da ambiguidade nos mostra a importância de definir as linguagens utilizadas para 
minimizar o impacto nas linguagens de programação aritmética a ser gerada a partir de 
regras gramaticais. Abordamos o conceito de gramáticas regulares e de ambiguidade, com 
demonstrações de execução bem como tabelas e autômatos das definições que foram 
expostas, sua importância e a correta aplicação dos conceitos fundamentam as linguagens 
de programação, o entendimento do conceito de a ambiguidade reduz a probabilidade de 
incompatibilidade com linguagens de programação. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: 
Bookman, 2011. 
SIPSER, Michael. Introdução à Teoria da Computação. 2. ed. São Paulo: Cengage 
Learning, 2007.