CENTRO UNIVERSITÁRIO DO NORTE – UNINORTE

CURSO EM ENGENHARIA DA COMPUTAÇÃO

FRANCISCO RICARDO DE SOUZA-03330612

HELENIANNY G. MEDEIROS -03193701
ISMAEL ISAQUE DIAS FREIAS-03094464

GRAMATICA REGULAR
GRAMATICA DE LIVRE CONTEXTO
FORMA NORMAL DE CHOMSKY
FORMA NORMAL DE GREIBACH

Trabalho apresentada para a disciplina

Linguagens Formais e Autômatos, no curso de
Engenharia da Computação, Centro Universitário
do Norte – UNINORTE.

Prof. Wanderlan Carvalho de Albuquerque

Manaus/AM
2023
[Link]çao

Segundo a Hierarquia de Chomsky, a Linguagem Regular trata-se de uma linguagem mais

simples, sendo possível desenvolver algoritmos de reconhecimento ou de geração de pouca
complexidade, grande eficiência e de fácil implementação.
As Linguagens Livres de Contexto é um reconhecedor de linguagens, capaz de aceitar
palavras corretas (cadeia, sentenças) da linguagem. Por exemplo, os autômatos. Um gerador
de linguagens é um dispositivo capaz de sintetizar todas as palavras de uma linguagem, é o
caso das gramáticas.
Estabelecem restrições rígidas na definição de produções, sem reduzir o poder de geração das
GLCs Gramáticas Livres de Contexto; Obtenção de gramáticas adequadas para o parsing e
para obtenção de autômato de pilha para LLC.

[Link] Regular

Definição 09:

Seja G = (V, T, P, S) uma gramática e sejam A e B elementos de V e w uma

palavra de T*. Então G é uma:
(a) Gramática Linear à Direita (GLD) se todas as regras de produção são da forma:
A wB ou A  w

(b) Gramática Linear à Esquerda (GLE) se todas as regras de produção são da forma:
A Bw ou A  w

(c) Gramática Linear Unitária à Direita (GLUD) se todas as regras de produção são
como na linear à direita e, adicionalmente |w| <= 1
(d) Gramática Linear Unitária à Esquerda (GLUE) se todas as regras de
produção são como na linear à esquerda e, adicionalmente |w| <= 1
• Exemplo 14:

(a) G = ({S}, {x, y}, P, S)

 P = { S  xyS, S  x}

Assim, G é uma GLD

(b) G = ({S1, S2, S3}, {a, b}, P, S1)

P = { S1  S2ab, S2  S2ab | S3, S3  a }

Assim, G é uma GLE

(c) G = ({S, A, B}, {a, b}, P, S)

P = { S  A, A  aB|  , B

 Ab } Assim, G não é

Linear

Definição 10:
Uma Gramática Regular é qualquer Gramática Linear

Teorema 02:

Se L é uma linguagem gerada por uma Gramática Regular, então L é uma

Linguagem Regular.

Prova:
Para mostrar que uma linguagem é regular, é suficiente construir um AF que a reconheça.
Suponha G = ( V, T, P, S) uma GLUD. Então o AF M = {Q,  ,  , q0, F} com:
Q = V  { qf }
 = T q0 = S
F = { qf }

, como na tabela abaixo:

Tipo de Produção Transição Gerada
A (A, ) = qf
Aa (A, a) = qf
AB (A, ) = B
A  aB (A, a) = B
Simula as derivações de G, ou seja, L(G) = L(M).

A demonstração que L(G) = L(M) é verdade de fato, está no número

 de derivações. Seja  elemento de (T  V)* e w elemento de T*,
então:
(a) base de indução. Suponha S 1 , então, se:
(a .1.)  = , existe uma regra S   e assim para o
AFM, (S, ) = qf (a .2.)  = a, existe uma regra S  a e
assim para o AFM, (S, a) = qf (a .3.)  = A, existe uma
regra S  A e assim para o AFM, (S, ) = A
(a .4.)  = aA, existe uma regra S  aA e assim para o AFM, (S, a) = A

(b) hipótese de indução. Suponha que S n , n >

1, tal que, se: (b.1.)  = w, então *(S, w)
= qf
(b.2.)  = wA, então *(S, w) = A

