Linguagens Regulares

Prévia do material em texto

Autômatos e Linguagens Formais – Cap 1 Página 1 de 23 
Prof.: Roberto Luis 
 
 CAPÍTULO 2 
 
LINGUAGENS REGULARES 
 
 
INTRODUÇÃO: 
 
Linguagens regulares ou do Tipo 3, que estudaremos neste capítulo, pode ser definida nas 
formas: 
 
 Operacional ou reconhecedor: Autônomo Finito: determinístico, não-determinístico 
ou com movimentos vazios. 
 
 Axiomático ou gerador: Gramática Regular. 
 
 Denotacional: Expressão Regular. (também pode ser considerado como um gerador) 
 
 
Como vemos na Hierarquia de Chomsky, é a classe de linguagens mais simples, permitindo 
desenvolver algoritmos de reconhecimento ou de geração de pouca complexidade, grande 
eficiência e de fácil implementação. 
 
Estudaremos os Autônomo Finito: determinístico, não-determinístico. 
 
 
SISTEMAS DE ESTADO FINITO: 
 
 Um Sistema de Estados Finito é representado por um modelo matemático de sistema com: 
1) Entradas e saídas discretas 
2) Um número finito e pré-definido de estados. 
3) Cada estado possui algumas informações do passado necessárias para determinar as 
ações para a próxima entrada. 
4) O estado corrente, o símbolo lido e o programa determinam o novo estado. 
 
 
Um Sistema de Estados Finito pode representar diversos tipos de sistemas naturais e 
construídos como: 
 
1) Um sistema de simples entendimento é um elevador 
a. É um sistema que não memoriza as requisições anteriores. 
b. Cada “estado” resume as informações: “andar corrente” e “direção do movimento”. 
c. As entradas para o sistema são as requisições pendentes. 
 
2) Analisadores Léxicos (usados nos compiladores) e Processadores de Textos 
a. É um sistema que não memoriza as requisições anteriores. 
b. Cada “estado” memoriza a estrutura do prefixo da palavra em análise. 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 2 de 23 
Prof.: Roberto Luis 
 
Nem todos os Sistema de Estados Finito podem ser estudados por esta abordagem: 
 
1) O célebro humano 
a. Possui 235 células, podendo de representado por um número finito de “estados”. 
b. Devido ao elevado número de combinações de células (“estados”) a abordagem 
não é eficiente. 
 
2) O computador 
a. Processadores e memórias determinam estados que podem ser representados por 
um Sistema de Estados Finito. 
b. Para estudar seu funcionamento adequadamente exige uma memória ilimitada. 
c. A Máquina de Turing é um formalismo de autômato mais adequado ao seu estudo. 
 
 
 
AUTÔMATO FINITO: 
 
Autômato Finito Determinístico (AFD) ou Autômato Finito (AF) é uma máquina composta 
por três partes; 
 
1) Fita: dispositivo de entrada, dividido em células, cada uma armazenando um símbolo 
pertencente a um alfabeto de entrada, o conjunto de todos os símbolos, que ocupa toda a 
fita forma a palavra (informação) a ser processada. 
 
2) Unidade de Controle: possui um número finito e pré-definido de estados e a cada instante 
reflete o estado corrente da máquina. É formada por uma unidade de leitura (cabeça de 
leitura da fita), que lê o conteúdo de uma célula a cada vez, partindo da célula mais a 
esquerda da fita. Após a leitura a cabeça move-se uma célula para a direita. 
 
3) Programa ou Função de Transição: função parcial que comanda a leitura e, dependendo 
do estado corrente e do símbolo lido determina o novo estado do autômato. 
 
Obs: Usamos o conceito de estado para armazenar as informações passadas necessárias para o 
processamento, já que o Autômato Finito não possui memória de trabalho. 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 3 de 23 
Prof.: Roberto Luis 
 
DEFINIÇÃO FORMAL: 
 
Um autômato finito é uma 5-upla A = (, Q, , q0, F) onde: 
 
  Alfabeto de símbolos de entrada 
 Q Conjunto finito não vazio (Estados);   Q =  
 Função programa ou de transição de estados, : Q    Q 
 q0 Estado inicial: q0  Q 
 F Conjunto de estados finais: F  Q 
 
 
Simbolicamente: 
 
 
 
 
 
 
 
 
 
 
 (q, a) = q’  O autômato estando no estado q e lendo o símbolo a na fita de entrada, move 
 a cabeça leitora uma posição para a direita e vai para o estado q’. 
 
 
