LivoLinguagensAutomatosFomais

Prévia do material em texto

LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Definir o formalismo de gramática regular.
 > Apresentar os passos de derivação em gramáticas regulares.
 > Exemplificar a construção de gramáticas regulares.
Introdução
Uma gramática consiste em um mecanismo bastante simples para definir 
um conjunto de símbolos válidos para uma linguagem e suas regras. Toida 
(2013) afirma que uma gramática é um conjunto de regras de reescrita que 
são usadas para gerar palavras reescrevendo sucessivamente os símbolos de 
um determinado alfabeto. 
Dito isto, as gramáticas regulares são a forma mais simples de gramáticas, 
assim, por meio delas é possível representar linguagens regulares que represen-
tam todas as linguagens do tipo 3 na hierarquia de Chomsky (1956). No entanto, 
essa simplicidade caracterizada nas linguagens regulares, apesar de possuir 
grandes restrições, possibilita uma vasta gama de aplicações; desse modo, 
é possível aplicar essas linguagens em semáforos, sistemas de geração de senhas 
de atendimento e até mesmo na análise léxica de linguagens de programação.
Neste capítulo, você vai ver o que é uma gramática, identificar o formalismo 
de uma gramática regular, como ocorre a representação de uma linguagem 
regular a partir de uma gramática regular, como derivar gramáticas regulares 
e, por fim, como construir gramáticas regulares. 
Gramáticas 
regulares
Carlos Estevão Bastos Sousa
O formalismo da gramática regular
Quando tratamos de linguagens regulares, podemos fazer uso de gramáticas 
regulares para defini-las. Neste sentido, podemos afirmar que uma linguagem 
é regular se pode ser gerada por alguma gramática regular.
De acordo com Ricarte (2008), as gramáticas regulares, embora bastante 
limitadas, são muito utilizadas para a representação de aspectos importantes 
de linguagens de programação. Consideremos por exemplo a definição de 
identificadores utilizados para representar nomes de variáveis e de funções. 
Neste sentido, um identificador, para ser válido, necessita ser uma palavra 
iniciada por um caractere que é uma letra, e, após esta, poderão existir outros 
caracteres que podem ser letras ou dígitos.
Conforme Menezes (2011), uma gramática é basicamente um conjunto de 
regras que, quando aplicadas sucessivamente, geram palavras. Deste modo, 
podemos afirmar que o conjunto de todas as palavras geradas por uma de-
terminada gramática define uma linguagem. Matsuno (2006) complementa 
apresentando que uma gramática, em um sentido geral, é um formalismo 
que define regras que geram sentenças de uma linguagem sobre conjunto 
de símbolos. 
Disto isto, podemos apresentar uma gramática como uma quádrupla da 
forma:
G = (V, T, P, S) 
onde:
 � V é o conjunto de símbolos variáveis ou variáveis não terminais; 
 � T é o conjunto de símbolos terminais, de forma que T ∩ V = ∅, ou seja, 
T e V são disjuntos;
 � P é o conjunto de regras, ou seja, as produções. Este caracteriza-se 
por ser uma relação finita, no qual P é um conjunto finito de pares em 
que cada par é reconhecido como uma regra ou produção;
 � S é símbolo não terminal, denominado símbolo inicial ou variável inicial.