(c) passo da indução. Suponha que S n+1 . Então ocorre a hipótese (b.2.) e S n wA
1 
(c.1.)  = w, existe uma regra A   e assim
*(S, w) = (*(S, w),)
= (A, ) = qf (c.2.)  = wb, existe uma
regra A  b e assim
* (S, wb) = (* (S, w),b)
= (A, b) = qf (c.3.)  = wB, existe uma
regra A  B e assim
* (S, w) = (* (S, w),)
= (A, ) = B (c.4.)  = wbB, existe uma
regra A  bB e assim
* (S, wb) = (* (S, w),b) = (A, b) = B

Exemplo 15:

Considere a GLUD, G = ({S, A, B}, {a, b}, P, S), onde P é:

S  aA
A  bB|
B  aA
O AF M que reconhece a linguagem gerada por G é: M = ({S,A,B, qf }, {a,b},  , S, {qf }),
tal que  é dada na tabela abaixo:

Produção Transição Gerada

S  aA (S, a) = A
A  bB (A, b) = B
A (A, ) = qf
B  aA (B, a) = A
Teorema 03:
Se L é uma linguagem Regular, então existe uma Gramática Regular que gera L.
Prova:
Se L é uma Linguagem Regular, então existe um AFN M = {Q,  ,  , q0, F} tal que L(M)
= L. A idéia central da demonstração é construir uma GLD G a partir de M tal que L(G) =
L(M).
Então G = (V, T, P, S) tal que: V = Q  {S} e T = 
P é construído como segue:

Transição Tipo de Produção

- S  q0
- qf  
( qi, a) = qk qi  a qk

Suponha w elemento de *
a) base de indução: seja w tal que seu comprimento seja zero (|w|=0). Então
a cadeia vazia pertence à linguagem L(M), logo q0 é um estado final e assim q0

S  q0  

b) hipótese de indução. Seja w tal que |w| = n (n  1) e *(q0 , w) = q. Então

b.1) q não é estado final, então S  wq
b.2) q é estado final, então S  wq  w

c) Passo de indução. Seja w tal que |wa| = n+1 e *(q0 , wa) = p. Então (*(q0
, w),a) = p. Portanto ocorre somente a hipótese b.1 acima e 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

1 Exemplo 16:
Seja M = ({q0, q1, q2}, {a,b,c},  , q0, {q0, q1, q2})
Então G = ({q0, q1, q2, S}, {a,b,c}, S, P), onde P é como a tabela abaixo:

Transição Tipo de Produção

- S  q0
- Q0  
- Q1  
- Q2  
( q0, a) = q0 Q0  a q 0
( q0, b) = q1 Q0  b q 1
( q1, b) = q1 Q1  b q 1
( q1, c) = q2 Q1  c q 2
( q2, c) = q2 Q2  c q 2
3. GRAMÁTICA LIVRE DE CONTEXTO

As Linguagens Livres Contexto são desenvolvidas a partir das Gramáticas Livres de Contexto
(GLC). A GLC é um tipo mais complexo de geradores de linguagem, as quais materializam um
completo entendimento do procedimento de construção das palavras pertencentes à linguagem. A
GLC é aplicada em compiladores e
conversores de documentos.

Exemplo: GLC para a linguagem an bn

Regras
1- S _ l
2- S _ a S b
Exemplo de funcionamento para a palavra aabb
S _ a S b (aplicamos a regra 2)
aa S bb (aplicamos em S a regra 2)
aal bb (aplicamos em S a regra 1)
Resultado: aabb

Definição:
Há quatro conceitos importantes em uma descrição de uma gramática:

 Um conjunto finito de símbolos, chamados terminais ou símbolos terminais;

 Conjunto finito de variáveis, chamados de categorias sintáticas ou não terminais.
 Uma das variáveis representa a linguagem que está sendo definida, chamada símbolo de
início.

Existe um conjunto finito de produções ou regras que representam a definição recursiva

de uma linguagem. Cada produção consiste em:
 Uma variável que está sendo (parcialmente) definida pela produção. Essa variável é
chamada de cabeça (head) da produção
 O símbolo de produção, →
 Uma palavra de zero ou mais terminais e variáveis. Esta parte é chamada de corpo.
 O lado esquerdo das produções possui exatamente uma variável.

Definição Formal

Exemplo
Definir a gramática que gera palíndromos. “Um Palíndromo é uma cadeia lido da mesma
forma, da direita para a esquerda e da esquerda para a direita”.

Exemplo1: 0110, 11011, 000, ε são palíndromos