A função programa pode ser representada como um gráfico, onde p é o estado anterior, a é o smbolo 
lido, q é o novo estado, q0 é o estado inicial e qf o final. 
 
 
 
 
 
Obs: Seja M um Autômato Finito e w uma palavra de entrada. Seu processamento se dá aplicando 
sucessivamente a função programa para cada símbolo de w (da esquerda para direita) até 
ocorrer uma condição de parada. 
 
 
p p 
q0 qf 
a 
 ai Fita de entrada 
Controle 
finito 
Cabeça de 
leitura 
Autômatos e Linguagens Formais – Cap 2 Página 4 de 23 
Prof.: Roberto Luis 
 
EXEMPLO: Autômato Finito 
 
Seja a linguagem: L1 = {w | w possui aa ou bb como subpalavra} 
 
O Autômato Finito: M1 = ({a, b}, {q0, q1, q2, qf}, 1, q0, {qf}} 
 
Onde 1 reconhece L1 e é representada pela tabela abaixo: 
 
 
1 a b 
q0 q1 q2 
q1 qf q2 
q2 q1 qf 
qf qf qf 
 
 
O autômato pode ser representado pelo gráfico abaixo: 
 
 
 
Obs: O algoritmo usa os estados q1 e q2 para “memorizar” o símbolo anterior. Temos que: 
 
1) O estado q1 representa: “o símbolo anterior é a”. 
2) O estado q2 representa: “o símbolo anterior é b”. 
3) O estado qf, (final) é alcançado após ter lido dois a ou dois b consecutivos em seguida 
vare o sufixo da palavra de entrada, sem qualquer controle lógico, só para terminar o 
processamento. 
 
a b 
p p 
q0 
qf 
b 
a 
a, b 
b 
a 
Autômatos e Linguagens Formais – Cap 2 Página 5 de 23 
Prof.: Roberto Luis 
 
EXEMPLO: Autômato Finito 
 
 O processamento do autônomo finito M1 para a entrada (palavra) w= abba, que é aceita. 
 Temos o gráfico: 
 
a b b a 
 
 
 
 
 
 
Obs: O Autônomo Finito sempre para após processar uma palavra (w) de entrada, pois são finitas. 
 As condições de parada são: 
 
1) Após processar o último símbolo da fita o autônomo assume: 
a. um estado final: o autônomo para e a entrada w é aceita; 
b. um estado não-final: o autônomo para e a entrada w não é aceita; 
 
2) A função programa é indefinida para o argumento (estado corrente e símbolo lido): 
a. a máquina para e a palavra de entrada w é rejeitada. 
 
 
a 
b 
p p 
q0 
qf 
b 
a 
Autômatos e Linguagens Formais – Cap 2 Página 6 de 23 
Prof.: Roberto Luis 
 
FUNÇÃO PROGRAMA ESTENDIDA: 
 
Para definir formalmente o comportamento de um Autônomo Finito (dar semântica à 
sintaxe), estendemos a definição da função programa usando como argumento um estado e 
uma palavra. 
 
M = (, Q, , q0, F) um Autômato Finito Determinístico. A Função Programa Estendida ( 
estendida) é denotada por: 
 
  = : Q  *  Q 
 
É a função  : Q    Q estendida para palavras e é definida como: 
 
 (q, ) = q transição que não altera estado 
 
 (q, aw) =  ( (q, a), w); w  * 
 a   
 
(q, x) = q’  O autômato estando no estado q e lendo o símbolo mais à esquerda da cadeia x, 
 vai estar no estado q’ após todos os símbolos de x terem sido lidos. 
 
 
 
EXEMPLO: Função Programa Estendida 
 
Seja o Autônomo Finito M1 = ({a, b}, {q0, q1, q2, qf}, 1, q0, {qf}}, do exemplo anterior. 
 
A Função Programa Estendida aplicada a palavra abaa a partir do estado inicial q0 é: 
 
 
 (q0, abaa) = função estendida sobre abaa 
 ( (q0, a), baa) = processa abaa 
 (q1, baa) = função estendida sobre baa 
 ( (q1, b,), aa) = processa baa 
 (q2, aa) = funçãoestendida sobre aa 
 ( (q2, a), a) = processa aa 
 (q1, a) = função estendida sobre a 
 ( (q1, a), ) = processa abaa 
 (qf, ) = qf função estendida : fim da indução 
 
 a palavra é aceita 
 