É possível encontrar na literatura gramáticas representadas por 
outros símbolos/letras, desta forma, neste documento optamos por 
representá-las da forma G = (V, T, P, S).
Gramáticas regulares2
Ricarte (2008) apresenta que uma gramática para uma linguagem deve 
incluir, além da especificação do seu alfabeto, um conjunto de produções 
dado por uma relação representada pelo símbolo →, o qual indica que o lado 
esquerdo da relação pode ser substituído pelo direito, de forma que cada 
produção determina uma regra com o intuito de transformar uma sequência de 
símbolos em outra. Deste modo, considerando uma regra de produção (α, β), 
ela pode ser representada por:
α → β
Assim, um conjunto de regras de produção para gramáticas regulares 
pode ser descrito por:
α → β1, α → β2, …, α → βn
Pode-se ainda abreviar como:
α → β1|β2|…|βn
Seguindo este conceito, existe um tipo de gramática que restringe regras 
de produção de modo a definir apenas linguagens regulares. Essas gramáticas 
estão presentes na maioria das linguagens de programação e possibilitam 
a construção de identificadores, tipos de dados, entre outros. No exemplo a 
seguir, é apresentada uma gramática regular que possibilita a produção de 
qualquer número natural.
S → 0|1|2|3|4|5|6|7|8|9|0S|1S|2S|3S|4S|5S|6S|7S|8S|9S
Salienta-se que dizemos que uma gramática, normalmente abreviada por 
GR, é regular se também for uma gramática linear à direita ou uma gramática 
linear à esquerda. Essas gramáticas possuem restrições quanto ao seu formato 
de construção e podem ser divididas em quatro formas:
 � gramáticas lineares à direita (GLD);
 � gramáticas lineares à esquerda (GLE);
Gramáticas regulares 3
 � gramáticas lineares unitárias à direita (GLUD);
 � gramáticas lineares unitárias à esquerda (GLUE).
Vejamos a seguir uma breve apresentação de cada uma das gramáticas 
lineares citadas. Estas são apresentadas com base no trabalho de Menezes 
(2011).
Gramáticas lineares à direita (GLD)
Seja G = (V, T, P, S) uma gramática na qual A, B ∈ V e w ∈ T*, nas gramáticas 
lineares à direita, todas as regras de produção são da forma:
A → wB ou A → w
Isto posto, note que o lado esquerdo só possui uma variável. Ao lado 
direito temos a produção, que pode, ou não, possuir apenas uma variável. 
Vejamos:
Dada uma linguagem L que corresponde a todas as palavras que iniciam 
com o símbolo a e que pode, ou não, possuir diversas sequências de ba, deno-
tada pela expressão regular a(ba)*, a gramática linear à direita corresponde a 
G = ({S, A}, {a, b}, P, S)} de forma que:
 � S, A são símbolos não terminais;
 � a e b são símbolos terminais;
 � S é o símbolo de início tal que S ∈ V;
 � P possui as seguintes regras de produção:
S → aA
A → baA|ε
Note que, nesse caso, iniciamos a nossa gramática com o símbolo S, que 
possui como regra a leitura do terminal a e da variável A. Na regra seguinte, 
temos que A representa baA ou ε, assim, no primeiro caso, é possível de 
forma recursiva ler diversos conjunto de símbolos ba ou, no segundo caso, 
encerrar a produção com uma palavra vazia, ε.
Gramáticas regulares4
Com relação às linguagens de programação, as gramáticas regulares 
definem o formato em que poderão ser escritos os elementos léxicos. 
Isto é, os nomes de identificadores, as palavras reservadas, os operadores, etc.
Gramáticas lineares unitárias à direita (GLUD)
De forma semelhante as GLDs, as GLUDs possuem regra de produção na forma:
A → wB ou A → w
no entanto, de forma adicional, temos:
|w| ≤ 1
Deste modo, ainda sobre a expressão a(ba)*, a GLUD corresponde a 
G = ({S, A, B}, {a, b} P, S) com P possuindo a seguinte produção:
S → aA
A → bB|ε
B → aA
Note que neste tipo de gramática há apenas um símbolo terminal para 
cada regra desenvolvida.
Gramáticas lineares à esquerda (GLE)
De forma oposta às gramáticas anteriormente apresentadas, nas GLEs todas 
as regras de produção são da forma:
A → Bw ou A → w
ou seja, neste tipo de gramática a variável, se existir, é inserida no lado 
esquerdo do terminal.
Gramáticas regulares 5
Deste modo, ainda considerando a expressão regular a(ba)*, temos 
G = ({S}, {a, b} P, S) e P como:
S → a
S → Sba
Perceba no caso abordado que, diferentemente das GLDs e das GLUDs, 
as GLEs possuem variáveis do lado esquerdo do terminal.
Gramáticas lineares unitárias à esquerda (GLUE)
De forma semelhante às GLEs, essas gramáticas possuem como regra:
A → Bw ou A → w
no entanto, tal qual as GLUDs, temos:
|w| ≤ 1
ou seja, há apenas um símbolo terminal para cada regra desenvolvida.
Neste caso, ainda sobre a expressão a(ba)*, temos G = ({S, A}, {a, b} P, S). 
Vejamos as regras de produção para a expressão dada:
S → a|Aa
A → Sb
Apesar de as gramáticas apresentadas possuírem um formato diferente 
de produção, estas são equivalentes e, portanto, podem denotar a mesma 
linguagem. Analise a explicaçãoa seguir.
Equivalência para as gramáticas regulares
Conforme Menezes (2011), ao considerar L uma linguagem, esta é gerada 
por uma GLD se — e somente se — também for gerada por uma GLE, se — 
e somente se — for gerada por uma GLUD e, finalmente, se — e somente 
se — for gerada por uma GLUE. Dito isto, as diversas formas de gramáticas 
lineares apresentadas possuem formalismos equivalentes. Note que isso foi 
exemplificado ao apresentar as quatro gramáticas lineares para uma mesma 
expressão regular, a(ba)*.
Gramáticas regulares6
Conforme Coutinho e Schechter (2016), as gramáticas regulares também 
são chamadas de gramáticas lineares à direita. No entanto, como visto, 
os quatro modelos de linguagens lineares aqui apresentados são equivalentes. 
Como forma de padronizar os exemplos aqui utilizados, apresentaremos, 
a partir daqui, apenas as gramáticas com este formato.
Derivação em gramáticas regulares
Conforme apresentado, a aplicação de um conjunto de regras de produção 
é denominada derivação. Deste modo, a aplicação sucessiva de regras de 
produção permite derivar todas as palavras de uma determinada linguagem 
representada pela gramática. 
Considerando uma gramática G, conforme Menezes (2011), dizemos que 
uma linguagem gerada por esta gramática pode ser denotada por:
L(G) ou GERA(G) 
tal que:
L(G) = {w ∈ T*|S ⟹+ w}
Note que a definição de regra (→) é diferente da aplicação da regra (⇒), 
isto é, utilizamos → como forma de representar as regras. De outro modo, 
fazemos uso de ⇒ quando estamos derivando, ou seja, verificando se uma 
determinada palavra pertence à linguagem.
Vejamos um exemplo.
Exemplo 1
Considere a gramática sobre o alfabeto {a, b}:
S → bS|aA|ε
A → bA|aS
Como forma de exemplificar a derivação nos basearemos no Quadro 1, 
que representa uma tabela de derivação na qual temos como primeira linha 
os símbolos terminais e como primeira coluna as variáveis. 
Gramáticas regulares 7
Quadro 1. Tabela de derivação
a b ε
S aA bS ε
A aS bA
Utilizaremos as regras de derivação para verificar se a palavra baab per-
tence à linguagem. Vejamos:
1. Iniciamos o processo de derivação a partir de S. Como a palavra pro-
curada consiste em baab, iniciaremos pelo símbolo b. Deste modo, ao 
localizar a linha S e a coluna correspondente ao símbolo b, temos que:
S ⇒ bS
2. Partindo para o passo seguinte, temos o símbolo a. Desse modo, como 
o símbolo à direita corresponde a S e na linha que representa S ao ler 
a, temos aA, deste modo produzimos:
⇒ baA
3. Note que na regra apresentada, temos uma variável A à direita e que 
o próximo símbolo lido é a; dito isto, temos:
⇒ baaS
4. No passo seguinte, como temos a leitura de um símbolo b e a produção 
até o momento é encerrada com uma variável S, temos que
⇒ baabS
5. Por fim, perceba que não temos mais terminais a serem lidos, assim, 
podemos localizar na linha S o símbolo ε e concluir a leitura em:
⇒ baab
Deste modo, como a palavra baab pode ser gerada pela gramática, podemos 
afirmar que baab ∈ L(G).
Gramáticas regulares8
A seguir é apresentado o processo de derivação completo para a geração 
da palavra baab.
S ⇒ bS
⇒ baA
⇒ baaS
⇒ baabS
⇒ baab
Como visto, é possível, com alguns números de derivações, produzir uma 
determinada cadeia, ou seja:
 � V ⇒* w, isto é, fecho transitivo e reflexo, w é derivável a partir de V 
