TRANSFORMAÇÕES
GRAMATICAIS
DANIELA REIS
Sumário
INTRODUÇÃO������������������������������������������������� 3
GRAMÁTICA REGULAR ��������������������������������� 4
GRAMÁTICAS LIVRES DE CONTEXTO��������� 11
GRAMÁTICAS REGULARES VERSUS
AUTÔMATOS FINITOS��������������������������������� 15
TRANSFORMAÇÕES GRAMATICAIS����������� 20
FORMAS NORMAIS�������������������������������������� 25
EXEMPLOS E DEMONSTRAÇÕES���������������� 34
CONSIDERAÇÕES FINAIS���������������������������� 39
REFERÊNCIAS BIBLIOGRÁFICAS &
CONSULTADAS�������������������������������������������� 41
2
INTRODUÇÃO
Neste e-book, abordaremos os conceitos funda-
mentais sobre as transformações gramaticais,
com exemplos e demonstrações.
Discutiremos sobre gramática regular e sua rela-
ção com autômatos finitos, além de analisarmos
as gramáticas livres de contexto, compreendendo
sobre as transformações gramaticais e as formas
normais.
Bons estudos!
3
GRAMÁTICA REGULAR
Para a ciência da computação, uma gramática é
um conjunto de regras para juntar strings (cadeias
de caracteres) e, portanto, corresponder a uma
linguagem.
Uma gramática consiste em um conjunto de variáveis,
também chamadas de não-terminais, sendo uma
delas designada como variável inicial. É comum
usarmos letras maiúsculas para variáveis e também
existir um conjunto de terminais do alfabeto e uma
lista de produções, também chamada de regras.
As gramáticas regulares são outra maneira de
descrever linguagens regulares. Em relação a elas,
devemos ter em mente que uma gramática é com-
posta por terminais, variáveis e regras de produção.
Como o nome indica, uma gramática regular é um
tipo especial de gramática, pois existem muitas
gramáticas que não são regulares.
A partir delas, temos as linguagens. Na gramática
regular, o lado esquerdo sempre consiste em um
único não-terminal. Enquanto o lado esquerdo não
pode ter mais de uma variável não-terminal ou
qualquer variável terminal. Nele, pode haver um
único terminal ou um único terminal seguido por
um não-terminal no lado direito.
4
A produção da gramática regular deverá ocorrer
do seguinte modo:
𝑋𝑋 → 𝑥𝑥𝑥𝑥
𝑋𝑋 → 𝑥𝑥
𝑋𝑋 → 𝑌𝑌𝑌𝑌
No exemplo apresentado, X e Y são usados para
indicar a variável (V), enquanto ‘x’ é usado para
indicar a cadeia de terminais (T*).
Além da produção das gramáticas regulares, de-
vemos nos atentar aos seus tipos. São eles:
y Gramática Linear à Esquerda (LLG - Left Linear
Grammar);
y Gramática Linear à Direita (RLG - Right Linear
Grammar).
Na Gramática Linear à esquerda, a produção deve
ocorrer do seguinte modo:
𝑋𝑋 → 𝑥𝑥𝑥𝑥
𝑋𝑋 → 𝑥𝑥
No caso apresentado, X e Y pertencem a uma
variável (V), e ‘x’ pertence a T*.
Já na Gramática Linear à direita, a produção deve
ocorrer com:
𝑋𝑋 → 𝑌𝑌𝑌𝑌
5
𝑋𝑋 → 𝑥𝑥
Sendo que X e Y pertencem a uma variável (V) e
‘x’ pertence a T*.
A linguagem regular pode ser descrita como uma
linguagem que é gerada pela gramática do tipo
3 e para a qual os autômatos finitos (FA - Finite
Automata) podem ser projetados, sendo capaz
de converter autômatos finitos em gramáticas do
tipo 3.
O exemplo na figura a seguir demonstra os autô-
matos finitos aceitando uma string que começa
com o símbolo y.
Figura 1: Autômatos finitos aceitando uma string que
começa com o símbolo y
X.V
V
X V
Fonte: Adaptado de https://pt-static.z-dn.net/files/
d29/43b2557fb7d1b9bcbf7bdcc615dc9dfa.jpg.
Assim, temos:
∑ = {𝑥𝑥, 𝑦𝑦}
𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 (𝑞𝑞𝑞) = 𝑋𝑋
6
𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸 𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 (𝐹𝐹) = 𝑌𝑌
A Gramática Linear à direita correspondente ao
autômato finito é descrita da seguinte forma:
𝑋𝑋 → 𝑦𝑦𝑦𝑦
𝑌𝑌 → ∈/𝑥𝑥𝑥𝑥/𝑦𝑦𝑦𝑦
Essa gramática pode ser escrita diretamente atra-
vés de autômatos finitos.
Figura 2: Exemplo de Gramática Linear à direita
X X X
Y Y Y Y Y Y
Є Y Y Y Y
Є Є
Fonte: Adaptado de: https://media.geeksforgeeks.org/
wp-content/uploads/20210703154210/Untitleddrawing59.
png.
Uma string pode ser gerada com a ajuda da Gra-
mática Linear à direita apresentada, que começa
com b. Depois desse b, essa string pode aceitar
qualquer símbolo de entrada (ou seja, ∑ = {𝑥𝑥, 𝑦𝑦} ).
A linguagem regular que corresponde à gramática
linear correta é descrita da seguinte forma:
7
𝐿𝐿 = {𝑦𝑦, 𝑦𝑦𝑦𝑦, 𝑦𝑦𝑦𝑦, 𝑦𝑦𝑦𝑦𝑦𝑦, 𝑦𝑦𝑦𝑦𝑦𝑦, 𝑦𝑦𝑦𝑦𝑦𝑦, 𝑦𝑦𝑦𝑦𝑦𝑦 . . . . . . }
Se invertermos a produção da Gramática Linear
à Direita acima, obteremos a seguinte gramática
𝑋𝑋 → 𝐴𝐴𝐴𝐴
𝑌𝑌 → ∈⁄𝑌𝑌 𝑥𝑥⁄𝑌𝑌 𝑦𝑦
Essa gramática deriva a linguagem que possui
todas as strings que terminam com b, que é des-
crita a seguir:
𝐿𝐿𝐿 = {𝑦𝑦, 𝑦𝑦𝑦𝑦, 𝑥𝑥𝑥𝑥, 𝑥𝑥𝑥𝑥𝑥𝑥, 𝑦𝑦𝑦𝑦𝑦𝑦, 𝑥𝑥𝑥𝑥𝑥𝑥, 𝑦𝑦𝑦𝑦𝑦𝑦 . . . . . . }
Em suma, se temos autômatos finitos que repre-
sentam a linguagem L, podemos convertê-los na
Gramática Linear à Direita, que também representa
a mesma linguagem L.
Nesse caso, quando invertemos a Gramática Linear
à Direita, obteremos a Gramática Linear à Esquerda
representando a linguagem L’, que é o inverso de L.
FIQUE ATENTO
É possível realizar a conversão de Gramática Linear à
Direita para Gramática Linear à Esquerda.
8
As etapas para realizar a conversão de Gramática
Linear à Direita na Gramática Linear à Esquerda
para a linguagem L são:
y O primeiro passo consiste em inverter os au-
tômatos finitos;
y O segundo, em escrever a gramática linear
correta para a linguagem;
y O terceiro em inverter a Gramática Linear à
Direita;
y Em seguida, será possível obter a gramática
que gera a linguagem, que é capaz de represen-
tar a Gramática Linear à Esquerda para a mesma
linguagem L.
Figura 3: Conversão de Gramática Linear à direita para
Gramática Linear à esquerda
Reverter Escrever Reverter
Autômato Autômato Gramática Gramática
Linear à Linear à
direita Esquerda
r
(L) (L)r (L)r (L)r = L
Fonte: Adaptado de: https://media.geeksforgeeks.org.
Aqui, usamos o L para descrever a linguagem para
autômatos finitos e LR para descrever a reversão
da linguagem L.
9
SAIBA MAIS
Para conhecer mais conceitos e exemplos sobre gra-
máticas regulares nos, assista aos vídeos a seguir e
leia o texto sugerido:
- Linguagens regulares, disponível em: https://youtu.
be/7v3NgFsJc90;
- Gramáticas e autômatos, disponível em: https://youtu.
be/yLmlOz_ZsHI;
- Expressões regulares, gramática regular e linguagens
regulares, disponível em: https://acervolima.com/expres-
soes-regulares-gramatica-regular-e-linguagens-regulares/.
10
GRAMÁTICAS LIVRES DE
CONTEXTO
Uma gramática livre de contexto (CFG - Context
Free Grammar) é uma notação para descrever lin-
guagens. É mais poderosa que autômatos finitos
ou expressões regulares (RE - Regular Expressions),
mas ainda não permite definir todas as linguagens
possíveis.
As gramáticas livres de contexto são úteis para
estruturas aninhadas, como parênteses em lin-
guagens de programação. A ideia básica é usar
variáveis para representar conjuntos de strings,
ou seja, idiomas. Essas variáveis, ou idioma, são
definidas recursivamente uma em função da outra.
FIQUE ATENTO
As regras recursivas, ou produções, envolvem apenas
concatenação. Já as regras alternativas para uma vari-
ável permitem a união.
As gramáticas livres de contexto podem ser clas-
sificadas com base em duas propriedades, com
base no número de strings que gera e com base
no número de árvores de derivação. Com base no
11
número de strings que gera temos as seguintes
propriedades:
y Se a gramática livre de contexto está gerando
um número finito de strings, então a gramática livre
de contexto é não recursiva (pode ser chamada
simplesmente de gramática não recursiva);
y Se a gramática livre de contexto pode gerar
um número infinito de strings, então a gramática
é chamada de gramática recursiva.
Durante a compilação, o analisador usa a gramáti-
ca da linguagem para criar uma árvore de análise,
ou árvore de derivação, a partir do código-fonte. A
gramática utilizada deve ser inequívoca. Uma gra-
mática ambígua não deve ser usada para análise.
Com base no número de árvores de derivação
temos as seguintes propriedades:
y Se houver apenas uma árvore de derivação, a
gramática livre de contexto é inequívoca;
y Se houver mais de uma derivação mais à
esquerda t ou derivação mais à direita ou árvore
de análise, então a gramática livre de contexto é
ambígua.
Analisemos a seguir alguns exemplos de gramá-
ticas recursivas e não recursivas.
Gramáticas recursivas:
12
𝑆𝑆 → 𝑆𝑆𝑆𝑆𝑆𝑆
𝑆𝑆 → 𝑏𝑏
A linguagem ou conjunto de strings gerada pela
gramática apresentada é: {𝑏𝑏, 𝑏𝑏𝑏𝑏𝑏𝑏, 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏, … } , que é infinita.
𝑆𝑆 → 𝐴𝐴𝐴𝐴
𝐴𝐴 → 𝐴𝐴𝐴𝐴|𝑐𝑐
A linguagem gerada pela gramática acima é:
{𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐𝑐𝑐, 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 … } , que é infinita.
Devemos ter em mente que uma gramática livre de
contexto recursiva, que não contém regras inúteis,
necessariamente produz uma linguagem infinita.
Gramáticas não recursivas:
𝑆𝑆 → 𝐴𝐴𝐴𝐴
𝐴𝐴 → 𝐴𝐴𝐴𝐴|𝑐𝑐
A linguagem gerada pela gramática acima é: {𝑏𝑏𝑏𝑏, 𝑐𝑐𝑐𝑐}
, que é finita.
Considerando os tipos de gramáticas recursivas
com base na natureza da recursão, uma gramática
livre de contexto recursiva pode ser novamente
dividida da seguinte forma:
13
y Gramática recursiva esquerda tendo deixado
a recursão;
y Gramática recursiva à direita tendo recursão
à direita;
y Gramática recursiva geral com recursão geral.
Um ponto importante para termos em mente é
que uma gramática linear é uma gramática livre de
contexto, que possui no máximo um não-terminal
no lado direito de cada uma de suas produções.
SAIBA MAIS
Para conhecer outras análises de conceitos e exemplos
sobre gramáticas livres de contexto, acesse os links a
seguir:
- O que é uma linguagem livre de contexto? disponível em:
https://pt.stackoverflow.com/questions/180927/o-que-
-%C3%A9-uma-linguagem-livre-de-contexto;
- Gramática livre de contexto, disponível em: https://
youtu.be/-vQUhvEVS2s;
- Gramáticas livres de contexto (GLC), disponível em:
https://youtu.be/MRXBDKeoVJI.
14
GRAMÁTICAS REGULARES
VERSUS AUTÔMATOS
FINITOS
Uma gramática regular, ou tipo três ou G, define a
linguagem chamada linguagem regular, que é acei-
ta por autômatos finitos. Esse tipo de gramática
consiste em quatro tuplas (V, T, P, S).
Já a gramática chamada de linear, é reconhecida
quando, no máximo, um não-terminal ocorre no lado
direito de qualquer regra de produção. É preciso
termos claro que existem dois tipos de gramáticas
lineares: a Gramática Linear à Direita e a Gramática
Linear à Esquerda.
Uma Gramática Linear à Direita é uma gramática
𝐺𝐺𝐺 = 𝑉𝑉, 𝑇𝑇, 𝑃𝑃, 𝑆𝑆 tal que todas as regras de produção
P são uma das seguintes formas:
𝐴𝐴 → 𝑎𝑎
𝐴𝐴 → 𝑎𝑎𝑎𝑎
Nestes casos, A e B são variáveis em V, ou seja,
A e B pertencem à variável V e a é um terminal.
O lado esquerdo da regra de produção na Gramática
Linear à direita consiste em apenas um símbolo
do conjunto de variáveis e o lado direito contém
15
cadeias de terminais ou apenas uma variável pre-
sente na posição mais à direita.
Já uma Gramática Linear à esquerda é uma gramá-
tica 𝐺𝐺𝐺 = 𝑉𝑉, 𝑇𝑇, 𝑃𝑃, 𝑆𝑆 tal que todas as regras de produção
P são uma das seguintes formas:
𝐴𝐴 → 𝑎𝑎
𝐴𝐴 → 𝐵𝐵𝐵𝐵
Aqui, A e B são variáveis em V, ou seja, A e B per-
tencem a variáveis e a é um terminal.
Em relação aos autômatos finitos, eles são o mo-
delo mais simples aceito na linguagem chamada
linguagem regular. O termo finito em autômatos
finitos significa que ele tem um número limitado
de estados e o número limitado de alfabetos nas
strings.
Um autômato finito consiste em cinco tuplas (Q,
?, q0, F, ?).
Considerando a aplicação, se G é uma gramática
regular, então L (G) é uma linguagem regular.
Assim, podemos entender como prova da aplicação
desses teoremas, o fato de as linguagens regulares
serem reconhecidas por autômatos finitos. Então,
primeiro deve-se construir um autômato finito
não-determinístico (FNA - Non-deterministic Finite
Automata) equivalente a dada gramática linear
16
correta, que aceita a linguagem definida pela dada
gramática regular G. Desse modo:
Seja 𝐺𝐺𝐺 = 𝑉𝑉, 𝑇𝑇, 𝑃𝑃, 𝑆𝑆 uma Gramática Linear à direita.
Seja 𝑉𝑉𝑉 = 𝐴𝐴𝐴𝐴𝐴𝐴 … . . 𝐴𝐴𝐴𝐴 , onde A0 é o símbolo inicial S.
Com isso, definimos um autômato finito não-de-
terminístico N = ({q0q1….qnqf},?, ?, q0, qf}), em que
o ponto de interrogação é definido como:
y Para cada produção 𝐴𝐴𝐴𝐴𝐴 → 𝑏𝑏𝑏𝑏𝑏𝑏 . Neste N, há a
transição de qi para qjQ com rótulo b;
y Para cada produção 𝐴𝐴𝐴𝐴𝐴 → 𝑏𝑏 . Neste N, há tran-
sição de qk para qf com rótulo b.
Da construção, deve ficar claro que 𝐴𝐴𝐴𝐴 → 𝑏𝑏𝑏𝑏𝑏𝑏𝑏 → 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 →
𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 → … . . → 𝑏𝑏𝑏𝑏𝑏𝑏𝑏 − 1 → 𝑏𝑏𝑏 … . 𝑏𝑏𝑏𝑏 , se, e somente se, houver um
caminho em N, partindo do estado inicial q0 e ter-
minando no estado final qf com valor de caminho
b1b2….bn. Portanto temos:
𝐿𝐿 𝐺𝐺 = 𝑇𝑇 𝑁𝑁
Observemos um exemplo a seguir:
Seja 𝐺𝐺𝐺 = 𝑉𝑉, 𝑇𝑇, 𝑃𝑃, 𝑆𝑆 uma gramática regular, onde:
𝑉𝑉𝑉 = 𝐴𝐴𝐴, 𝐴𝐴𝐴, 𝐴𝐴𝐴
𝑇𝑇𝑇 = 0, 1
Sendo S o símbolo inicial da gramática e P o con-
junto de regras de produção definido como:
17
𝐴𝐴𝐴𝐴 → 0𝐴𝐴𝐴
𝐴𝐴𝐴𝐴 → 1𝐴𝐴𝐴
𝐴𝐴𝐴𝐴 → 0𝐴𝐴𝐴
𝐴𝐴𝐴𝐴 → 0
Ao construir um autômato finito que aceite a
linguagem gerada por uma dada gramática G, a
solução seria:
𝑀𝑀𝑀 = 𝑄𝑄, ? , 𝑞𝑞𝑞, 𝐹𝐹, ? um autômato finito que aceita
L (G), onde:
𝑄𝑄𝑄 = 𝑞𝑞𝑞, 𝑞𝑞𝑞, 𝑞𝑞𝑞, 𝑞𝑞𝑞𝑞
? = 0, 1
Sendo q0 o estado inicial, temos:
𝐹𝐹𝐹 = 𝑞𝑞𝑞𝑞
Os estados q0, q1, q2 correspondem a A0, A1, A2
e qf que é o novo estado final de M.
Inicialmente temos quatro estados de autômatos
finitos M.
A regra de produção A0 � 0A1 inclui uma transição
de q0 para q1 com rótulo 0.
A regra de produção A0 � 1A2 inclui uma transição
de q0 para q2 com rótulo 1.
18
A regra de produção A1 � 0A2 inclui uma transição
de q1 para q2 com rótulo 0.
Similarmente, para a regra de produção A2 � 0
inclui uma transição de q2 para qf com rótulo 0.
Após esta regra de produção teremos um diagrama
final de autômatos finitos aceitando L(G).
SAIBA MAIS
Explore mais conceitos e exemplos sobre gramáticas
regulares e autômatos finitos no link abaixo:
Introdução às linguagens formais e autômatos/Lingua-
gens regulares
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%-
C3%A0s_Linguagens_Formais_e_Aut%C3%B4matos/
Linguagens_Regulares.
19
TRANSFORMAÇÕES
GRAMATICAIS
As expressões regulares (RegEx) podem ser um
trabalho muito desafiador. Mesmo os profissionais
mais experientes podem ter dificuldade neste
contexto. Portanto, existem diversas ferramentas
desenvolvidas para facilitar a atuação de profis-
sionais nesta área extremamente técnica.
Importacular, por exemplo, é uma ferramenta gra-
tuita de importação e exportação de expressões
regulares. Com ela, é possível exportar dados de
expressões regulares diretamente para as fontes
de dados desejadas.
Ela proporciona ao usuário a capacidade de trans-
formar os dados recebidos de um valor em outro.
No início da Importacular, isso era simplesmente um
valor “de” e um valor “para” e se o valor de entrada
correspondesse ao “de” ele mudaria para “para”.
Esse processo é muito simples e eficaz. Entretanto,
desenvolvedores perceberam que seria necessário
mais poder, então a Importacular adicionou cor-
respondências parciais, ou correspondências de
palavras, esclarecendo que o original seria uma
correspondência mais exata.
20
Foram adicionados, então, diferentes tipos de
substituições, como “complete” e “partial” e depois
“append” e “prepend”. Assim, se o “complete” foi
selecionado, todo o valor de entrada foi substituído
pelo valor de substituição. Se o “partial” foi selecio-
nado, então apenas a parte correspondente seria
substituída, mantendo o restante do valor original.
Enquanto, o “append” e “prepend” adicionariam o
texto de substituição ao final ou ao início do origi-
nal, respectivamente. Em seguida, é adicionado à
expressão regular primeiro para correspondência
e depois para substituição.
A Importacular percorre cada linha na grade de
transformação de dados e continua por elas, a
menos que o sinalizador de parada de processa-
mento tenha sido definido.
Se um tipo de correspondência de expressão re-
gular for escolhido, podemos colocar a expressão
regular na célula “From source” e a Importacular
tentará fazer a correspondência.
Por exemplo, podemos usar a expressão regular
abaixo:
.∗
Com isso, a Importacular corresponderá a qualquer
número de qualquer caractere, ou seja, sempre
corresponderá ao que for encontrado.
21
Se usarmos a seguinte expressão regular:
𝐵𝐵[𝑎𝑎 − 𝑧𝑧]𝑔𝑔
Ele corresponderá a “Bag”, “Big”, “Bog” e “Bkg”,
assim como todas as letras de A a Z.
Se uma correspondência for encontrada, haverá a
tentativa de substituir o valor. Assim, para substituir
a expressão regular, haverá duas coisas a serem
observadas:
1) Não importa como a partida foi feita. Pode ser
uma expressão regular, uma correspondência com-
pleta, parcial ou de palavras, substituir independe
de como a correspondência foi feita;
2) A Importacular não usa o mecanismo clássico
de substituição da expressão regular, ou seja, ela
não cria um grupo de captura (o que geralmente
é feito usando parênteses ou, às vezes, barra e
parênteses) para, em seguida, fazer referência a
esse grupo com o símbolo de cifrão, por exemplo
$1 ou $2. A Importacular não utiliza este método,
mas usa outras técnicas para garantir que os dados
sejam normalizados e que as estruturas de tabelas
sejam mantidas.
O “replace” da Importacular funciona ao selecionar
o valor de entrada e ao aplicá-lo à expressão regular
para ele extrair um valor. Esse valor é então usado
22
como o texto de substituição. Por exemplo, se o
valor recebido for:
“Recurso Anual 2022”
Então podemos extrair o ano usando a expressão
regular:
^20[0 − 9][0 − 9]
É importante termos claro que que há várias ma-
neiras diferentes de obter as mesmas informações
usando uma expressão regular, esta é apenas uma
delas.
Outro exemplo seria se buscássemos obter o
código de áreas de um número de telefone dos
Estados Unidos. O número de telefone está em
dois formatos diferentes: (415)-666-999 ou 415-
666-999. Assim, podemos extrair o código de área
usando a seguinte expressão:
(? <=)[0 − 9]{3}|^[0 − 9]{3}
Para melhorar a eficácia, podemos usar uma se-
gunda linha na transformação para transformar o
código de área da cidade. Nesse caso, depois de
extrair “415”, poderíamos transformar para “São
Francisco”.
A parte mais difícil de usar expressões regulares
no Importacular é realmente a própria expressão
regular. Além dessa ferramenta, é possível usar
23
o site RegExr para testar uma correspondência e
substituir a extração antes de colocá-la na grade
de transformação.
Uma vez na grade de transformação, também é
possível verificarmos a tela de revisão e anali-
sarmos o êxito, pois o valor resultante aparecerá
transformado, se tudo ocorrer como esperado.
SAIBA MAIS
Para conhecer mais exemplos sobre transformações
gramaticais, consulte os links a seguir:
- RegExp (Expressões Regulares), disponível em: https://
youtu.be/IVcbytKjL4U;
- Gramática Regular e transformações, disponível em:
https://youtu.be/CzaVNvWMXz0;
- Como transformar uma gramática livre de contexto
em um autômato de pilha?
https://pt.stackoverflow.com/questions/243105/como-
-transformar-uma-gram%C3%A1tica-livre-de-contexto-
-em-um-aut%C3%B4mato-de-pilha.
24
FORMAS NORMAIS
Um banco de dados é geralmente uma coleção de
informações ou dados organizados e armazenados
em tabelas com esforços feitos para garantir sua
precisão e facilidade de recuperação.
Durante o processo de design de um sistema de
gerenciamento de banco de dados, ou DBMS (Data
Base Management System), é de extrema impor-
tância que a disposição das tabelas e a relação
entre elas estejam corretas.
A maneira como os dados são adicionados, edita-
dos e excluídos também é um fator que deve ser
levado em consideração, além de sua estrutura,
colunas e linhas.
Desse modo, é importante destacarmos o papel
da normalização, que é o processo de remoção de
incidências existentes ou passíveis de anomalias,
redundâncias de dados e imprecisão de dados em
um banco. Isso limita as tabelas a uma finalidade
ou entidade específica.
Em um hotel, por exemplo, um quarto é uma área
privativa exclusiva para apenas um hóspede regis-
trado por vez e não deve funcionar como passagem
para o spa ou ser acessível por mais de um cliente
do spa. Regras como essa, no projeto do sistema
de gerenciamento de banco de dados, foram de-
25
senvolvidas para organizar melhor as tabelas e
minimizar anomalias.
Em suma, nos bancos de dados relacionais, espe-
cialmente os grandes, é necessário organizar as
entradas para que outros mantenedores e admi-
nistradores possam realizar a leitura para trabalhar
nelas. É por esse motivo que a normalização do
banco de dados é importante.
Simplificando, a normalização do banco de dados
envolve a organização de um banco em várias
tabelas para reduzir a redundância. Podemos
projetar um banco de dados para seguir qualquer
um dos tipos de normalização, como 1NF (Normal
Form - ou Forma Normal), 2NF e 3NF.
É preciso termos claro, que a normalização de
um banco de dados é um princípio do design de
banco de dados para organizar dados de maneira
adequada e consistente. Esse tipo de ação ajuda
a evitar redundância e manter a integridade do
banco de dados, além de auxiliar na eliminação de
características indesejáveis associadas à inserção,
exclusão e atualização.
Assim, compreendemos que o principal objetivo da
normalização do banco de dados é evitar comple-
xidades, eliminar duplicatas e organizar os dados
de maneira consistente.
26
Na normalização, os dados são divididos em várias
tabelas vinculadas por relacionamentos, sendo
que os administradores dos bancos são capazes
de obter esses relacionamentos usando chaves
primárias, estrangeiras e compostas.
Pensando na consolidação desta ação, uma chave
primária em uma tabela, por exemplo, Funciona-
rios_Salarios está relacionada ao valor de outra
tabela, por exemplo, Funcionarios_dados.
É preciso termos em mente que uma chave primária
é uma coluna que identifica de forma única as linhas
de dados de uma tabela. Ela é um identificador
exclusivo, como uma identificação de funcionário,
carteira de estudante, número de identificação do
eleitor, CPF e assim por diante.
Uma chave estrangeira é um campo relacionado
também à chave primária, mas em outra tabela.
Já uma chave composta é como uma chave pri-
mária, mas em vez de ter uma coluna, ela tem
várias colunas.
Em relação aos tipos de normatização de banco
de dados, temos os três primeiros: 1FN, 2FN e
3FN. Eles representam a primeira forma normal, a
segunda forma normal e a terceira forma normal,
respectivamente.
27
Existe também a 4FN (quarta forma normal), 5FN
(quinta forma normal) e até 6FN (sexta forma
normal), mas a forma normal mais comum que
encontramos é a 3FN (terceira forma normal).
Todos os tipos de normalização de banco de
dados são cumulativos, o que significa que cada
um é construído sobre os que estão abaixo dele.
Portanto, todos os conceitos da 1FN também são
transferidos para a 2FN e assim por diante.
Para que uma tabela esteja na primeira forma
normal, ela deve atender aos seguintes critérios:
y Uma única célula não deve conter mais de um
valor, conferindo atomicidade a ela;
y Deve haver uma chave primária para identificação;
y Não pode haver linhas ou colunas duplicadas;
y Cada coluna deve ter apenas um valor para
cada linha da tabela.
Além disso, é preciso termos claro que a 1FN eli-
mina apenas grupos repetitivos, não redundância.
É por isso que existe a 2FN.
Podemos afirmar que uma tabela está na 2FN, se
atender aos seguintes critérios:
y Se já está na 1FN;
y Se não tem dependência parcial. Ou seja, todos
os atributos não-chave são totalmente dependentes
de uma chave primária.
28
Quando uma tabela está na 2FN, ela elimina gru-
pos repetitivos e redundância, mas não elimina a
dependência parcial transitiva. Isso significa que
um atributo não primo, um atributo que não faz
parte da chave do candidato, depende de outro
atributo não primo e é, justamente, esse aspecto
que a terceira forma normal elimina. Então, para
uma tabela estar na 3FN, ela deve:
y Estar em 2FN;
y Não tem dependência parcial transitiva.
Ainda sobre a normalização do banco de dados,
é preciso termos claro que ela é bastante técnica.
Imaginemos a construção de um aplicativo de ge-
renciamento de restaurante. Ele precisa armazenar
dados sobre os funcionários da empresa, assim
ela começa com uma tabela de funcionários, como
observamos a seguir:
Tabela 1: Exemplo de forma normal 1
ID_Fun- Nome Codigo_ Funcao Codigo_ Estado_
cionario Funcao Estado Base
E001 Maria J01 Cozi- 11 Sao
nheira Paulo
E001 Maria J02 Garco- 11 Sao
nete Paulo
E002 Luiz J02 Garcom 21 Rio de
Janeiro
E002 Luiz J03 Barten- 21 Rio de
der Janeiro
29
E003 Maria J01 Cozi- 21 Rio de
nheira Janeiro
Fonte: Adaptado de: https://www.youtube.com/
watch?v=eRaAMNjCFYw&t=266s.
Todas as entradas são atômicas e há uma chave
primária composta, como ID_Funcionario e Codi-
go_Funcao, para que a tabela esteja na primeira
forma normal 1, ou 1FN.
Mesmo que saibamos apenas o ID_Funcionario de
alguém, poderemos determinar o nome, Estado_Base
e Codigo_Estado, porque eles devem ser a mesma
pessoa. Isso significa que Nome, Estado_Base e
Codigo_Estado dependem de ID_Funcionario, que
é uma parte da chave composta primária.
Portanto, a tabela não está na 2FN. Assim, devemos
separá-los em uma tabela diferente para torná-la
2FN. Observemos o exemplo a seguir:
Tabela 2: Exemplo de forma normal 2
- Funcionario_Funcao
ID_Funcionario Codigo_Funcao
E001 J01
E001 J02
E002 J02
E002 J03
E003 J01
E001 J01
Fonte: Adaptado de: https://www.youtube.com/
watch?v=6ER9lWOk-cY&t=1s.
30
Tabela 3: Exemplo de forma normal 2 – Funcionário
ID_Funcio- Nome Codigo_Es- Estado_Base
nario tado
001 Maria 11 São Paulo
E002 Luiz 21 Rio de
Janeiro
Rio de Rio de Rio de Rio de
Janeiro Janeiro Janeiro Janeiro
Fonte: Adaptado de: https://www.youtube.com/
watch?v=6ER9lWOk-cY&t=1s.
Tabela 4: Exemplo de forma normal 2 - Função
Codigo_Funcao Funcao
J01 Cozinheiro(a)
J02 Garcom/Garconete
J03 Bartender
Fonte: Adaptado de: https://www.youtube.com/
watch?v=6ER9lWOk-cY&t=1s.
Assim, estado_Base agora depende de Codigo_Es-
tado. Portanto, se conhecermos o Codigo_Estado,
poderemos encontrar o valor do Estado_Base.
Para dar um passo adiante, para a forma normal 3,
devemos separar os dados em uma tabela diferente.
Tabela 5: Exemplo de forma normal 3
- Funcionario_Funcao
ID_Funcionario Codigo_Funcao Funcao
E001 J01 Cozinheiro(a)
E001 J02 Garcom/Garconete
E002 J02 Garcom/Garconete
31
E002 J03 Bartender
E003 J01 Cozinheiro(a)
Fonte: Adaptado de: https://www.youtube.com/
watch?v=usA8QKvEHWw&t=1s.
Tabela 6: Exemplo de forma normal 3 - Funcionario
ID_Funcionario Nome Codigo_Estado
E001 Maria 11
E002 Luiz 21
E003 Maria 31
Fonte: Adaptado de: https://www.youtube.com/
watch?v=usA8QKvEHWw&t=1s.
Tabela 7: Exemplo de forma normal 3 - Funcao
Codigo_Funcao Funcao
J01 Cozinheiro(a)
J02 Garcom/Garconete
J03 Bartender
Fonte: Fonte: Adaptado de: https://www.youtube.com/
watch?v=usA8QKvEHWw&t=1s.
Tabela 8: Exemplo de forma normal 3 - Estado
Codigo_Estado Estado_Base
11 Sao Paulo
21 Rio de Janeiro
Fonte: Fonte: Adaptado de: https://www.youtube.com/
watch?v=usA8QKvEHWw&t=1s.
Dessa forma, a base de dados está em 3FN.
32
SAIBA MAIS
Ainda sobre formas normais, explore mais análises dos
conceitos e exemplo, acesse os links a seguir:
- Forma Normal de Chomsky, disponível em: https://
youtu.be/QE2bbLI5Ez8;
- Forma Normal de Greibach, disponível em: https://
youtu.be/OsO_v6A2xCo;
- Formas Normais, disponível em: https://jkolb.com.br/
formas-normais/.
33
EXEMPLOS E
DEMONSTRAÇÕES
Na teoria dos autômatos, há diversas formas de
realizar transformações gramaticais, sendo que o
ponto mais importante a ser considerado nelas é
que a qualidade da linguagem deve ser mantida a
todo custo quando uma transformação é realizada.
Em relação à gramática simplificada temos que
ela é livre de contexto, é caracterizada por não
apresentar símbolos desnecessários, produções
vazias, ou produções do tipo A � B.
A simplificação ocorre primeiramente ao excluir
as produções vazias, então são excluídas as pro-
duções da forma A � B, e finalmente, os símbolos
desnecessários.
Para realizar a exclusão de produções vazias,
precisamos considerar as variáveis que as consti-
tuem e, então, devemos realizar a exclusão dessas
produções.
Observemos a seguir, a inclusão de geração de
palavra vazia, caso necessário:
y 𝐺𝐺 = ({𝑆𝑆, 𝑋𝑋, 𝑌𝑌}, {𝑎𝑎, 𝑏𝑏}, 𝑃𝑃, 𝑆𝑆) , sendo;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏 | ∈, 𝑋𝑋 → 𝑎𝑎 | 𝑏𝑏 | 𝑌𝑌, 𝑌𝑌 → ∈} ;
y Conjunto de variáveis que geram є:
34
A partir disso, analisemos as tabelas a seguir:
Tabela 9: Análise das variáveis
iteração variáveis
0 Ø
1 {S, Y}
2 {S, Y, X}
3 {S, Y, X}
Fonte: https://docplayer.com.br/131660190-Linguagens-
-formais-e-automatos-simplificacao-de-gramaticas-livre-
-do-contexto-glc.html.
Observemos os conjuntos sem produções vazias:
Tabela 10: Conjuntos sem produções vazias
iteração produções
0 {S � aXa | bXb, X � a | b | Y}
1 {S � aXa | bXb | aa | bb, X � a
| b | Y}
2 {S � aXa | bXb | aa | bb, X � a
| b | Y}
Fonte: https://docplayer.com.br/131660190-Linguagens-
-formais-e-automatos-simplificacao-de-gramaticas-livre-
-do-contexto-glc.html.
Caso seja necessário incluir palavra vazia neste
caso, o procedimento será o seguinte:
𝐺𝐺 = ({𝑆𝑆, 𝑋𝑋, 𝑌𝑌}, {𝑎𝑎, 𝑏𝑏}, 𝑃𝑃, 𝑆𝑆)
y , sendo;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏 | 𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏 | ∈, 𝑋𝑋 → 𝑎𝑎 | 𝑏𝑏 | 𝑌𝑌} .
35
O próximo passo será a exclusão das produções da
forma A � B. Caso a variável A possa ser substitu-
ída pela variável B, então teremos o seguinte caso:
y Se B � α;
y Então a produção A � B;
y Pode ser substituída por A � α.
Analisemos um exemplo prático com construção
de fecho e exclusão de produções A � B:
y 𝐺𝐺 = ({𝑆𝑆, 𝑋𝑋}, {𝑎𝑎, 𝑏𝑏}, 𝑃𝑃, 𝑆𝑆) , sendo;
y ;
𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏, 𝑋𝑋 → 𝑎𝑎 | 𝑏𝑏 | 𝑆𝑆 | Ø}
y Construção do fecho de cada variável:
y Fecho-S = Ø;
y Fecho-X = {S}.
Tabela 11: Exclusão de produções A � B
iteração produções
0 {S � aXa | bXb, X � a | b | S
| є}
S {S � aXa | bXb, X � a | b | S
| є}
X {S � aXa | bXb, X � a | b | aXa
| bXb | є}
Fonte: Adaptado de: https://docplayer.com.br/
131660190-Linguagens-formais-e-automatos-simplifica-
cao-de-gramaticas-livre-do-contexto-glc.html.
y 𝐺𝐺 = ({𝑆𝑆, 𝑋𝑋}, {𝑎𝑎, 𝑏𝑏}, 𝑃𝑃, 𝑆𝑆) , sendo;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏, 𝑋𝑋 → 𝑎𝑎 | 𝑏𝑏 | 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏 | ∈} .
36
Por último, temos a exclusão de símbolos des-
necessários, que não são usados na geração de
palavras terminais. Portanto, a exclusão ocorrerá
ao eliminar produções que se referem a estes
símbolos, bem como, os próprios símbolos.
y 𝐺𝐺 = ({𝑆𝑆, 𝐴𝐴, 𝐵𝐵, 𝐶𝐶}, {𝑎𝑎, 𝑏𝑏, 𝑐𝑐}, 𝑃𝑃, 𝑆𝑆) , onde;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎 | 𝑏𝑏𝑏𝑏𝑏𝑏, 𝐴𝐴 → 𝑎𝑎 | 𝑆𝑆, 𝐶𝐶 → 𝑐𝑐} ;
Além disso, qualquer variável gera palavra de ter-
minais. Observemos na tabela a seguir:
Tabela 12: Exclusão de símbolos desnecessários
iteração produções
0 Ø
1 {A, C}
2 {A, C, S}
3 {A, C, S}
Fonte: Adaptado de https://docplayer.com.br/
131660190-Linguagens-formais-e-automatos-simplifica-
cao-de-gramaticas-livre-do-contexto-glc.html.
Então, temos:
y 𝐺𝐺 = ({𝑆𝑆, 𝐴𝐴, 𝐶𝐶}, {𝑎𝑎, 𝑏𝑏, 𝑐𝑐}, 𝑃𝑃, 𝑆𝑆) , onde;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎, 𝐴𝐴 → 𝑎𝑎 | 𝑆𝑆, 𝐶𝐶 → 𝑐𝑐} ;
y 𝐺𝐺 = ({𝑆𝑆, 𝐴𝐴, 𝐶𝐶}, {𝑎𝑎, 𝑏𝑏, 𝑐𝑐}, 𝑃𝑃, 𝑆𝑆) , onde;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎, 𝐴𝐴 → 𝑎𝑎 | 𝑆𝑆, 𝐶𝐶 → 𝑐𝑐} ;
Sendo que qualquer símbolo é atingido por meio
do símbolo inicial.
37
Tabela 13: Análise das variáveis
iteração variáveis terminais
0 {S} Ø
1 {S, A} {a}
2 {S, A} {a}
Fonte: Adaptado de: https://docplayer.com.br/
131660190-Linguagens-formais-e-automatos-simplifica-
cao-de-gramaticas-livre-do-contexto-glc.html
y 𝐺𝐺 = ({𝑆𝑆, 𝐴𝐴}, {𝑎𝑎}, 𝑃𝑃, 𝑆𝑆) ,
onde;
y 𝑃𝑃 = {𝑆𝑆 → 𝑎𝑎𝑎𝑎𝑎𝑎, 𝐴𝐴 → 𝑎𝑎 | 𝑆𝑆}1 (LEHRER).
SAIBA MAIS
Para mais exemplos e demonstrações práticas relaciona-
das aos tópicos desta unidade, acesse os links a seguir:
- Gramática regular, disponível em: https://youtu.
be/9fPaBOxfhM8;
- Gramáticas livres de contexto, disponíveis em: https://
youtu.be/EeWTxEOfLtw e https://youtu.be/nN2v4e6USgc;
- Formas normais, disponíveis em: https://youtu.be/
eRA45FHrt8o e https://youtu.be/VQ-0x21bAMo.
38
CONSIDERAÇÕES FINAIS
Neste e-book, apresentamos as concepções básicas
sobre as transformações gramaticais. Também
conhecemos os conceitos sobre gramáticas re-
gulares, livres de contexto e a relação das gramá-
ticas regulares com os autômatos finitos, além de
transformações gramaticais e formas normais.
Compreendemos que uma gramática é um con-
junto de regras para juntar strings, as cadeias de
caracteres e, portanto, corresponde a uma lingua-
gem. Uma gramática consiste em um conjunto de
variáveis, também chamadas de não-terminais,
uma das quais é designada como variável inicial.
Assim, devemos ter em mente que uma gramática
é composta por terminais, variáveis e regras de
produção.
Discutimos também o conceito de gramáticas livres
de contexto, que é uma notação para descrever
linguagens e é mais poderosa que autômatos
finitos ou expressões regulares, mas ainda não
permite definir todas as linguagens possíveis. As
gramáticas livres de contexto são úteis para estru-
turas aninhadas, como parênteses em linguagens
de programação.
Tratamos sobre as gramáticas regulares e sua
relação com autômatos finitos. Uma gramática
regular, ou tipo três, define a linguagem chamada
linguagem regular, que é aceita por autômatos
finitos. Enquanto que na gramática chamada de
linear, no máximo um não-terminal pode ocorrer
39
no lado direito de qualquer regra de produção. Por
isso, é importante termos claro que há dois tipos
de Gramática Linear, a à direita e à esquerda.
Analisamos também conceitos sobre as transfor-
mações gramaticais, notando que existem diversas
ferramentas desenvolvidas para facilitar a atuação
de profissionais nesta área. Importacular, por
exemplo, é uma delas e é gratuita para importa-
ção e exportação de expressões regulares. Com
ela, é possível exportarmos dados de expressões
regulares diretamente para as fontes de dados
desejadas. Assim, é preciso termos em mente que
a parte mais difícil de usar expressões regulares
no Importacular é realmente a própria expressão
regular.
Por fim, discutimos conceitos de formas normais.
Analisamos que em bancos de dados relacionais,
especialmente os grandes, é necessário organizar
as entradas para que outros mantenedores e admi-
nistradores possam realizar a leitura para trabalhar
nelas. É por esse motivo que a normalização do
banco de dados é importante.
Simplificando, a normalização do banco de dados
envolve a organização de um banco de dados em
várias tabelas para reduzir a redundância. É possível
projetar o banco de dados para seguir qualquer um
dos tipos de normalização como forma normal 1,
forma normal 2 ou forma normal 3.
40
Referências Bibliográficas
& Consultadas
DIVERIO, T. A; MENEZES, P. B. Teoria
da computação: máquinas universais e
computabilidade. Editora Grupo A, 2009. [Minha
Biblioteca]
LEHRER, C. Simplificação de Gramáticas Livre
do Contexto (GLC). Disponível em: https://
docplayer.com.br/131660190-Linguagens-
formais-e-automatos-simplificacao-de-
gramaticas-livre-do-contexto-glc.html. Acesso
em: 06 abr. 2023.
MELO, A. V. Princípios de linguagem de
programação. 3 ed. Editora Blucher, 2014.
[Biblioteca Virtual]
MENEZES, P. B. Linguagens formais e
autômatos. v. 3, 6 ed. Bookman. 2010. [Minha
Biblioteca]
SANTOS, P. R. Compiladores: da teoria à prática.
Editora Grupo GEN, 2018. [Minha Biblioteca]
SEBESTA, R. Conceitos de linguagens de
programação. 11 ed. Editora Grupo A, 2018.
[Minha Biblioteca]
SILVA, F. S. C.; MELO, A. C. V. Modelos clássicos
de computação. 1 ed. Editora Cengage Learning
Brasil, 2006. [Minha Biblioteca]
SIPSER, M. Introdução à teoria da computação.
2 ed. Editora Cengage Learning Brasil, 2007.
[Biblioteca Virtual]
SOUSA, C. E. B. et al. Linguagens formais e
autômatos. Editora Grupo A, 2021. [Minha
Biblioteca]