Obs: As duas funções:  e  passam a ser denotadas por  para simplificar. 
Autômatos e Linguagens Formais – Cap 2 Página 7 de 23 
Prof.: Roberto Luis 
 
LINGUAGEM ACEITA POR UM AUTÔNOMO FINITO: 
 
Seja M = (, Q, , q0, F) um Autômato Finito Determinístico.A linguagem aceita por M:L 
(M) ou ACEITA(M) é o conjunto de todas as palavras pertencentes a * (w  *) aceitas 
por M: 
ACEITA(M) = {w |  (q0, w)  F} 
 
REJEITA(M) = {todas palavras não aceitas por M} 
 
Temos como verdade: 
 ACEITA(M)  REJEITA(M) =  
 
 ACEITA(M)  REJEITA(M) = * 
 
 o complemento de ACEITA(M) é REJEITA(M) 
 
 o complemento de REJEITA(M) é ACEITA(M) 
 
 
AUTÔNOMOS FINITOS EQUIVALÊNTES : 
 
 M1 e M2 são Autônomos Finitos Equivalentes se so´se: ACEITA(M1) = ACEITA(M2) 
 
LINGUAGEM REGULAR OU TIPO 3: 
 
Uma Linguagem Regular ou Tipo 3 é uma linguagem aceita por um Autônomo Finito 
determinístico.. 
 
 
EXEMPLO: Autômato Finito 
 
 
 
 
 
 
 
( Diagrama de Transição de Estados ) 
 
 
A = ( , Q, , q0, F ); 
 
A = ({0,1}, {q0, q1}, , q0, {q1}) 
 
 
Tabela de Transição de Estados 
 
(q0, 0) = q0 (q1, 0) = q1 
(q0, 1) = q1 (q1, 1) = q0 
 
 
Exemplos de cadeias aceitas por A: 1 , 01 , 01101, ... 
 
Exemplos de cadeias rejeitadas por A: 0 , 101 , 101101, ... 
 
L (A) = { x  * | x tem quantidade ímpar de 1’s } 
0 0 
q1 q0 
1 
1 
Autômatos e Linguagens Formais – Cap 2 Página 8 de 23 
Prof.: Roberto Luis 
 
 
AUTÔMATO FINITO NÃO-DETERMINÍSTICO 
 
INTRODUÇÃO: 
 
 Não-determinismo: 
1) É uma importante generalização dos modelos de máquinas 
2) É importante no estudo da Teoria da Computação e da Teoria das Linguagens 
Formais 
 
Qualquer Autômato Finito Não-Deterministico pode ser simulado por um Autômato Finito 
Determinístico. 
 
O que diferencia um Autômato Finito Não-Deterministico do Autômato Finito 
Determinístico é a atuação da função programa: a função programa, ao processar uma 
entrada composta pelo estado corrente e um símbolo lido, tem como resultado um conjunto 
de novos estados. Cada caminho é independente. O processamento de um caminho não 
influi no estado, posição da cabeça dos demais caminhos. 
 
 
DEFINIÇÃO FORMAL: 
 
Um Autômato Finito Não-Deterministico (AFN) é uma 5-upla A = (, Q, , q0, F) onde: 
 
  Alfabeto de símbolos de entrada 
 Q Conjunto finito não vazio (Estados);   Q =  
 Função programa ou de transição de estados, : Q    2
Q
 
 q0 Estado inicial: q0  Q 
 F Conjunto de estados finais: F  Q 
 
onde 2
Q
 é o conjunto potência de Q. 
 
A função programa: (q, a) = {p1, p2, ..., pn} diferencia um AFD de um AFN e pode ser 
representada pelo grafo abaixo: 
 
 
 
 
p1 pn 
q 
p2 
a 
a Símbolo lido a 
Estado anterior 
Conjunto de 
novos 
estados 
Autômatos e Linguagens Formais – Cap 2 Página 9 de 23 
Prof.: Roberto Luis 
 
(q, a) = {p1, p2, ..., pn}  O autômato estando no estado q e tendo o símbolo a na fita de 
 entrada, move sua cabeça leitora uma posição para a direita, 
 transitando para cada um dos pi estados, i=1, ...., n; conceitualmente, é 
 equivalente a imaginar que o autômato se subdivide em n cópias, cada 
 uma das quais transita para um pi distinto, i=1, ...., n. (como se 
houvesse uma multiplicação da unidade de controle, uma para cada 
alternativa, processando independente sem compartilhar recursos com 
as demais). 
 