aplicando 0 ou mais regras sucessivas.
 � V ⇒+ w, isto é, fecho transitivo, w é derivável a partir de V aplicando 1 
ou mais regras sucessivas.
 � V ⇒n w, isto é, w é derivável a partir de V aplicando n ou mais regras 
sucessivas.
Deste modo, uma palavra w ∈ (V ∪ T)* é uma forma sentencial de S ⇒* w 
e uma palavra w ∈ T* é uma sentença se S ⇒* w. 
Vejamos mais um exemplo.
Exemplo 2
Vamos verificar se ababa pertence a L(G), considerando a seguinte gramática:
S → aA
A → aA|bB
B → aB|bB|a
Com o intuito de facilitar o entendimento, faremos uso da tabela de de-
rivação apresentada no Quadro 2.
Gramáticas regulares 9
Quadro 2. Tabela de derivação
a b
S aA
A aA bB
B aB a bB
Ao derivar de modo a obter a palavra ababa, com o intuito de verificar se 
esta pertence a linguagem, temos as seguintes etapas.
1. Iniciamos a leitura a partir do símbolo não terminal inicial S lendo a.
S ⇒ aA
2. Note que a variável consiste em A e o próximo terminal é b. Deste 
modo, temos:
⇒ abB
3. Em B ao ler a, temos ab ou a, mas como a leitura não será encerrada 
inserimos aB, obtendo a produção:
⇒ abaB
4. Em B, ao ler b, temos:
⇒ ababB
5. E novamente em B, lendo a como último símbolo da palavra, temos:
⇒ ababa
Gramáticas regulares10
Perceba que o processo de derivação consiste em:
S ⇒ aA
⇒ abB
⇒ abaB
⇒ ababB
⇒ ababa
Assim, ababa é uma palavra válida, pois ababa ∈ L(G) de modo que S ⇒5 
ababa.
Vejamos agora um exemplo aplicado a uma palavra não pertencente à 
linguagem.
Exemplo 3
Considere a mesma gramática do exemplo anterior. Assim, vamos provar que 
w = abbabb ∉ L(G) Acompanhe:
S ⇒ aA
⇒ abB
⇒ abbB
⇒ abbaB
⇒ abbabB
⇒ abbabbB
Perceba que na última produção dada, a variável B não deriva em ε. Sendo 
assim, S ⇏* abbabb. Logo, abbabb ∉ L(G).
Até aqui você aprendeu a respeito do formalismo de uma gramática regular 
e como ocorre a sua derivação; a seguir, a partir de alguns exemplos, vejamos 
como construir gramáticas regulares.
Construção de gramáticas regulares
Como visto, as gramáticas regulares são uma forma bastante simples de 
denotar as linguagens regulares; elas são divididas em:
Gramáticas regulares 11
 � um conjunto de símbolos variáveis (V), também chamados de variáveis 
não terminais;
 � um conjunto de símbolos terminais que representam os símbolos de 
um alfabeto (T) para a construção de palavras;
 � um conjunto de regras, ou seja, as produções (P);
 � o símbolo não terminal denominado variável inicial ou símbolo inicial (S).