Exemplo2: 011, 0101, 1010 não são palíndromos.
Gramática
G=({P, {0, 1}, A, S)
Onde A é dada por:
1. S →  Redução do espaço utilizando a seguinte notação :
2. S →0 ou S→  |0|1|0S0|1S1
3. S →1
4. S → 0 S 0
5. S → 1 S 1

Gerar a palavra w = 00100100

S → 0S0
00S00
001S100
0010S0100
0010  0100

Derivações
Aplicando as regras de produção em ordens diferentes, uma gramática pode gerar muitas
cadeias. O conjunto de todas tais cadeias é a linguagem definida ou gerada pela gramática.
Existe duas formas de derivação : derivação Mais à Esquerda e Mais à Direita
EXEMPLO: LINGUAGEM LIVRE DE CONTEXTO
A linguagem gerada pela GLC abaixo é composta por expressões aritméticas contendo
colchetes balanceados, dois operandos e um operador:
G = ({E}, {+, *, [, ], x}, P, E), onde

P = { E → E+E | E*E | [E] | x }.Por exemplo, a expressão [x+x]*x pode ser gerada pela

seguinte seqüência de derivações:

E →E*E [E]*E [E+E]*E [x+E]*E[x+x]*E [x+x]*x

E → E*E [E]*E [E+E]*E [x+E]*E

[x+x]*E [x+x]*x
[Link] Normal de Chomsky
Forma Normal de Chomsky
𝐴 → 𝐵𝐶, 𝐴→𝑎
Toda LLC (Linguagem Livre de Contexto) sem 𝜀 tem uma gramática G na qual todas as
produções são
da forma:

𝐴 → 𝐵𝐶
𝐴→𝑎
Para transformar uma GLC na forma normal de Chomsky, deve-se executar uma
simplificação preliminar:
Eliminar símbolos inúteis;
Eliminar produções vazias (𝐴 → 𝜀);
Eliminar produções unitárias (𝐴 →𝐵);
Com a gramática simplificada,
faz-se a transformação para Forma Normal de Chomsky:
[Link] as produções com tamanho maior que 2 devem ser alteradas para terem somente
variáveis;
[Link] as produções com tamanho maior ou igual a três devem ser quebradas em produções
cascatas, cada uma com duas variáveis:
Exemplo:
 5. Formas Normal de Greibach

Forma Normal de Greibach

𝐴 → 𝑎𝛼, onde α é uma sequência de variáveis
Produções da Forma: 𝐴 → 𝑎𝛼, onde a é terminal e α é uma sequência de zero
ou mais variáveis;
Mais complexo converter para essa forma;
Mesmo partindo de uma gramática na forma normal de Chomsky;
Passos para transformação:

Simplificação;
Renomeação de variáveis;
Transformar para 𝐴𝑟 → 𝐴𝑠𝛼, onde 𝑟 ≤ 𝑠 (e recursões);

Eliminar inícios por variável (𝐴1 →𝐴2𝐴2);

Transformação para a Forma Normal
de Greibach

Eliminar 𝐴𝑟 → 𝐴 𝑠 𝛼, onde 𝑟 > 𝑠

Excluir tal produção

E incluir 𝐴𝑟 →

𝛽𝛼, onde β é o lado

direito das

produções de As;
Eliminar recursões

Colocar terminal no início

 𝐴 ⇒+ 𝐴𝛼
Entende-se por recursão a esquerda a ocorrência da seguinte situação:

Uma variável deriva ela mesma, de forma direta ou indireta, como símbolo mais a
esquerda de uma subpalavra gerada.
Elimina-se a recursão a esquerda executando-se as quatro primeiras etapas do algoritmo de

Greibach.

1-Simplificação da Gramática

2-Renomeação das variáveis em ordem crescente

3 Qualquer produção é da forma

𝐴𝑟 → 𝐴𝑠𝛼 𝑜𝑛𝑑𝑒 𝑟 < 𝑠

4 Exclusão das recursões

Referências

HOPCROFT, J. E., ULLMAN, J. D. e

MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação.
Ed. Campus, 2002.

ENEZES, Paulo Blauth. Linguagens Formais e Autômatos.

Porto Alegre: Editora Sagra-Luzzatto, 1998.

VIEIRA, Newton José. Introdução aos Fundamentos da Computação. São Paulo:

Editora Thomson Learning, 2006.