Exemplo : 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FUNÇÃO PROGRAMA EXTENDIDA: 
 
Para definir formalmente o comportamento de um Autômato Finito Não-Deterministico 
(dar semântica à sintaxe), estendemos a definição da função programa usando como 
argumento um conjunto finito de estados e uma palavra. 
 
M = (, Q, , q0, F) um Autômato Finito Não-Deterministico. A Função Programa 
Estendida ( estendida) é denotada por: 
 
  = : 2
Q
  *  2
Q
 
 
É a função  : Q    2
Q
 estendida para palavras e é definida como: 
 
 (P, ) = q transição que não altera estado 
 
 (P, aw) =  ( qP  (q, a), w); w  * 
 a   
 
Temos que para um dado conjunto de estados {q1, q2, ..., qn} e para um dado símbolo a: 
 
  ({q1, q2, ..., qn}, a} =  (q1, a)   (q2, a)  ...   (qn, a) 
 
1 
1 1 
1 
1 
0 0 
0 
0 
0 
0 
1 
p2 p4 
q 
p1 p3 
Autômatos e Linguagens Formais – Cap 2 Página 10 de 23 
Prof.: Roberto Luis 
 
 
 
LINGUAGEM ACEITA POR UM AUTÔNOMO FINITO NÃO-DETERMINISTICO: 
 
Seja M = (, Q, , q0, F) um Autômato Finito Não-Determinístico. A linguagem aceita por 
M: L (M) ou ACEITA(M) é o conjunto de todas as palavras pertencentes a * (w  *) tais 
que existe pelo menos um caminho alternativo que aceita a palavra, ou sejas: 
 
ACEITA(M) = {w | existe q   (q0, w) tal que q  F} 
 
REJEITA(M) = {todas palavras  * rejeitadas por todos os caminhos 
alternativos de M ( a partir de q0)} 
 
 
 
 
 
EXEMPLO: Autômato Finito Não-Determinístico 
 
Seja a linguagem L5 = {w | w possui aa ou bb como sub palavra}. 
 
Seja o Autônomo Finito Não-Determinístico M5 = ({a, b}, {q0, q1, q2, qf}, 5, q0, {qf}). 
 
Onde 5 é tal que ACEITA(M5) = M1 é representada pela tabela abaixo: 
 
 
5 a b 
q0 {q0,q1} {q0,q2} 
q1 qf - 
q2 - {qf} 
qf {qf} {qf} 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 11 de 23 
Prof.: Roberto Luis 
 
O autômato pode ser representado pelo gráfico abaixo: 
 
 
 
Existem três caminhos alternativos de processamento: 
 
 o ciclo em q0 realiza uma varredura em toda a entrada. 
 o caminho q0 / q1 / qf qarante a ocorrência de aa 
 o caminho q0 / q2 / qf qarante a ocorrência de bb 
 
 
 
EXEMPLO: Autômato Finito Não-Determinístico 
 
Seja a linguagem L6 = {w | w possui aaa como sufixo}. 
 
Seja o Autônomo Finito Não-Determinístico M6 = ({a, b}, {q0, q1, q2, qf}, 6, q0, {qf}). 
 
Onde 6 é tal que ACEITA(M6) = L6 : 
 
O autômato pode ser representado pelo gráfico abaixo: 
 
 
 
 
 
q1 qn q0 q2 a a 
a 
 
a, b 
 
 
q1 
 
q2 
 
q0 
qf 
b 
a, b 
a 
a,b 
b 
a 
Autômatos e Linguagens Formais – Cap 2 Página 12 de 23 
Prof.: Roberto Luis 
 
EQUIVALÊNCIA ENTRE AFD E AFN: 
 
A classe de AFD é equivalente à classe dos AFN. 
 
Toda linguagem reconhecida por um AFD é reconhecida por um AFN e vice-versa. 
 
A classe de linguagens reconhecidas por AFD’s e AFN’s é a das Linguagens Regulares. 
 
Seja M = (, Q, , q0, F) um AFN qualquer. 
 
Seja M’ = (, Q’, ’ , ‹q0›, F’) um AFD construído a partir de M como segue: 
 
 Alfabeto de símbolos de entrada 