A seguir são apresentados os processos que envolvem a construção das 
gramáticas regulares. Estes serão realizados com o intuito de apresentar 
a equivalência entre eles, a partir da descrição de linguagens regulares, 
de autômatos finitos e, por fim, de gramáticas regulares.
Elaboração de uma gramática regular a partir 
da descrição formal de uma linguagem
Para a nossa primeira gramática construída, escolheremos uma linguagem 
bastante simples. Deste modo, sobre o alfabeto Σ = {0, 1}, considere a linguagem 
L = {w | w termina com um 0}. 
Para a construção da gramática regular que represente esta linguagem, 
devemos inicialmente compreender quais palavras podem ser produzidas a 
partir dela; assim, podemos afirmar que L = {0, 10, 00, 100, ...}. Deste modo, 
conforme apresentado a seguir, esta gramática é facilmente dada por:
S → 0S|1S|0
Note que ao reconhecer o símbolo 1, voltamos à variável S, pois o reco-
nhecimento não pode ser encerrado com este símbolo. De outro modo, ao 
reconhecer 0, há a possibilidade de continuar o reconhecimento em S, reco-
nhecendo 0S, ou simplesmente encerrar o reconhecimento, reconhecendo 
apenas o símbolo 0. 
Vejamos a seguir a derivação da palavra 0010.
S ⇒ 0S
⇒ 00S
⇒ 001S
⇒ 0010
Gramáticas regulares12
Elaboração de uma gramática regular a partir 
de um autômato finito
Como visto, as gramáticas regulares denotam linguagens regulares. No en-
tanto, há outra forma de representar linguagens regulares, dada por meio de 
autômatos finitos, que consiste em um modelo de computação que pode ser 
usado para simular lógica sequencial de alguns programas de computador, 
os quais geram linguagens regulares e podem ser utilizados para modelar 
problemas em diversos campos, como matemática, inteligência artificial, 
jogos, linguística, entre outros.
Isto posto, tendo em vista que tanto autômatos finitos quanto gramáticas 
regulares denotam linguagens regulares, torna-se possível elaborar uma 
gramática regular que represente um autômato finito. Para isso, vejamos o 
autômato finito apresentado na Figura 1.
Figura 1. Autômato finito.
Para obtermos a gramática regular a partir de um autômato finito, deve-
mos, inicialmente,como forma de facilitar o processo, renomear os estados, 
a fim de que possam simbolizar as variáveis de uma gramática regular. Assim, 
teremos como resultado o exposto na Figura 2.
Figura 2. Autômato finito renomeado.
Gramáticas regulares 13
A partir do autômato elaborado, vamos realizar o processo de conversão, 
conforme o algoritmo dado por Anderson (2006). 
Vejamos os passos.
1. Inicialmente, partindo do estado S, temos uma leitura do símbolo b 
chegando ao estado A. Assim, podemos representar o início da nossa 
gramática por:
S → bA
2. Estando no estado A, faremos um processo semelhante ao descrito 
anteriormente. Assim, temos que partindo de A, lemos a e chegamos 
ao estado B, isto é:
A → aB
3. Note que ao chegar no estado B há duas possibilidades de transição, 
isto é, podemos não ler nenhum símbolo terminal e ir para C ou E; 
assim, temos:
B → C|E
4. Iniciando a partir do estado C, temos a leitura do símbolo a e a chegada 
ao estado D:
C → aD
5. A partir do estado D, temos duas possibilidades: voltar para o estado 
C ou partir para o estado E. Desse modo, 
D → C|E
6. Por fim, temos E como o estado de aceitação que pode ser represen-
tado por:
E → ε
Gramáticas regulares14
A partir do exposto, é possível construir a seguinte gramática regular:
S → bA
A → aB
B → C|E
C → aD
D → C|E
E → ε
Note que, conforme Gersting (2014), para qualquer linguagem regular existe 
uma máquina de estado finito que reconhece exatamente essa linguagem. 
Na demonstração dada, as produções da gramática regular correspondem 
às transições de estados da máquina de estado finito.
As gramáticas diferenciam-se dos autômatos finitos pois estas 
tratam-se de formalismos gerativos de linguagens, enquanto os 
autômatos são reconhecedores de linguagens.
Salienta-se que a gramática elaborada é passível de redução em relação 
ao seu número de regras. Cardozo (2016) cita que uma mesma linguagem pode 
ser gerada por mais de uma gramática; quando isso ocorre, dizemos que essas 
gramáticas são equivalentes. Assim, no caso apresentado, torna-se possível 
gerar uma gramática com uma menor quantidade de regras e que consiga 
representar a mesma linguagem descrita pela gramática apresentada.
Elaboração de uma gramática regular a partir 
de uma expressão regular
Para o exemplo com uso de uma expressão regular, vamos nos basear no 
trabalho proposto por Gersting (2014). Deste modo, considere o alfabeto 
Σ = {0, 1} sobre a expressão regular 01(0 + 1)* 1.
Iniciamos inserindo as regras para gerar a leitura dos símbolos 0 e 1, 
respectivamente. Deste modo, podemos produzir:
S → 0A
A → 1B
Gramáticas regulares 15
Neste momento, iniciamos o processo de fecho de Kleene (1951) sobre 
uma operação de união, assim, podemos possuir várias representações de 
0's ou 1's, ou nenhuma. Deste modo, podemos representar esta operação por:
B → 0B|1B|C
Por fim, temos que a palavra deverá ser concluída com o símbolo 1. Deste 
modo, concluímos nossa gramática com:
C → 1
Deste modo, nossa gramática para representar a expressão 01(0 + 1)* 1 
pode ser denotada por:
S → 0A
A → 1B
B → 0B|1B|C
C → 1
Neste capítulo, você aprendeu um pouco sobre as gramáticas regulares, 
o formalismo que as envolve, e verificou que possuem um formato bastante 
simples para denotar as linguagens regulares. Viu, também, que são regulares 
se forem também gramáticas lineares à direita ou à esquerda e que possuem 
equivalência com autômatos finitos e expressões regulares. Por fim, acom-
panhou o processo de construção das gramáticas regulares.
Referências
ANDERSON, J. A. Automata theory with modern applications. New York: Cambridge 
University, 2006.
CARDOZO, E. Linguagens e gramáticas: introdução a software de sistema. Campinas: 
UNICAMP, 2016. Disponível em: https://www.dca.fee.unicamp.br/~eleri/ea876/04/cap4. 
Acesso em: 17 fev. 2021.
CHOMSKY, N. Three models for the description of language. Boston: MIT, 1956. Disponível 
em: https://chomsky.info/wp-content/uploads/195609-.pdf. Acesso em: 17 fev. 2021. 
COUTINHO, S. C.; SCHECHTER, L. M. Autômatos, linguagens formais e computabilidade. 
Rio de Janeiro: UFRJ, 2016.
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação: matemática 
discreta e suas aplicações. 7. ed. Rio de Janeiro: LTC, 2014.
Gramáticas regulares16
KLEENE, S. C. Representation of events in nerve nets and finite automata. Santa Monica: 
Rand, 1951. Disponível em: https://www.rand.org/content/dam/rand/pubs/research_
memoranda/2008/RM704.pdf. Acesso em: 17 fev. 2021. 
MATSUNO, I. P. Um estudo dos processos de inferência de gramáticas regulares e livres 
de contexto baseados em modelos adaptativos. 2006. Dissertação (Mestrado em 
Engenharia Elétrica) — Escola Politécnica, Universidade de São Paulo, São Paulo, 2006.
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. 
(Série Livros Didáticos Informática UFRGS, v. 3). E-book.
RICARTE, I. Introdução à compilação. Rio de Janeiro: Campus, 2008.
TOIDA, M. Regular grammar. Tokyo: University of Tokyo, 2013. Disponível em: https://
www.cs.odu.edu/~toida/nerzic/390teched/regular/grammar/reg-grammar.html. Acesso 
em: 17 fev. 2021.
Leituras recomendadas
COSTA, J. F.; GOUVEIA, P. Gramáticas regulares. In: COSTA, J. F.; GOUVEIA, P. Matemática 
discreta. Lisboa: Universidade de Lisboa, 2016. cap. 11.4, p. 488–496.
MENEZES, P. B. Linguagens regulares: expressões regulares. In: MENEZES, P. B. Linguagens 
formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. cap. 3.7, p. 100–106. (Série 
Livros Didáticos Informática UFRGS, v. 3).
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os edito-
res declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Gramáticas regulares 17