Q’ Conjunto de todas as combinações, sem repetições, de estados de Q, 
denotadas por ‹q1q2...qn›, onde qi  Q, para i em {1, 2, ..., n}. A ordem dos 
elementos não distingue combinações: ‹quqv› = ‹qvqu› 
’ tal que ’ = (‹q1...qn›,a) = ‹p1...pn› soesose  = ({q1,...,qn},a) = {p1,...,pn} 
‹q0› Estado inicial 
F’ Conjunto de todos os estados ‹q1q2...qn›  Q’ tal que alguma componente 
qi  F, para i em {1, 2, ..., n} 
 
EXEMPLO: Construção de um AFD a partir de um AFN 
 
Seja o Autônomo Finito Não-Determinístico M6 = ({a, b}, {q0, q1, q2, qf}, 6, q0, {qf}). 
 
O autômato pode ser representado pelo gráficoabaixo (Exemplo anterior): 
 
 
 
O correspondente AFD M6’ = ({a, b}, Q’, 6’ , ‹q0›, F’) é: 
 
Q’ = {‹q0›, ‹q1›, ‹q2›, ‹qf›, ‹q0q1›, ‹q0q2›, ‹q0q1q2...qf›} 
 
6’ é descrita na tabela abaixo que só contém os estados onde a função programa é definida 
 
6 a b 
‹q0› ‹q0q1› ‹q0› 
‹q0q1› ‹q0q1q2› ‹q0› 
‹q0q1q2› ‹q0q1q2qf› ‹q0› 
‹q0q1q2qf› ‹q0q1q2qf› ‹q0› 
 
 
p1 pn q0 p2 a a 
a 
 
a, b 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 13 de 23 
Prof.: Roberto Luis 
 
O correspondente AFD M6’ pode ser representado pelo gráfico abaixo onde os estados p0, 
p1, p2, p f denotam ‹q0›, ‹q0q1›, ‹q0q1q2›, ‹q0q1q2qf› 
 
 
 
 
 
 
EXPRESSÕES REGULARES 
 
INTRODUÇÃO: 
 
 Expressões Regulares: 
 
1) Descrevem as Linguagens regulares 
 
2) É um formalismo gerador, pois pode-se inferir como construir (“gerar”) as palavras de 
uma linguagem 
 
3) É definida a partir de conjuntos (linguagens) básicos e operações de concatenação e união. 
 
4) São adequadas para a comunicação homem x homem e homem x máquina. 
 
 
b 
a 
b b 
p1 pf q0 p2 
a a 
 
b 
 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 14 de 23 
Prof.: Roberto Luis 
 
DEFINIÇÃO: 
 
Seja  um alfabeto. Uma expressão regular (ER) sobre , e os conjuntos que ela representa, 
é definida como: 
 
a)  é uma ER, representa o conjunto  , e denota a linguagem vazia. 
 
b)  é uma ER, representa o conjunto {}, e denota a linguagem que só possui a palavra 
vazia, {} 
 
c) Se x  , então x é uma ER, representa o conjunto {x}, e denota a linguagem contendo a 
palavra unitária, {x}. 
 
d) Se r e s são ER representando, respectivamente, os conjuntos R e S (denotam as 
linguagens R e S), então: 
 (r+s), é ER e denota a linguagem R  S. 
 (rs), é ER e denota a linguagem RS = {uv |u  R e v  S} (concatenação) 
 (r*) é ER e denota a linguagem R*. 
 
OBS: Para se poder eliminar alguns parênteses, assume-se que a prioridade das operações é: 
 
1) Concatenação sucessiva 
2) Concatenação 
3) Soma ou união 
 
OBS: Uma linguagem gerada por uma ER r é representada por L(r) ou GERA(r) e é 
denominada de Linguagem Regular. 
 
EXPRESSÃO 
REGULAR 
LINGUAGEM REPRESENTADA 
aa Somente a palavra aa 
ba* Todas as palavras que iniciam por b, seguido por zero ou mais a’s 
(a+b)
+
 Todas as palavras sobre {a, b} 
(a+b)* Todas as palavras sobre {a, b}, e também a cadeia vazia 
(a+b)*aa(a+b)* Todas as palavras contendo aa como subpalavra 
a*ba*ba* Todas as palavras contendo exatamente dois b’s 
(a+b)*(aa+bb) Todas as palavras que terminam com aa ou bb 
(a+)(b+ba)* Todas as palavras que não possuem dois a’s consecutivos 
 
Autômatos e Linguagens Formais – Cap 2 Página 15 de 23 
Prof.: Roberto Luis 
 
GRAMÁTICA REGULAR 
 
INTRODUÇÃO: 
 
Usando o conceito geral de gramática, já visto, podemos definir Linguagens Regulares e 
Não-Regulares. A classe de Linguagens regulares fica definida através do estabelecimento 
de restrições nas regras de produção. 
 
 
GRAMÁTICAS LINEARES (GL): 
 
 Seja G = (V, T, P, S) uma gramática 
 
 Sejam A e B elementos de V e w palavra de T* . Então G é uma: 
 
 1) Gramática Linear à Direita (GLD). Se as regras de produção são da forma: 
 
 A wB ou A  w 
 
 2) Gramática Linear à Esquerda (GLE). Se as regras de produção são da forma: 
 
 A Bw ou A  w 
 
 
3) Gramática Linear Unitária à Direita (GLUD). Se as regras de produção são como na GLD 
acrescida de: 
 
 |w|  1 
 
OBS: Nas GL o lado direito de uma produção é formado por no máximo uma variável. esta 
variável, se existir sempre antecede (linear à esquerda) ou sucede (linear à direita) 
qualquer subpalavra de terminais. 
 
 
EQUIVALÊNCIA DAS GRAMÁTICAS LINEARES: 
 
 Seja L uma linguagem. Então: 
 
 L é gerada por uma GLD se e só se, 
 
 L é gerada por uma GLE se e só se, 
 
 L é gerada por uma GLUD se e só se, 
 
 L é gerada por uma GLUE se e só se, 
 
 Vemos que as diversas formas de GL são formalismos equivalentes. 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 16 de 23 
Prof.: Roberto Luis 
 
GRAMÁTICA REGULAR (GR): 
 
 Uma Gramática Regular é qualquer Gramática Linear. 
 
 Seja G uma Gramática Regular, então L(G) ou GERA(G) é uma linguagem gerada por G. 
 
 
EXEMPLO: Gramática Regular. 
 
 A linguagem a(ba)* é gerada pela seguintes Gramáticas Regulares: 
 
1) Linear à Direita. G = ({S, A}, {a, b}, P, S} onde P possui as regras de produção: 
 
S  aA 
A  baA |  
 
 2) Linear à Esquerda. G = ({S}, {a, b}, P, S} onde P possui as regras de produção: 
 
S  Sba | a 
 
 3) Linear Unitária à Direita. G = ({S, A, B}, {a, b}, P, S) onde P possui as regras de produção: 
 
S  aA 
A  bB |  
 
B  aA 
 
 4) Linear Unitária à Esquerda. G = ({S, A}, {a, b}, P, S) onde P possui as regras de produção: 
 
S  Aa | a 
 
A  Sb 
 
EXEMPLO: Gramática Regular. 
 
 A linguagem (a + b)*(aa + bb) é gerada palas seguintes Gramática Regulares: 
 
1) Linear à Direita. G = ({S, A}, {a, b}, P, S} onde P possui as regras de produção: 
 
S  aS | bS | A 
 
A  aa | bb 
 
 2) Linear à Esquerda. G = ({S, A}, {a, b}, P, S} onde P possui as regras de produção: 
 
S  Aaa | Abb 
 
A  Aa | Ab |  
Autômatos e Linguagens Formais – Cap 2 Página 17 de 23 
Prof.: Roberto Luis 
 
GRAMÁTICA REGULAR  LINGUAGEM REGULAR: 
 
 Se L é uma linguagem gerada por uma Gramática Regular, então L é uma Linguagem Regular. 
 
 
LINGUAGEM REGULAR  GRAMÁTICA REGULAR: 
 
 Se L é uma Linguagem Regular, então existe G, Gramática Regular, que gera L. 
 
EXEMPLO: Construção de uma Gramática Regular a partir de um AFD 
 
Considere o AFD: 
 
M = ({a, b, c}, {q0, q1, q2}, , q0, {q0, q1, q2}). 
 
 Ilustrado como abaixo: 
 
 
 
 A Gramática Regular correspondente é: 
 
 G = ({q0, q1, q2, S}, {a, b, c}, S, P) onde P é como segue: 
 
 
Transição Produção 
- S q0 
- q0  
- q1  
- q2  
(q0, a) = q0 q0 aq0 
(q0, b) = q1 q0 bq1 
(q1, b) = q1 q1 bq1 
(q1, c) = q2 q1 cq2 
(q2, c) = q2 q2 cq2 
 
 
 c a b 
 
 
q1
 
 
 
q0 q2 
c b 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 18 de 23 
Prof.: Roberto Luis 
 
PROPRIEDADES DAS LINGUAGENS REGULARES (LR) 
 
INTRODUÇÃO: 
 
 Características das LR: 
 
1) São representadas por formalismo: 
a. De pouca complexidade 
b. Grande eficiência 
c. Fácil implementação. 
 
2) É uma classe relativamente simples, portanto: 
a. É restrita e limitada 
b. É fácil definir Linguagens Não-regulares 
 
Passaremos a analisar as seguintes questões sobre as LR: 
 
1) Como determinar se uma Linguagem é uma LR? 
2) Como verificar se uma LR é finita, infinita ou vazia? 
3) É possível analisar duas LR e concluir se são iguais ou diferentes? 
4) A Classe das LR é fechada para as operações de união, concatenação e intersecção? 
 
LINGUAGENS REULARES E NÃO-REGULARES: 
 1) Mostrar que uma linguagem é regular: 
 É só representá-la usando um dos formalismos apresentados: 
o Autômato Finito 
o Expressão Regular 
o Gramática Regular 
 
 2) Mostrar que uma linguagem é não-regular: 
 Deve ser analisado caso a caso: 
o Podemos usar o Lema do Bombeamento 
 
EXEMPLO: Linguagem Não-Regular 
 
 Seja L = {w | w possui o mesmo número de símbolos a e b} 
 
 Demonstramos que a Linguagem L não é regular usam o Lema do Bombeamento quando 
chegamos a um resultado absurdo: 
 
 Suponha que L é Regular. Então: 
 
 Existe um AFD M com n estados que aceita L 
 
 Seja w = a
n
b
n
 
 
 Pelo Lema do Bombeamento: 
 w podeser definida como: w = uvz onde: 
 |uv|  n, |v|  1 e, para todo i  0 uviz é palavra de L 
 
Temos uma situação absurda, pois como |uv| n, uv é composta só por símbolos a. 
 
Como exemplo w = uv
2
z não pertence a L, pois não possui o mesmo número de 
símbolos a e b. 
Autômatos e Linguagens Formais – Cap 2 Página 19 de 23 
Prof.: Roberto Luis 
 
OPRAÇÕES FECHADAS SOBRE LINGUAGENS REULARES: 
 
 A Classe das LR é fechada (continua sendo uma LR) para as operações: 
 
 União 
 Concatenação 
 Complemento 
 Intersecção 
 
INVESTIGAÇÃO SE UMA LINGUAGEM REGULAR É 
FECHADA, VAZIA OU INFINITA. 
 
TEOREMA: Linguagem Regular Vazia, Finita ou Infinita 
 
Se L uma LR aceita por um Autômato Finito M = (, Q, , q0, F) com n estados ( o 
cardinal de Q é n), Então L é: 
 
1) Vazia se e só se, M não aceita qualquer palavra w tal que |w| < n 
 
2) Finita se e só se, M não aceita uma palavra w tal que n  |w| < 2n 
 
3) Infinita se e só se, M aceita qualquer palavra w tal que n  |w| < 2n 
 
EXEMPLO: Linguagem Não-Regular 
 
 Qual a linguagem é aceita pelo autômato (AFD) abaixo? 
 
 
 
 
 Pelo Teorema anterior Temos: 
 
Infinita se e só se, M aceita qualquer palavra w tal que n  |w| < 2n, 
 
A menor palavra aceita cujo comprimento maior ou igual a 3 é aabaa a qual possui 
comprimento 5. 
 
Ou seja: 3  | aabaa | < 6 
 
a q1 q0 pf 
a 
 
b 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 20 de 23 
Prof.: Roberto Luis 
 
IGUALDADE DE LINGUAGENS REGULARES: 
 
TEOREMA: Igualdade de Linguagens Regulares 
 
Se M1 e M2 são Autômatos Finitos, então existe um algoritmo para determinar se 
ACEITA(M1) = ACEITA(M2). 
 
 
EFICIÊNCIA DE UM AUTÔMATO FINITO COMO ALGORITMO 
DE RECONHEIMENTO. 
 
A implementação de um simulador de AFD consiste basicamente em um algoritmo que 
controla a mudança de estado do autômato a cada símbolo lido da entrada. O tempo de 
processamento necessário para rejeitar ou aceitar é diretamente proporcional ao tamanho da 
entrada, não depende do autômato de reconhecimento. Entretanto podemos reduzir o número 
de estados através de um algoritmo para construir o AFD mínimo (com o menor número de 
estados) para qualquer Linguagem Regular. 
 
 
 
AUTÔMATOS FINITOS COM SAÍDA 
 
INTRODUÇÃO: 
 
 
Sem alterar a classe de linguagens reconhecidas, é possível estender a definição de autômato 
finito incluindo a geração de uma palavra de saída. A saída não pode ser lida , ou seja, não 
pode ser usada como memória auxiliar., e é como segue: 
 
 É definido sobre um alfabeto especial (alfabeto de saída), que pode ser igual ao de 
entrada. 
 a saída é armazenada em uma fita independente da fita de entrada. 
 a cabeça da fita de saída move uma célula para direita a cada símbolo gravado 
 o resultado do processamento é o seu estado fina (aceita / rejeita) e a fita de saída. 
 
 Temos como exemplos as máquinas de Mealy e de Moore, que são modificações sobre o AFD 
 
 
Autômatos e Linguagens Formais – Cap 2 Página 21 de 23 
Prof.: Roberto Luis 
 
MÁQUINA DE MOORE: 
 
 
 Constitui-se de uma 6-upla (Q, , , , q0), onde: 
 
  lfabeto de saída # 
 Q  Função de saída: a saída se define exclusivamente 
a partir do estado da máquina. 
 
Exemplo: 
 
 
 
 
 
 
 
O que faz esta máquina? 
Dado um número natural que lhe é fornecido, em representação binária, ela calcula o resto da 
divisão inteira desse número por 3 (i.e., ela implementa a operação MOD3 sobre o número). 
 
 
MÁQUINA DE MEALLY: 
 
Também constitui-se de uma 6-upla (Q, , ,, q0), mas a função tem agora uma 
caracterização mais refinada: 
 
Q     Função de saída: a saída se define não só a partir do estado da 
 máquina, mas também em função do símbolo lido na fita. 
 
Exemplo: 
 
 
 
 
 
 
 
 
 
 
 
 
O que faz esta máquina? Ela reconhece a linguagem representada por (0+1)*(00+11). 
OBS: O AFDmín requer 5 estados! 
 
 
 
 
 
 
0 
0 
0 
1 
1 
1 
1 0 
2 
q0 q2 q1 = { 0, 1, 2 } 
q1 
0/n 
1/n 
1/n 
0/n 
1/y 
0/y q0 
q2 
 = { n, y } 
Autômatos e Linguagens Formais – Cap 2 Página 22 de 23 
Prof.: Roberto Luis 
 
Autômatos Finitos (ou suas variações) como Formalismos de Modelagem de Sistemas: 
 
 
Exemplo 1 (P.B.Menezes): 
Neste exemplo, uma Máquina de Mealy trata algumas situações típicas de um diálogo que cria e 
atualiza arquivos. A seguinte simbologia é adotada no grafo da função de transição: 
 
  : Entrada fornecida pelo usuário (em um teclado, por exemplo). 
 “...” : Saída gerada pelo programa (em um vídeo, por exemplo). 
 [...] : Ação interna ao programa, sem comunicação com o usuário. 
 (...) : Resultado de uma ação interna ao programa; é usado como entrada no grafo. 
 
Autômatos e Linguagens Formais – Cap 2 Página 23 de 23 
Prof.: Roberto Luis 
 
 
AUTÔMATO FINITO E VARIAÇÕES 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
AFD 
AFB 
(bidirecional) 
1-pebble AFB AFBND 
AFBND com 
endmarkers 
[ AFD com 
saída explícita ] 
(Q, ,  , , , q0) 
: alfabeto de saída 
Máquina de 
Mealy 
( : Q ) 
 
Máquina de 
Moore 
( : Q ) 
Máquina de 
Turing 
unidirecional 
AFND 
(não-determinístico) 
AFND- 
(com -movimento) 
...
.. 
 x1 x2 ...
.. 
xn $ ...
.. 
 
t0 tf