Prévia do material em texto

Linguagens regulares
Conceitos elementares de linguagens formais e autômatos, conjuntos, expressões e linguagens regulares,
autômatos finitos determinísticos e não determinísticos.
Prof.º Tomás de Aquino Tinoco Botelho
1. Itens iniciais
Propósito
Apresentar os conceitos fundamentais das linguagens regulares, os autômatos finitos, e sua importância na
construção de compiladores e interpretadores de linguagens como C++ e Java, pois a linguagem regular é
base para a definição dessas linguagens de programação.
Objetivos
Reconhecer os conceitos básicos sobre gramáticas regulares.
Analisar o funcionamento de um autômato finito.
Aplicar a conversão de autômatos finitos não determinísticos em determinísticos.
Aplicar expressões regulares em um programa de computador.
Introdução
Neste conteúdo, aprenderemos os conceitos e a prática sobre os conjuntos, as expressões e as linguagens
regulares, bem como os autômatos finitos, que são máquinas de estado finito reconhecedoras das expressões
regulares (ER).
Conforme Linz (2016), para nos comunicarmos com alguém, precisamos de uma linguagem, tal como o
português e o inglês, que são chamados de idiomas. Para construir uma linguagem, existem algumas regras
que compõem aquilo que denominamos gramática.
Na ciência da computação, para se comunicar com o hardware do computador, o usuário precisa de algumas
linguagens de programação, como C, C# e Java. A linguagem formal é uma abstração das características
gerais de uma linguagem de programação.
• 
• 
• 
• 
1. Gramáticas regulares
Conjuntos
Definição
Um conjunto é uma coleção bem definida de objetos, chamados de elementos ou membros do conjunto.
Para indicar que é um elemento do conjunto , escrevemos (diz-se: pertence a ). Caso 
não esteja em , escrevemos: (diz-se: não pertence a ).
Um conjunto é uma entidade única e é caracterizado por sua propriedade. Em geral, se é a propriedade
definida para os elementos de , então é denotado como tem a propriedade . É assim em 
 é natural .
Um conjunto pode ser especificado incluindo algumas descrições de seus elementos entre chaves.
Exemplo
O conjunto de inteiros 0, 1, 2 é mostrado como S = {0, 1, 2}. 
As reticências são usadas para indicar uma continuidade. Sendo assim, vejamos esses dois casos a seguir:
{a, b, ..., z}
Representa o conjunto de todas as letras
minúsculas do alfabeto.
{1, 3, 5, ...}
Representa o conjunto de todos os inteiros
ímpares positivos.
Quando surge uma necessidade, usamos uma notação mais explícita, como veremos a seguir:
Lê-se: “S é o conjunto de todo i, tal que i é maior que zero e i é ímpar”, o que implica, é claro, que i é um
inteiro.
Um conjunto pode ser considerado de dois tipos:
Finito
Se contiver um número finito de elementos, como no seguinte exemplo:
S = {0, 1, 2, 3, 4, 5, 6, 7}
O tamanho de um conjunto finito é o número de elementos nele contido, denotado por |S|. No
exemplo anterior: |S| = 8.
Infinito
Se contiver um número infinito de elementos, como no seguinte exemplo:
S = {..., -3, -2, -1, 0, 1, 2, 3, ....}
Todo conjunto infinito é ilimitado. No exemplo, abrange tanto os números inteiros negativos quanto os
números inteiros positivos.
Um conjunto que contém apenas um elemento é chamado de unitário. Portanto, os conjuntos e 
 são unitários escritos na forma de lista. Além disso, e 
Dois conjuntos A e B serão iguais se contiverem exatamente os mesmos elementos. Isso significa que, se
algum elemento está em A, esse elemento também está em B.
Operações sobre conjuntos
As operações algébricas sobre conjuntos usuais são:
União (U)
 ou 
Interseção 
 e 
Diferença (-)
 e 
Os conjuntos e são disjuntos ou mutuamente exclusivos quando .
Existe ainda a complementação ou complemento. Dado um conjunto universal U, o complemento de um
conjunto Y é:
Produto cartesiano e concatenação
O produto cartesiano e a concatenação para dois conjuntos A e B e o conjunto sem elementos (denominado 
conjunto vazio ou conjunto nulo) são denotados, respectivamente, por:
A x B
Seja A = {2, 3, 4, 5} e B = {3, 4}. Então, A × B = {(2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4), (5, 3), (5, 4)}. Em geral,
A × B = {(a, b) | a ∈ A e b ∈ B}.
AB
Seja A={a,b} e B={c,d}. Então, AB={ac,ad,bc,bd}. Em geral, AB={ab∣ a está em A e b está em B}.
Um conjunto S1 é considerado um subconjunto de S se cada elemento de S1 for também um elemento de S.
Dizemos que S1 está contido em S e escrevemos isso como:
O conjunto de todos os subconjuntos de um conjunto S é chamado conjunto potência (powerset) ou conjunto
das partes de S e é designado por 2s, em que s é o número de elementos do conjunto S.
Relações e funções
Conceito de relações
O produto cartesiano de dois conjuntos é o conjunto formado por todos os pares ordenados (a, b), em que a é
um elemento de A, e b é elemento de B, como é mostrado a seguir:
Um par ordenado tem a seguinte representação: (a, b). Tal representação implica uma relação de ordem, em
que o elemento a é anterior ao elemento b. Consequentemente, se a ≠ b, então, (a, b) ≠ (b, a).
Exemplo
Sejam A = {a, b, c} e B = {0, 1}. Então, A × B = {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}. 
Uma relação R sobre dois conjuntos A e B, não vazios, é definida como um subconjunto de A × B. Os
conjuntos A e B recebem, respectivamente, os nomes domínio e contradomínio da relação R. Por envolver dois
conjuntos, essa relação é chamada de binária, e seus elementos recebem a designação de pares ordenados.
A relação de equivalência é uma generalização do conceito de igualdade (identidade). Para indicar que um par
 está em uma relação de equivalência, escrevemos: .
Uma relação denotada por é considerada uma equivalência se satisfizer três regras:
Reflexidade
 a para todo a.
Simetria
Se , então .
Transitividade
Se e , então .
Para entender melhor, considere o seguinte caso:
Exemplo
No conjunto de inteiros não negativos, podemos definir uma relação se, e apenas se, , em que mod é o
resto da divisão inteira de por y. Então, e 12 . Claramente, essa é uma relação de equivalência, pois
satisfaz a reflexividade, a simetria e a transitividade. 
O que é uma função?
Uma função é a regra que atribui aos elementos de um conjunto um elemento único de outro conjunto. Se f
denota uma função, então os dois conjuntos S1 e S2 ficarão da seguinte forma:
Primeiro conjunto S1
É chamado de domínio de f.
Segundo conjunto S2
É chamado de contradomínio de f.
Para cada elemento do domínio, existirá um único correspondente no contradomínio. Esse correspondente é
conhecido como imagem. Nós escrevemos assim:
Usualmente, denotamos uma função por:
Sendo que os elementos são descritos como:
F = nome da função;
A = domínio;
B = imagem;
Y = f(x) = expressão da lei de correspondência (relação) dos elementos x em A com os elementos y em
B.
Dados os conjuntos e , uma relação é o conjunto dos pares ordenados 
 a se relaciona com b por meio da regra f. Dizemos que é uma função se, e somente
se, para todos os , temos 
Em outras palavras, para todo elemento a , existe, no máximo, um elemento , tal que a se relaciona
com b. E escrevemos , quando a se relaciona com b por meio da regra f.
Diagramas de Venn
Estes são os diagramas utilizados em matemática para simbolizar graficamente propriedades, axiomas e
problemas relativos aos conjuntos e sua teoria.
Se uma função leva elementos do domínio e os relaciona com seu dobro no contradomínio, 2 estará
relacionado com 4. Logo, a imagem da função para 2 é igual a 4. Ao juntarmos todas as imagens, formamos o
conjunto das imagens, que são todos os elementos do contradomínio correspondentes a algum elemento do
domínio.
Pode ser representado pelo diagrama de Venn a seguir:
• 
• 
• 
• 
Diagrama de Venn da função \(f: A \rightarrow B\).
Gráfico de uma função
O gráfico de uma função é o conjunto dos pares ordenados no produto cartesiano da
forma , ou seja , ou ainda e . Veja:
Gráfico de uma função
O gráfico da função pode ser visto a seguir:
Gráfico dafunção y = 2x + 1
Noções básicas sobre linguagens
Principais conceitos
Vejamos a seguir as definições relativas a cada um desses principais conceitos:
Símbolo
É uma entidade definida como um ponto em geometria e é uma abstração.
Alfabeto
É um conjunto finito de símbolos denotados por Σ em autômatos. Um alfabeto é usado para construir
uma linguagem. Por exemplo, {0, 1} é um alfabeto binário e {A ..., Z, a ..., z} é um alfabeto definido para
o idioma português.
Cadeia
É definida como uma sequência de símbolos de comprimento finito. Uma cadeia é denotada por w.
Por exemplo, 000111 é uma cadeia binária. O comprimento de uma cadeia w é denotado por |w|. Para
o caso anterior: |w|=|000111| = 6.
Prefixo de uma cadeia
É a cadeia formada por qualquer número de símbolos iniciais dessa cadeia. Por exemplo, vamos pegar
uma cadeia w = 0111. Para a cadeia específica, λ, 0, 01, 011 e 0111 são prefixos da cadeia 0111. Para
uma cadeia de comprimento n, há n + 1 prefixos. A cadeia vazia, que não contém símbolos, é
denotada por λ.
Prefixo próprio para uma cadeia
É qualquer prefixo da cadeia diferente da própria cadeia.
Por exemplo, para a cadeia w = 0111, os prefixos próprios são λ, 0, 01 e 011.
Sufixo de uma cadeia
É formado a partir de qualquer número de símbolos do final da cadeia. Por exemplo, vamos pegar uma
cadeia w = 0110. Para a cadeia específica, λ, 0, 10, 110 e 0110 são sufixos da cadeia 0110. Para uma
cadeia de comprimento n, há n + 1 sufixos.
Sufixo próprio para uma cadeia
É qualquer sufixo da cadeia diferente da própria cadeia. Por exemplo, para a cadeia w = 0110, os
sufixos próprios são λ, 0, 10 e 110.
Subcadeia de uma cadeia
É definida como uma cadeia formada por qualquer número de símbolos da cadeia. Por exemplo, para
a cadeia w = 012, as subcadeias são λ, 0, 1, 2, 01, 02, 12 e 012.
O número de subcadeias de uma cadeia é igual a 2n, em que n é o número de símbolos que compõem
essa cadeia. No exemplo anterior, a cadeia w = 012 tem três símbolos. Logo, deverá ter 23 = 8
subcadeias.
Duas cadeias, sejam elas elementares ou não, podem ser anexadas, formando uma só cadeia por
meio da operação de concatenação, gerando uma nova cadeia.
Linguagem formal e gramática
A linguagem formal é uma abstração das características gerais de uma linguagem de programação. Para a
construção das linguagens, existem algumas regras a serem seguidas, as quais chamamos de gramática.
A gramática é um conjunto de regras para definir se uma frase é válida em qualquer idioma.
Gramáticas definem linguagens e são especificações finitas de regras de geração de cadeias.
Uma gramática deve ser capaz de gerar toda e qualquer cadeia pertencente à linguagem que ela define. Uma
gramática G é definida como a quádrupla, como é mostrado a seguir:
Em que cada elemento corresponde às seguintes definições:
V é o vocabulário da gramática que inclui um conjunto finito e não vazio de símbolos não terminais,
chamados de variáveis, porque podem ser substituídos;
T é um conjunto finito de objetos chamados de símbolos terminais. Assim, T é um conjunto disjunto de 
, ou seja, .
P é um conjunto finito de produções ou regras de substituição da gramática no formato , em
que "a" é uma palavra sobre contendo, pelo menos, um símbolo não terminal, e "b" é uma palavra
sobre (V U T).
S é o símbolo inicial, ou Start Symbol.
As regras de produção de uma gramática consistem nas duas seguintes partes:
1
Lado Esquerdo (LE)
Contém principalmente os símbolos não terminais a serem substituídos. Pode conter terminal e não
terminal em alguns casos, mas pelo menos um não terminal.
Os símbolos não terminais são aqueles símbolos que podem ser substituídos várias vezes. Os
símbolos terminais são aqueles que, uma vez inseridos na cadeia, não podem ser substituídos
posteriormente.
2
Lado Direito (LD)
Pode conter terminal, não terminal ou qualquer combinação de terminal e não terminal, mesmo o
nulo. Para ser uma gramática válida, uma produção deve conter o símbolo inicial S em seu LE.
• 
• 
• 
• 
Gramáticas lineares e classes de linguagens
Hierarquia de Chomsky
Conjuntos e expressões regulares (ER) são notações alternativas utilizadas para representar a classe de
linguagens mais simples que se conhece: a classe das linguagens regulares – a mais restrita dentro da
hierarquia de Chomsky. Vamos conhecer essa hierarquia a seguir:
Hierarquia de Chomsky.
Tipo 0 é uma gramática com estrutura de frase, sem qualquer restrição.
Tipo 1 é a chamada gramática sensível ao contexto.
Tipo 2 é a gramática livre de contexto.
Tipo 3 é a chamada gramática regular.
ER é a parte da linguagem da gramática do tipo 3, que é chamada de gramática regular. Uma ER é aceita pela
máquina chamada autômato finito (AF).
As gramáticas da hierarquia de Chomsky são diferenciadas a partir de restrições aplicadas às produções da
forma 
Veja as implicações de cada lado da gramática a seguir:
1
Gramática linear à direita
É aquela cujas produções obedeçam a todas as seguintes condições:
 
 
 
Como por exemplo: a gramática 
 é linear à direita.
• 
• 
• 
• 
2 Gramática linear à esquerda
É aquela em que todas as produções exibem as seguintes características:
 
 
 
Como: a gramática , S) é linear
à esquerda.
Gramáticas lineares, à esquerda ou à direita, geram linguagens denominadas regulares ou simplesmente do
tipo 3.
Demonstra-se que as gramáticas lineares à esquerda ou à direita geram exatamente a mesma classe de
linguagens. Portanto, é indiferente o emprego de uma ou outra dessas duas variantes de gramática, já que
ambas possuem a mesma capacidade de representação de linguagens.
Na gramática do tipo 3 (gramática regular), todas as produções serão nas seguintes formas:
O lado esquerdo das regras de produção só contém símbolos não terminais, e o lado direito poderá conter
terminais e não terminais em sua composição.
Definições recursivas
Vamos conhecer, agora, as definições recursivas referentes às gramáticas regulares:
Quaisquer terminais, ou seja, os símbolos que pertencem a Σ, são ER. A cadeia nula (λ) e o conjunto
nulo (Ø) também são ER;
Se P e Q são duas ER, então a união das duas ER denotadas por P + Q também é uma ER;
Se P e Q são duas ER, então sua concatenação denotada por PQ também é uma ER;
Se P for uma ER, então a iteração (repetição ou fechamento) denotada por P* também é uma ER;
Se P é uma ER, então (P) é uma ER;
As expressões obtidas pela aplicação repetida das regras de (1) a (5) em ∑ também são ER.
Operações sobre ER
Vejamos as três operações básicas sobre ER:
1. 
2. 
3. 
4. 
5. 
6. 
União
Se R1 e R2 são duas ER em , então L (R1 U R2) é denotado por:
 ou 
Concatenação
Se R 1 e R 2 são duas ER em , então é denotado por .
 é uma cadeia de R1 seguido por uma cadeia de R2.
Fechamento
Se R1 e R2 são duas ER em , então é uma cadeia obtida pela concatenação de n
elementos para .
Fechamento de Kleene
É definido como um conjunto de todas as cadeias, incluindo a cadeia vazia (λ), obtido a partir dos alfabetos do
conjunto Σ. É denotado como Σ*.
Se o alfabeto não contiver a cadeia vazia (λ), ele será representado por:
Vejamos um exemplo de uma ER. Sejam as seguintes regras:
Se , então 
Se , então 
Se , então, 
Se , então, 
Uma ER consiste em qualquer combinação de a e b, começando e terminando com b.
Uma linguagem de qualquer combinação de a e b contendo bb como subcadeia.
ER de a e b contendo pelo menos 2 'b's e qualquer número de a e b entre eles.
ER para a linguagem L = {anbm | onde m ≥ 2 e n ≥ 0}.
Utilizando a notação do fechamento de Kleene, chegamos à seguinte expressão: 
A ER consiste em qualquer combinação de a e b, ou seja, (a + b)* no meio da expressão. Mas a ER começa e
termina com b. Entre b e b, qualquer combinação de a e b ocorre.
A linguagem Ɲ formada pelos números naturais decimais é um conjunto regular sobre o alfabeto dos
algarismos arábicos e pode ser representada pelo seguinte conjunto regular:
Em que o * representa todas as combinações de números naturais, incluído nenhumalgarismo. O primeiro
conjunto indica que os números devem começar por um algarismo entre 0 e 9 e podem ser seguidos de zero
ou mais algarismos concatenados. Se D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, então, Ɲ = DD*.
Conceitos sobre teoria dos conjuntos e grafos
Neste vídeo, serão apresentados exemplos sobre a teoria dos conjuntos e grafos e sua aplicação no tema em
exemplos práticos de computação.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
A gramática
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Hierarquia de Chomsky
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
1. 
2. 
3. 
4. 
Verificando o aprendizado
Questão 1
O conjunto de todas as cadeias de {0, 1} com exatamente dois zeros é:
A
1*01*01*
B
(0 + 1)*11
C
{11 + 0}*
D
{00 + 11}*
E
(001)*
A alternativa A está correta.
De acordo com o fechamento de Kleene, a alternativa E contém a cadeia nula, o que vai contra o
enunciado. O mesmo acontece com as alternativas C e D. A alternativa B só garante a existência de dois
símbolos "1". Portanto, a única alternativa que satisfaz o enunciado é a letra A.
Questão 2
Analise a seguinte ER:
 
ER consiste em qualquer combinação de a e b, começando com a e terminando com b.
Linguagem de qualquer combinação de a e b, contendo ab como subcadeia.
ER de a e b contendo pelo menos um a e um b e qualquer número de a e b entre eles.
 
Assinale a alternativa que gera a expressão em notação do fechamento de Kleene para essa ER:
A
L = b (a + b) * b
1. 
2. 
3. 
B
L = a (a + b) * b
C
L = (a + b)*ab(a + b)*
D
a*b*
E
(ab)*
A alternativa B está correta.
Para atender às regras I e II, há necessidade de que a cadeia comece por a e termine por b. Se isso for
satisfeito, a regra III também será satisfeita. Entre a e b pode haver qualquer número de ocorrências de a e
b, inclusive em quantidades diferentes. A única alternativa que satisfaz todas as condições é a letra B.
2. Autômatos finitos
Conceitos básicos
Teoria dos autômatos
A teoria dos autômatos é o estudo de máquinas
abstratas e problemas computacionais
relacionados a essas máquinas, chamadas de
autômatos. A palavra “autômato” remete a
alguma coisa que está fazendo algo por si
mesma, de forma independente, guardando
alguma similaridade com o termo automático.
Como vimos antes, em meados de 1950, o
linguista norte-americano Noam Chomsky
estruturou uma hierarquia de linguagens
formais com base nas propriedades das
gramáticas necessárias para gerar essas linguagens.
Os autômatos finitos podem ser aplicados em diferentes áreas da Ciência da Computação, bem como da
Engenharia. Podemos citar os seguintes exemplos:
Corretores ortográficos Dicionários multilíngues
Compactação de texto
É possível que a aplicação mais tradicional seja encontrada na construção de compiladores, onde tais
autômatos podem ser usados para modelar e implementar analisadores léxicos.
Em um computador, todos os processos parecem ser feitos automaticamente. Veja o que ocorre a seguir na 
CPU:
CPU
Não estamos preocupados com o funcionamento interno da CPU, mas apenas com a entrada e a saída. 
A partir dessa discussão, fica claro que a CPU executa as operações da máquina internamente. Em
autômatos, aprenderemos como projetar tais máquinas.
Entrada 
Uma entrada é processada na CPU. A
entrada é convertida em '0' e '1' e atribuída
ao processo para o qual foi fornecida.
Saída 
Uma saída é gerada. O computador
realiza operação interna no circuito
eletrônico e gera a saída no formato '0' e
'1', que é convertida em formato
compreensível pelo usuário que a
recebe.
Para se comunicar com um computador, o usuário precisa de uma linguagem chamada de linguagem de
programação. C, C++, C# e Java são alguns exemplos de linguagens de programação, que possuem como
característica principal semelhanças ao idioma inglês e são facilmente compreensíveis pelo usuário. No
entanto, o computador entende apenas números binários.
Os computadores têm um compilador que verifica a sintaxe e atua como um conversor entre as declarações
do tipo inglês para números binários e vice-versa. Mas, para projetar o compilador, é necessária uma
gramática para a linguagem em questão. A gramática é o construtor de qualquer linguagem. Da mesma forma,
as linguagens usadas para fins de programação de computadores têm alguma gramática para construí-las.
Alguns empregos da teoria dos autômatos em diferentes campos da Ciência da Computação e Engenharia são
os seguintes:
Projeto do compilador
É projetada pelos autômatos finitos. Na parte de análise de sintaxe, um erro comum (chamado de erro
de sintaxe) é verificado pelas regras da gramática livre de contexto.
Princípio de funcionamento do software
É utilizado para verificar o comportamento de circuitos digitais.
Software para Processamento de Linguagem Natural (PLN)
É ajudado pela teoria dos autômatos.
Autômatos úteis na projeção do software
É contado para contar a ocorrência de uma palavra, um padrão etc. em um texto grande.
Características de um autômato
Um autômato finito (AF), também conhecido como máquina de estados finita (MEF), fornece o modelo mais
simples de um dispositivo de computação, possuindo um número finito de estados. O estado do sistema
memoriza as informações relativas à entrada anterior. A partir daí, é necessário determinar o comportamento
futuro do sistema, ou seja, qual o próximo estado a ser atingido a partir daquela entrada específica.
Um AF é um modelo matemático usado para representar programas de computador ou circuitos lógicos. O
conceito é entendido como uma máquina abstrata que deve estar em algum estado de um número finito de
estados. A máquina está em apenas um estado por vez. Esse estado é chamado de estado atual, que exerce
as seguintes funções:
1
Armazenamento de informações sobre o passado
Reflete as mudanças desde a entrada em um estado, no início do sistema, até o momento
presente.
2
Descrição de nó de comportamento do sistema
Está à espera de uma condição para executar uma transição.
3
Transição indicadora de mudança de estado
Descrita por uma condição que precisa ser realizada para que esta transição ocorra.
Autômatos finitos podem modelar muitos problemas, entre os quais estão:
A automação de design eletrônico;
O projeto de protocolo de comunicação;
A análise e outras aplicações de engenharia.
Na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por
vezes, utilizadas para descrever sistemas neurológicos e, em linguística, para descrever as gramáticas das
linguagens naturais.
Planos paralelos ou ortogonais aos planos e eixos
cartesianos
Agora, vamos usar o conceito estudado no item anterior para verificar os planos paralelos e ortogonais aos
planos cartesianos.
Lembrando os vetores normais aos planos coordenados: é normal ao plano é normal
ao plano e é normal ao plano .
• 
• 
• 
 
Assim:
 
Planos paralelos ao plano têm equação do tipo rea
Planos paralelos ao plano têm equação do tipo real;
Planos paralelos ao plano têm equação do tipo real;
Planos ortogonais ao plano têm equação do tipo e reais;
Planos ortogonais ao plano têm equação do tipo e reais;
Planos ortogonais ao plano têm equação do tipo e reais.
Ao compararmos as equações de um plano e de uma reta pode ser verificado se eles são paralelos ou
ortogonais, isso é, que apresentam um ângulo de entre si. Se o plano e a reta são paralelos entre si, o
vetor diretor da reta será perpendicular ao vetor normal ao plano , assim seu produto escalar é nulo.
Se o plano e a reta são ortogonais entre si, o vetor diretor da reta será paralelo ao vetor normal ao plano 
, logo seu produto escalar é nulo.
Exemplo 1
Determine o valor de k para que os planos e a reta sejam ortogonais.
Solução
Se a reta e o plano são ortogonais, então o vetor diretor da reta éparalelo ao vetor normal do plano.
O vetor normal do plano é e o vetor diretor da reta . Para serem paralelos, as
coordenadas devem ser proporcionais:
Exemplo 2
Verifique se o plano e a reta são paralelos.
Solução
Se a reta e o plano são paralelos, então o vetor diretor da reta é ortogonal ao vetor normal do plano.
O vetor normal do plano é e o vetor diretor da reta .
• 
• 
• 
• 
• 
• 
Ser 
Ser .
.
Assim, a reta e o plano são ortogonais.
 
Seguindo esse conceito das condições de ortogonalidade e de paralelismo entre reta e plano podemos agora
analisar as equações dos planos que serão paralelos e ortogonais aos eixos coordenados.
Eixo z
Planos paralelos ao eixo têm equação do tipo
, a, b e k reais.
Eixo y
Planos paralelos ao eixo y têm equação do tipo 
 e k reais.
Eixo x
Planos paralelos ao eixo têm equação do
tipo e k reais.
Observem que são os mesmos planos ortogonais, respectivamente, aos planos XY, XZ e YZ.
Eixo z
Planos ortogonais ao eixo têm equação do
tipo real.
Eixo y
Planos ortogonais ao eixo y têm equação do
tipo real.
Eixo x
Planos ortogonais ao eixo têm equação do
tipo real.
Observem que são os mesmos planos paralelos, respectivamente, aos planos XY, XZ e YZ.
 
Caso seja do seu interesse estudar mais as posições relativas entre reta e planos, bem como a obtenção de
ângulos entre reta e planos, o assunto pode ser aprofundado ao consultar as referências deste conteúdo.
Funcionamento
Sistema transicional
O autômato finito é um sistema transicional em que cada nó ou vértice representa um estado, e um arco
direcionado indica uma transição de estado. O rótulo dado a esse arco representa uma entrada, uma saída ou
ambos.
Uma função transicional tem duas propriedades. São elas:
f(q, λ) → q, ou seja, uma entrada nula faz com que o AF permaneça no mesmo estado;
Para toda cadeia w e uma entrada “a” pertencente ao alfabeto, temos:
01 D
45 3
01 D
45 E
01 D
46 4
01 D
44E
01 D
45 3
01 D
45 3
01 D
45 E
01 D
46 4
01 D
44E( , )―→ ( ( , ), )
01 D
45 3
01 D
45 E
01 D
44E
01 D
46 4
01 D
45 3
01 D
45 3
01 D
45 E
01 D
44E
01 D
46 4( , )―→ ( ( , ), ).
Aceitação de uma cadeia por AF
Para que uma cadeia seja aceita por um AF, existem duas condições a serem satisfeitas:
A cadeia deve ser totalmente percorrida;
O AF deve chegar a um estado final, ou seja, parar em um estado final.
Resumindo
Podemos dizer que, se f(q0, w) = qn (em que w é a cadeia dada como entrada para o AF, q0 é o estado
inicial, e qn pertence ao conjunto de estados finais), então a cadeia w pode ser considerada aceita pelo
AF. 
Veja a seguir as consequências de quando as duas condições são atendidas e quando não são ou quando
uma delas não é:
Atendidas
Poderemos declarar uma cadeia como aceita
pelo AF.
Não atendida ou não atendidas
Poderemos declarar uma cadeia como não
aceita pelo AF.
Vamos usar como exemplo o AF descrito na tabela anterior. Observe as etapas do processo:
1
Um caractere lido por vez
Para verificar se uma cadeia é aceita por esse AF, assumiremos que a cadeia de entrada começa a
ser varrida pelo controle finito no estado inicial q0. Mas uma única entrada é fornecida em cada
pulso de clock, ou seja, apenas um caractere por vez é lido.
2
A entrada para o estado recém-alcançado
Assim, inicialmente, a entrada para o estado inicial q0 é franqueada ao caractere mais à esquerda. A
partir da função de transição dada na tabela, o próximo estado é determinado. O próximo caractere
da cadeia é tratado como a entrada para o estado recém-alcançado, que pode ser o mesmo (não
houve mudança de estado).
1. 
2. 
1. 
2. 
3 A cadeia não aceita
Esse processamento segue até que a cadeia seja finalizada ou o AF pare em um estado que não
pertence ao conjunto de estados finais. Nesse caso, a cadeia não foi aceita.
Vamos considerar a seguinte cadeia de entrada: 0110. Inicialmente, o controle finito tem sua cabeça de leitura
apontada para o símbolo inicial da fita. No instante em que o AF começa a funcionar, ele pula
automaticamente para o primeiro caractere da cadeia a ser lido, que é “0”. Observe:
Cadeia de entrada 0110.
Podemos chegar às seguintes conclusões:
Pelas regras de transição mostradas na tabela e acompanhando a forma gráfica desse AF, ele
permanece no estado q0;
A próxima entrada é “1”. Nesse caso, o AF muda para o estado q1 e lê o próximo caractere, que é outro
“1”, o que faz com que o AF permaneça no estado q1;
O último caractere da cadeia é “0”. O AF muda para o estado final q0 e para, porque terminou a leitura
da cadeia de entrada.
Percebemos que a cadeia foi totalmente percorrida, e o AF chegou a um estado final, ou seja, parou em um
estado final.
As duas condições para que uma cadeia fosse aceita pelo AF foram satisfeitas. Em outras palavras,
a cadeia foi reconhecida pelo AF. Isso significa que ela pertence à linguagem regular reconhecida
por esse autômato.
Vejamos outro exemplo. Seja a cadeia de entrada igual a 01011. Neste caso, veja:
1
Com a entrada “0”
Continuamos no estado q0.
2
Com a entrada “1”
O AF muda para o estado q1.
• 
• 
• 
3 Ao ler o caractere “0”
O AF volta ao estado q0.
4
Ao ler o “1”
O AF muda novamente para q1.
5
Ao ler o último “1”
O AF permanece em q1.
Como não há mais entradas para serem lidas, o AF para em q1, que não é um estado final. Portanto, o AF não
reconhece a cadeia 01011 como pertencente às expressões regulares que ele reconhece.
Quais são as ER que esse autômato reconhece?
Faça uma tentativa antes de continuar a leitura. Vai ajudar a ampliar seu raciocínio. Consideremos o raciocínio
a seguir:
1
AF reconhece a cadeia nula
Uma vez que o estado inicial é também um estado final. No início do processamento, o AF está em
q0. Logo, ele reconhece λ.
2
AF reconhece cadeias com qualquer número de “0”
Não importa seu tamanho, porque ele permanece em q0 enquanto lê na entrada “0”.
3
AF muda para o estado q1 ao ler uma entrada “1”
Ali permanece até que leia outro “0” como entrada, quando, então, volta ao estado final q0. Aqui, ele
reconhece qualquer cadeia terminada em “0”. Caso contrário, ele não sai de q1.
Em síntese, o AF reconhece cadeias com qualquer número de zeros, incluindo nenhum zero (λ) e todas as
cadeias com quaisquer números de “0” e “1”, desde que terminem em zero.
Exemplos práticos
Exemplo 1
Vamos ver como se comporta o AF a seguir e qual expressão regular ele reconhece.
Representação de AF.
Esse AF pode ser descrito pela seguinte tabela:
Representação tabular de AF.
Vamos considerar a cadeia de entrada 0110 a seguir:
No instante em que o AF começa a funcionar, ele lê o primeiro caractere da cadeia, que é “0”. Pelas
regras de transição mostradas na tabela e acompanhando a forma gráfica desse AF, ele permanece no
estado q0;
A próxima entrada é “1”. Nesse caso, o AF muda para o estado q1 e lê o próximo caractere, que é outro
“1”, o que faz com que o AF retorne ao estado q0;
O último caractere da cadeia é “0”, e o AF permanece no estado final q0 e para.
Percebemos que a cadeia foi totalmente percorrida, e o AF chegou a um estado final, ou seja, parou em um
estado final. 
As duas condições para que uma cadeia fosse aceita pelo um AF foram satisfeitas. Em outras
palavras, a cadeia foi reconhecida pelo AF.
Vejamos outro exemplo. Seja a cadeia de entrada igual a 01011. Neste caso:
1
Com a entrada “0”
Continuamos no estado q0.
• 
• 
• 
2 Com a entrada “1”
O AF muda para o estado q1.
3
Ao ler o caractere “0”
O AF permanece em q1.
4
Ao ler o “1”
O AF muda para q0.
5
Ao ler o último “1”
O AF volta para o estado q1.
Como não há mais entradas para serem lidas, o AF para em q1, que não é um estado final. Portanto, o AF não
reconhece a cadeia 01011 como pertencente às expressões regulares que ele reconhece. 
Quais são as ER que esse autômato reconhece?
Novamente, faça uma tentativa antes de continuar a leitura. Experimente com algumas outras cadeias que
ajudem a inferir a resposta. Consideremos o raciocínio a seguir:
1
AF reconhece a cadeia nula
Uma vez que oestado inicial é também um estado final. No início do processamento, o AF está em
q0. Logo, ele reconhece λ.
2
AF reconhece cadeias com qualquer número de “0”
Não importa seu tamanho, porque ele permanece em q0 enquanto lê na entrada “0”.
3
AF muda para o estado q1 ao ler uma entrada “1”
Ali permanece até que leia outro “1” como entrada, quando, então, volta ao estado final q0. Ele
reconhece qualquer cadeia com um número par de “1”. Caso contrário, ele para em q1.
Em síntese, o AF reconhece cadeias com qualquer número de zeros, incluindo nenhum zero (λ) e todas as
cadeias que tenham um número par de “1”. As cadeias com número ímpar de caracteres “1” não serão aceitas
por esse AF.
Exemplo 2
Vejamos o AF descrito a seguir:
Representação de AF.
Vamos elaborar a tabela de transição de estados desse AF.
Notamos que a entrada “1” em q0 leva o AF ao estado q1. A entrada “0” leva o AF ao estado q2. Estando em
q1, uma entrada “1” faz com que o AF volte ao estado q0, e uma entrada “0” faz com que o autômato mude
para o estado q3, e assim sucessivamente. Portanto, temos:
Representação tabular de AF.
AF aceita as seguintes cadeias:
Cadeia vazia (λ), pois o estado inicial é
igual ao final.
Cadeias do tipo “00” ou “11”.
Cadeias como 0101 ou 1010. Cadeias que são compostas por um
número par de zeros e uns.
Verifique que tal AF não aceita esta cadeia: 0101110. Após a leitura da cadeia, o AF para no estado q2. Caso
retiremos o último zero dessa cadeia, ela se torna 010111 e passa a ser aceita. Assim, podemos inferir que
esse AF reconhece qualquer cadeia que tenha um número par de zeros e uns.
Tipos
Autômatos Finitos com saída
Observe na imagem a seguir que os estados q1 e q2 apresentam o valor de saída de cada um,
respectivamente. Em outras palavras, cada vez que a máquina passar pelo estado q1, emitirá uma saída “1”, e
cada vez que passar pelo estado q2, emitirá uma saída “0”:
Representação dos autômatos q1 e q2.
Note que q1 é um estado final. Assim, podemos imaginar que, toda vez que o AF reconhecer uma cadeia,
emitirá a saída “1”. Quando ele para em q2, a saída é “0”, indicando que não reconheceu a cadeia de entrada.
Logo, teremos uma cadeia de saída representando todas as vezes em que os estados foram visitados.
Quando essa cadeia termina em “1”, o AF reconheceu a cadeia. Caso contrário, a cadeia termina em “0”.
Vamos considerar a seguinte cadeia de entrada: 0110. Vejamos o processo a seguir:
1
Leitura do primeiro zero
Ao ler o primeiro zero, o AF permanece em q1 e emite um “1”.
2
Leitura de “1”
Ao ler o caractere seguinte (“1”), o AF muda para o estado q2 e emite “0”.
3
Leitura do próximo “1”
Ao ler o próximo “1” no estado q2, o AF volta para o estado q1 e emite “1”.
4 Leitura do “0”
Ao ler o caractere “0” no estado q1, o AF emite a saída “1”, parando neste estado final, porque a
cadeia terminou. Isso indica que o AF reconheceu a cadeia.
Esse processo gera a seguinte cadeia de saída: 1011. Note que, para esse caso, as saídas intermediárias não
são relevantes. Apenas o caractere final é significativo. Caso o caractere final seja “0”, a cadeia não foi
reconhecida. Caso seja “1”, a cadeia foi reconhecida.
A seguir, apresentamos a tabela de transição de estados desse AF:
Tabela de transição de estados.
Note que, nesse caso, o AF retrata as características básicas de um computador. São elas:
As operações da máquina são sincronizadas por ciclos discretos;
A máquina opera de forma determinística. Suas ações em resposta a uma sequência de entrada são
completamente previsíveis;
A máquina responde a entradas, apresentando saídas;
Existe um número finito de estados que a máquina pode alcançar. A qualquer momento a máquina está
em, exatamente, um desses estados;
A máquina é capaz de produzir saídas. A natureza da saída é uma função do estado atual da máquina,
o que significa que também depende das entradas anteriores.
O estado da máquina a qualquer momento serve como uma espécie de memória das entradas anteriores.
Autômatos finitos de duas vias ou bidirecionais
Até o momento, estudamos autômatos em que a cabeça de leitura se move apenas em uma direção: da
esquerda para a direita. Vamos apresentar, agora, os autômatos finitos de duas vias ou bidirecionais. São
máquinas que podem percorrer (ler) uma cadeia de entrada em ambas as direções (esquerda e direita).
Veja o diagrama esquemático a seguir:
Diagrama de autômatos finitos bidirecionais.
1. 
2. 
3. 
4. 
5. 
Considere o seguinte autômato finito determinístico bidirecional (2AFD), dado por sua tabela de transição de
estados:
Tabela de transição de estados.
Na tabela anterior de transição de estados, R significa que a cabeça de leitura se move em direção à direita
(Right), e L significa que a cabeça de leitura se move em direção à esquerda (Left). O estado inicial é A, e o
estado final é B.
Vamos utilizar a cadeia 101001 e verificar se ela é aceita pelo 2AFD ou não. Para isso, vamos seguir as
transições de acordo com a tabela anterior:
(A, 101001) → (B, 01001R) → (B, 1001R) → (C, 01001L) → (A, 1001R) → (B, 001R) → (B, 01R) → (B, 1R) → (C,
01L) → (A, 1R) → B
Após a leitura de todos os caracteres da cadeia, chegamos ao estado final. Assim, a cadeia 101001 é aceita
pelo 2AFD.
Representação de Autômato Finito
Neste vídeo, serão descritas a representação com fita de entrada e cabeça de leitura, a representação gráfica
e a representação tabular.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Conceitos básicos: uso de autômatos
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Autômatos finitos com saída
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Considere o seguinte AF:
Representação de AF.
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
A
011, 010, 0010, 110
B
010, 1, 00100, 111
C
00, 11, 001100, 011
D
001, 010, 0011, 1100
E
000, 1111, 1010, 0101
A alternativa B está correta.
A cada entrada "1", o autômato muda de estado e só para no estado final q1, quando o número de "1" na
cadeia for ímpar.
Questão 2
Considere o seguinte AF:
Representação de AF.
Assinale a alternativa em que todas as cadeias são aceitas por esse autômato:
A
011, 010, 0010, 110
B
010, 1, 00100, 111
C
0010, 0111, 1101, 0100
D
001, 010, 0011, 1100
E
000, 1111, 1010, 0101
A alternativa C está correta.
Esse AF só para no estado final q3 quando a entrada contiver um número ímpar de zeros e uns. Caso
contrário, ele para em estados não finais e não reconhece a cadeia.
3. Autômatos Finitos Não Determinísticos
Características e representação
AFN e AFD
Os autômatos finitos apresentados são conhecidos como:
Apesar de o AFN apresentar similaridades de leitura com o AFD, a diferença é que existe pelo menos um
estado em que, ao ler o mesmo símbolo, há mais de uma possibilidade de estado a ser atingida, ou seja,
alguns movimentos da máquina não podem ser determinados exclusivamente pelo estado atual e pelo símbolo
de entrada atual.
Assim, o próximo estado é um elemento do conjunto das partes dos estados. Esse elemento (um conjunto)
representa algum subconjunto de todos os possíveis estados que podem ser considerados.
Os AFN reconhecem expressões regulares e podem ser convertidos em seu equivalente AFD.
Como representar um AFN?
Vejamos como um AFN pode ser representado.
M = {Q, I, fs, q0, F} é um AF se:
Q
Conjunto de estados.
I
Conjunto finito de símbolos de entrada (alfabeto de entrada).
Função de transição de estados, onde 2Q é o conjunto de todos os subconjuntos de Q.
Estado inicial.
F
Conjunto de estados finais.
Considere o seguinte exemplo de tabela de transição de estados:
Autômato finito determinísticos (AFD) 
Lê um determinado símbolo de entrada,
dado seu estado atual, existindo apenas um
próximo estado possível a ser atingido.
Autômato finitonão determinístico (AFN) 
Lê uma cadeia de símbolos de entrada.
Para cada símbolo, ocorre uma
transição para novo estado, até que
todos os símbolos de entrada tenham
sido lidos.
Tabela de transição de estados.
Aqui, para o estado q0 e a entrada 0, o AFN decide ir para q0 ou q1. Para um AFD, é fácil determinar se uma
cadeia é aceita por ele ou não. No entanto, para um AFN, essa tarefa é mais difícil.
Vejamos a representação gráfica desse AFN:
Representação de AFN.
Observando esse AF, percebemos o seguinte:
Essa decisão é aleatória. Nos outros estados (q1 e q2), permanece o determinismo, e a cada entrada, ocorre a
mudança para apenas outro estado.
Para exemplificar melhor, vamos testar se a cadeia 00101 é aceita por esse AFN. Como sabemos, uma cadeia
é aceita caso o AF termine o processamento em um estado final. Do contrário, a cadeia não é reconhecida.
Para facilitar a explicação, vamos utilizar o diagrama de transição de estados a seguir:
Entrada “1” 
No estado q0, ao receber uma entrada “1”, o
AFN muda para o estado q2.
Entrada “0” 
No estado q0, ao receber uma entrada
“0”, ele permanece em q0 ou muda
para q1.
Diagrama de transição de estados.
Observando o diagrama de transição, constatamos o seguinte:
1
Três caminhos
De q0 para a cadeia de entrada 00101, obtemos três caminhos.
2
Estado final q2
Na cadeia 00101, podemos percorrer um dos três caminhos e chegar aos últimos estados: q1, q2 e
q1, respectivamente. Entre eles, q2 é o estado final.
3
Cadeia 00101 aceita pela AFN
Para a cadeia 00101 entrando em q0 (estado inicial), podemos chegar a um estado final. Assim, a
cadeia 00101 é aceita pelo AFN.
4
Caminho seguido pelo AFN
Se alguém seguir o caminho 1 ou o caminho 3, porém, não será possível chegar ao estado final.
Então, podemos declarar que a cadeia não é aceita pelo AF. Isso significa que o reconhecimento ou
não da cadeia depende do caminho seguido pelo AFN.
Em síntese, uma cadeia w será aceita por um AFN se houver algum caminho que permita que o AFN atinja
algum estado final após percorrer a cadeia. Inversamente, uma cadeia é rejeitada por um AFN se nenhum
caminho de transições levar o autômato a um estado final, após ler toda a cadeia.
AFD são equivalentes em poder de expressão a AFN. Isso ocorre porque, primeiramente, qualquer AFD é
também um AFN. Então, AFN podem expressar o que AFD expressam.
Além disso, dado um AFN, por meio de uma construção do conjunto das partes, é possível construir um AFD
que reconheça a mesma linguagem que determinado AFN. O AFD equivalente também pode precisar de um
número maior de estados que o AFN.
Conversão
Como converter AFN em AFD?
Para responder essa pergunta, consideremos o seguinte:
Para um AFN, a máquina pode ir a mais de um estado para uma única entrada dada a um único estado.
Portanto, para um AFN, é difícil decidir se uma cadeia será aceita ou não. Se um AFN puder ser convertido em
um AFD, esse tipo de problema não surgirá.
Isso significa que temos de converter para , em que é o conjunto finito de
estados para um AFN, e Q' é o conjunto de estados para o AFD convertido.
O processo de conversão acontece da seguinte forma:
1
Estado inicial do AFN
Comece do estado inicial do AFN. Pegue o estado dentro de [ ].
2
Próximos estados para o estado inicial
Coloque os próximos estados para o estado inicial (aqueles na mesma linha) nas entradas
fornecidas nas colunas do próximo estado. Coloque-os também em [ ].
3
Combinação de estado na coluna de estado atual
Pegue essa combinação de estado na coluna de estado atual, se qualquer nova combinação de
estado aparecer na próxima coluna de estado, que ainda não tenha sido tomada na coluna de
estado atual.
4
A combinação de cada um dos estados seguintes
Combine cada um dos estados seguintes, se na coluna de estado atual aparecer mais de um
estado.
5
Nenhuma nova combinação de estado
Interrompa o processo, se não aparecer nenhuma nova combinação de estado, que ainda não tenha
sido tomada na coluna de estado atual.
6
Estado inicial do AFN
Veja que estado inicial do AFD construído será o estado inicial do AFN.
Para um AFD 
fs é um mapeamento de função de
transição Q x I → Q.
Para um AFN 
fs é um mapeamento de função de
transição , em que é o
conjunto potência de Q.
7 A combinação de estados que contém um estado final
Conclua que o estado final ou estados finais para a construção do AFD será a combinação de
estados contendo pelo menos um estado final.
Vamos fazer um exercício prático para fixar esse processo utilizando o exemplo anterior.
Seja a tabela de transição de estados a seguir:
Tabela de transição de estados.
Seguindo os passos do algoritmo anterior, é possível gerar a seguinte tabela de transição de estados:
Tabela de transição de estados.
Vamos substituir [q0] por A, [q0, q1] por B, [q1, q2] por C, [q0, q1, q2] por D, [q2] por E e [q1] por F. Então, a
tabela de transição de estados construída é esta:
Tabela de transição de estados.
Nesse AF, podemos ver que, para determinada entrada, ele muda para um único estado por vez. Logo, é um
AFD. O estado inicial é [q0], agora denominado A. Os estados finais são [q1, q2], C, [q0, q1, q2], D e [q2],
agora denominado E.
Vejamos a representação gráfica desse autômato:
Representação do autômato.
Vamos mostrar mais um exemplo para fixação do conteúdo.
Seja o AFN da tabela de transição de estados a seguir, em que o estado inicial é q0 e o estado final é q3:
Tabela de transição de estados.
Aplicando as regras de 1 a 7, vistas anteriormente, transformamos esse AFN em um AFD. A seguir, o primeiro
passo:
Tabela de transição de estados.
Vamos substituir [q0] por A, [q0, q1] por B, [q0, q1, q2] por C, [q0, q1, q3] por D e [q0, q1, q2, q3] por E. Assim,
a tabela de transição de estado do AF construído é esta:
Tabela de transição de estados.
O estado inicial é A. Os estados finais são D e E. O diagrama de transição de estados fica desta forma:
Diagrama de transição de estados.
Conversão de um AFN em AFD
Neste vídeo, será descrita a conversão de um autônomo finito não-determinístico para um determinístico.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Características e representação de AFN
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Representação
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
(POSCOMP - SBC - 2012) Seja um autômato finito não determinístico (AFN) com seis estados. Aplicando-se o
algoritmo de conversão de um AFN para um autômato finito determinístico (AFD), em quantos estados, no
máximo, resultaria o AFD, considerando-se os estados redundantes?
A
12
B
36
C
64
D
1024
E
46656
A alternativa C está correta.
Na conversão de AFN para AFD, se o AFN possui n estados, ao fazer a conversão para AFD o autômato
passa a ter 2n estados. Portanto, como o AFN tem seis estados, o AFD resultante da conversão terá, no
máximo, 26 estados, ou seja, 64.
Questão 2
Um autômato finito determinístico (AFD) pressupõe que, a partir de um estado atual, exista apenas um
próximo estado possível a ser atingido. Já em um autômato finito não determinístico (AFN), ao ler um símbolo,
há mais de uma possibilidade de estado a ser atingido. Assinale a alternativa cuja função permite que um AFN
seja convertido em seu equivalente AFD:
A
Q × I → Q
B
Q × I → 2Q
C
Q × I → 2n
D
Q × I → Qn
E
Q x Q → In
A alternativa B está correta.
Para converter um AFN em um AFD, é necessário realizar a conversão de todos os conjuntos de estados
em estados únicos. Dessa forma, os Q estados do AFN darão lugar a 2Q estados no AFD.
4. Fundamentos de linguagens regulares
Principais definições
Expressões Regulares
A expressão regular (ER) é a linguagem da gramática tipo 3 na hierarquia de Chomsky, chamada de gramática
regular, como já vimos. Uma ER é aceita pela máquina denominadaautômato finito (AF).
As ER se tornaram úteis no programa de processamento de texto no sistema operacional Unix, conhecido
como “grep”, e nas linguagens de programação modernas, como “PERL”. Um cientista da computação
canadense chamado Henry Spencer escreveu a biblioteca “regex”, que é amplamente usada como uma
biblioteca de software para ER.
Essas expressões são chamadas de “regulares” porque descrevem uma linguagem com
propriedades muito constantes.
Uma ER pode ser definida como qualquer cadeia que seja aceita por um AF. Uma expressão regular é escrita
como ER, regex ou regexp.
Relembrando
Recapitulando, as operações sobre ER são a união, a concatenação e o fechamento. Em adição,
apresentamos o fechamento de Kleene. Neste ponto, vamos ver a diferença entre o fechamento simples
e o fechamento de Kleene. 
Fechamento simples e fechamento de Kleene
Vejamos a definição e propriedades dos dois tipos de fechamento:
Conjuntos regulares
Conjuntos e expressões regulares são notações alternativas utilizadas para representar a classe de linguagens
mais simples que se conhece dentro da hierarquia de Chomsky.
Conjuntos regulares sobre um alfabeto finito Σ são linguagens definidas recursivamente da seguinte forma:
É um conjunto regular sobre Σ.
{λ}
É um conjunto regular sobre Σ.
É um conjunto regular sobre Σ.
Se X e Y são conjuntos regulares sobre Σ, então também são conjuntos regulares sobre Σ:
(X);
01D
44B
01D
44C∪ ;
X · Y, também denotado XY;
X*.
Diz-se que determinado subconjunto de Σ* é um conjunto regular se ele puder ser formulado por meio do uso
combinado dessas regras apenas.
Exemplo
Seja L = {0m 1n | m ≥ 0, n ≥ 0} sobre o alfabeto Σ = {0, 1}. A linguagem L é formada por sentenças em
que a concatenação de um número arbitrário de símbolos “0” (incluindo λ) se relaciona com uma cadeia
resultante da classificação de um número também arbitrário de símbolos “1” (incluindo λ). Assim,
temos: L = {λ, 0, 1, 00, 01, 11, ...} 
Consideremos as linguagens sobre Σ mostradas a seguir:
Fechamento simples 
É a iteração
de 0 a ∞
vezes, onde
sua
aplicabilidade
é em ER
 
Se R = 01, então o
fechamento simples em R
denotado por R* são λ, 01,
0101, 010101, ..., ou seja, a
iteração da mesma cadeia 01.
Fechamento de Kleene 
É o conjunto
incluindo λ,
onde sua
aplicabilidade
é em Σ.
 
Se Σ = {0, 1}, então o
fechamento de Kleene é
denotado por Σ* = { λ, 0, 1, 01,
00, 11, 010, 011, 100, ...}, ou seja,
o conjunto de quaisquer
combinações de 0 e 1
incluindo λ.
1. 
2. 
3. 
4. 
Por definição, os conjuntos L1 e L2 são regulares sobre Σ. L3 = L1*, e L4 = L2* são conjuntos regulares
também, uma vez que são obtidos a partir de L1 e L3, respectivamente. O conjunto L5 pode ser obtido pela
concatenação de L5 = L3.L4. Em notação dos conjuntos regulares, essa linguagem pode ser expressa por: {0}
*{1}*.
Recursividade
Da mesma forma como ocorre nos conjuntos regulares, as expressões regulares sobre um alfabeto Σ também
podem ser definidas recursivamente da seguinte maneira:
É uma expressão regular e denota o conjunto
regular .
λ
É uma expressão regular e denota o conjunto
regular {λ}.
E uma expressão regular e denota o conjunto
regular {σ}, σ Σ.
Se x e y são expressões regulares sobre Σ que denotam os conjuntos regulares X e Y, então também são
expressões regulares:
(x)
Denota o conjunto regular X.
x|y ou x + y
Denota o conjunto regular X U Y.
x.y ou xy
Denota o conjunto regular XY.
Denota o conjunto regular .
Note que, nas expressões regulares, é possível eliminar o uso dos símbolos “{” e “}”, bem como substituir o
operador “∪” pelo operador “+” ou pela barra vertical “|”. Além disso, podemos utilizar precedência sobre os
operadores para as três operações sobre expressões regulares, o que reduz o emprego de parênteses. Veja a
tabela a seguir:
Operações sobre expressões regulares.
L1 = {0} L2 = {1} L3 = {0i | i ≥ 0} L4 = {1i | i ≥ 0} L5 = {0p 1q| p, q ≥ 0}
Propriedades
Lema do bombeamento
O lema do bombeamento (pumping lemma) descreve uma propriedade fundamental das linguagens regulares.
Para qualquer linguagem regular L, existe um número p, tal que qualquer cadeia w de comprimento
igual ou maior que p pode ser dividida em três subcadeias, e a parte do meio (não vazia), y, pode ser
repetida um número arbitrário de vezes (inclusive nenhuma vez, o que significa remover y), gerando
uma nova cadeia que também pertence a L.
Vejamos como podemos formalizar essa propriedade.
Seja L uma linguagem regular. Então, existe um inteiro p ≥ 1 (chamado de “comprimento de bombeamento”) tal
que cada cadeia w de L com comprimento maior ou igual a p pode ser escrita como w = xyz (w pode ser
dividida em três subcadeias), satisfazendo as seguintes condições:
y é a subcadeia que pode ser bombeada (removida ou repetida arbitrariamente).
Vamos, agora, à descrição das condições:
Comprimento maior ou igual a 1
Para ser bombeada, y precisa ter comprimento
maior ou igual a 1.
Primeiros caracteres
Y precisa estar entre os p primeiros caracteres.
Repetição arbitrária
Podemos repetir arbitrariamente (e omitir) a
subcadeia y, e a cadeia xyz resultante
pertencerá a L.
Esse processo de repetição é conhecido como “bombeamento”. O lema do bombeamento garante ainda que o
comprimento de xy será no máximo p, o que limita as maneiras em que w pode ser dividida.
Atenção
Linguagens finitas (aquelas reconhecidas por um autômato finito) satisfazem o lema do bombeamento
por vacuidade, isto é, a maior cadeia pertencente à linguagem é menor que o p dessa linguagem. 
O lema do bombeamento é frequentemente usado para provar que certa linguagem é não regular: faz-se uma
prova por contradição obtendo uma cadeia dessa linguagem que não obedeça ao lema, ou seja, uma cadeia
de tamanho pelo menos p que, em se aplicando o bombeamento, forneça uma cadeia que não pertença à
linguagem em questão.
Podemos provar que a linguagem L = {anbn : n ≥ 0} do alfabeto Σ = {a, b} é não regular por contradição.
Exemplo
Sejam w, x, y, z, p, e i como descritos anteriormente. Seja w = apbp. Pelo lema do bombeamento, é
preciso haver uma cadeia w = xyz com |xy| ≤ p e |y| ≥ 1, tal que xyiz pertença a L para todo i ≥ 0. Pela
condição |xy|≤ p do lema do bombeamento, sabemos que y consiste apenas de instâncias de a (já que
definimos w = apbp). Fazendo o bombeamento xy2z, obtemos uma cadeia que tem mais instâncias da
letra a que da letra b, uma vez que adicionamos instâncias da letra a sem acrescentar novas instâncias
da letra b (já que y é composto inteiramente de letras a).Logo, xy2z não pertence a L, o que é uma
contradição. Portanto, a suposição de que L é regular está incorreta. Assim, provamos por contradição
que L não é uma linguagem regular! 
O lema do bombeamento não é uma condição necessária e suficiente para a regularidade de uma linguagem:
se o lema não é satisfeito em uma linguagem L, então L não é regular; mas se o lema é satisfeito para dada
linguagem L, então L pode ou não ser regular, ou seja, nada pode ser afirmado caso o lema seja satisfeito.
Uso de Autômato Finito Determinístico
Para toda linguagem regular, há um autômato finito determinístico (AFD) que aceita a linguagem. Podemos
construir vários autômatos finitos distintos equivalentes para reconhecer a mesma linguagem. Portanto,
vamos considerar o autômato finito mais simples, isto é, aquele com o menor número de estados possível.
Veja a seguir as implicações relativas ao AFD:
1
Implicações relativas ao AFD
A quantidade de estados desse AFD é usada como o p da linguagem que ele reconhece. Para uma
cadeia de comprimento igual ou maior que p, seja s0 o estado inicial e s1, ..., sp a sequência dos
próximos p estados do AFD conforme a cadeia é lida.
2
Implicações relativas ao AFD
Pelo o AFD ter apenas p estados, na sequência de p + 1 estados visitados, deverá haver, ao menos,
um estado repetido que será visitado mais de uma vez. Chamemos esse estado de S. Entre a
primeira e a segunda visita a S, o AFD seguiu uma série de transições que correspondem a uma
subcadeia,a que chamaremos de y.
3
Implicações relativas ao AFD
Uma vez que o AFD garantidamente visita S ao menos uma vez, não precisamos voltar a S
novamente. Portanto, o AFD não precisa passar pelos estados intermediários representados pela
subcadeia y. De modo semelhante, já que o AFD sempre volta a S após seguir as transições
representadas por y, podemos repetir y um número arbitrário de vezes. As condições do lema estão
satisfeitas.
Vejamos um exemplo prático para clarear o que foi exposto.
Seja o autômato que aceita a cadeia abcd. Essa cadeia tem um comprimento igual ao número de estados do
autômato (quatro), e deve haver ao menos um estado repetido no autômato. Neste exemplo, o único estado
repetido é q1, conforme demonstra a imagem a seguir:
Representação da cadeia abcd.
Uma vez que a leitura da subcadeia bc resulta em transições que iniciam e terminam em q1, essa subcadeia
pode ser repetida: o autômato aceita, por exemplo, a cadeia abcbcd. A subcadeia bc também poderia ser
removida, e a cadeia resultante ad ainda seria aceita.
Usando a notação do lema do bombeamento, a cadeia abcd é dividida entre um x (a), um y (bc) e um z (d).
Note que esse autômato aceita cadeias do tipo a(bc)*d, escritas em notação de conjuntos regulares.
Aplicação prática
Como usar a linguagem regular em um programa de computador?
Uma expressão regular é uma cadeia (string) especialmente formatada que mostra um padrão de pesquisa e
substituição de textos. O principal objetivo dessas expressões é fazer validações nos dados de um programa,
assegurando que esses dados estejam em determinado formato. Uma expressão consiste em caracteres
literais e símbolos especiais.
Na prática, utilizamos uma notação para nos ajudar a montar o padrão de uma expressão regular que será
submetido a um programa de computador para verificar se a expressão desejada está no formato correto.
Vamos ver um exemplo a seguir:
Exemplo
Seja o formato atual de CEP: 22540-050. Esse formato pode ser expresso com uma expressão geral
como esta: \\d\\d\\d\\d\\d-\\d\\d\\d. Significa que teremos cinco dígitos decimais separados de outros
três dígitos decimais por meio de um caractere “-“. O “\d” significa qualquer dígito entre 0 e 9 ([0-9]).
Neste exemplo, “\d” é a expressão regular, e a barra invertida adicional é necessária para o código
compilar. 
Eventualmente, é preciso fazer com que alguns caracteres se repitam. Por isso, os metacaracteres precisam
ter um controlador, conhecido como quantificador: um caractere que consegue informar quantas vezes um
metacaractere pode ser repetido.
Assim, nossa expressão de CEP pode ser simplificada usando quantificadores: ^\\\d{5,5}\\\-\\\d{3,3}$. Essa
expressão apresenta o metacaractere “^”, que indica o início da expressão regular. Na sequência, devemos ter
exatamente o seguinte:
Cinco dígitos antes do “-” separador. Três dígitos após o separador.
O caractere “$” indica o final da expressão regular.
Vejamos, agora, como ficaria uma expressão regular para testar a digitação correta de CPF:
1
Início com três digítos separados por um ponto
Sabemos que a expressão deverá iniciar com três dígitos separados por um ponto: ^\\d{3}\\.
2
Repetição tripla do padrão
Devemos repetir três vezes esse padrão, colocar o separador “-“ e mais dois dígitos verificadores.
3
Resultado da expressão
Assim, a expressão regular em Java para CPF será:
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
Para validar um nome, sabemos que o primeiro caractere é maiúsculo e utilizamos("[A-Z][a-zA-Z]*"). A rotina
computacional retorna verdadeiro se a primeira letra do nome for maiúscula, e falso caso contrário.
Conceitos básicos de linguagens regulares
Neste vídeo, serão descritos os conceitos básicos de linguagens regulares, incluindo o fechamento de Kleene,
os conjuntos regulares e as expressões regulares.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Uso do lema do bombeamento
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Aplicações de expressões regulares
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo
ABC-5789 é:
A
^\\[A-Z]{3,3}\\-\\d{4,4}$
B
\\[A-Z]{3,3}\\d{2,2}\\[A-Z]{2,2}\\d{4,4}
C
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,4}
D
\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,2}$
E
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{4,4}$
A alternativa C está correta.
A expressão deve iniciar com "^", ter exatamente três letras maiúsculas iniciais e mais quatro dígitos
decimais, separados por um caractere "-". A expressão deve terminar com o caractere "$". A única
alternativa que atende a todos esses requisitos é a letra C.
Questão 2
A expressão regular que permite reconhecer a digitação correta de placas de automóveis no Brasil no modelo
BSE3R52 é:
A
^\\[A-Z]{3,3}\\-\\-\d{4,4}$
B
\\[A-Z]{3,3}\\d{2,2}\\[A-Z]{2,2}\\d{4,4}
C
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,4}
D
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{2,2}$
E
^\\[A-Z]{3,3}\\d{1,1}\\[A-Z]{1,1}\\d{4,4}$
A alternativa D está correta.
A expressão deve iniciar com "^", ter exatamente três letras maiúsculas iniciais seguidas por um dígito
decimal, mais uma letra maiúscula seguida por dois dígitos decimais. A expressão deve terminar com o
caractere "$". A única alternativa que atende a todos esses requisitos é a letra D.
5. Conclusão
Considerações finais
Visitamos as funções e os conceitos de domínio, contradomínio e imagem, bem como os diagramas de Venn.
Estudamos noções básicas sobre símbolos, cadeias, alfabetos, gramáticas e linguagens. Apresentamos as
linguagens regulares e conhecemos a hierarquia de Chomsky, com destaque para a gramática tipo 3,
chamada de gramática regular.
Na sequência, vimos que um autômato finito tem um número finito de estados e pode ser de dois tipos:
autômato finito determinístico (AFD) e autômato finito não determinístico (AFN). Um AFN pode ser convertido
em um AFD equivalente. Os autômatos finitos são usados, entre outras aplicações, em projetos de
analisadores léxicos de compiladores.
Por fim, conhecemos as propriedades das linguagens regulares, incluindo o fechamento simples e o
fechamento de Kleene, conjuntos e expressões regulares. Apresentamos o importante lema do bombeamento
na determinação de quais linguagens não são regulares e demonstramos o emprego na prática com exemplos
de expressões regulares em Java.
Podcast
Ouça um complemento do conteúdo do tema através de uma entrevista para reforçar o aprendizado.
Conteúdo interativo
Acesse a versão digital para ouvir o áudio.
Explore +
Conheça a ferramenta para experimentos práticos com linguagens formais: JFLAP.
Veja um exemplo real de especificação da linguagem de programação Java no site da Oracle, no capítulo que
trata de gramática: Chapter 2. Grammars.
Veja usos práticos de programação com expressões regulares em Java nos sites da Oracle e Regular-
Expressions.info: Lesson: Regular Expressions (The Java Tutorials) e Using Regular Expressions in Java.
Referências
FEITOSA, H. A.; NASCIMENTO, M. C.; ALFONSO, A. B. Teoria dos conjuntos: sobre a fundamentação
matemática e a construção dos conjuntos numéricos. 1. ed. Rio de Janeiro: Ciência Moderna, 2021.
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, linguagens e computação. 1.
ed. São Paulo: GEN LTC, 2002.
LINZ, P. An introduction to formal languages and automata. 6. ed. Burlington: Jones & Bartlett Learning, 2016.
MENEZES, P. F. B. Linguagens formais e autômatos. 5. ed. Porto Alegre: Sagra Luzzatto, 2005.
	Linguagens regulares
	1. Itens iniciais
	Propósito
	Objetivos
	Introdução
	1. Gramáticas regulares
	Conjuntos
	Definição
	Exemplo
	{a, b, ..., z}
	{1, 3, 5, ...}
	Finito
	Infinito
	Operações sobre conjuntos
	União (U)
	Interseção
	Diferença (-)
	Produto cartesiano econcatenação
	A x B
	AB
	Relações e funções
	Conceito de relações
	Exemplo
	Reflexidade
	Simetria
	Transitividade
	Exemplo
	O que é uma função?
	Primeiro conjunto S1
	Segundo conjunto S2
	Diagramas de Venn
	Gráfico de uma função
	Noções básicas sobre linguagens
	Principais conceitos
	Símbolo
	Alfabeto
	Cadeia
	Prefixo de uma cadeia
	Prefixo próprio para uma cadeia
	Sufixo de uma cadeia
	Sufixo próprio para uma cadeia
	Subcadeia de uma cadeia
	Linguagem formal e gramática
	Lado Esquerdo (LE)
	Lado Direito (LD)
	Gramáticas lineares e classes de linguagens
	Hierarquia de Chomsky
	Gramática linear à direita
	Gramática linear à esquerda
	Definições recursivas
	Operações sobre ER
	União
	Concatenação
	Fechamento
	Fechamento de Kleene
	Conceitos sobre teoria dos conjuntos e grafos
	Conteúdo interativo
	Vem que eu te explico!
	A gramática
	Conteúdo interativo
	Hierarquia de Chomsky
	Conteúdo interativo
	Verificando o aprendizado
	2. Autômatos finitos
	Conceitos básicos
	Teoria dos autômatos
	Corretores ortográficos
	Dicionários multilíngues
	Compactação de texto
	Projeto do compilador
	Princípio de funcionamento do software
	Software para Processamento de Linguagem Natural (PLN)
	Autômatos úteis na projeção do software
	Características de um autômato
	Armazenamento de informações sobre o passado
	Descrição de nó de comportamento do sistema
	Transição indicadora de mudança de estado
	Planos paralelos ou ortogonais aos planos e eixos cartesianos
	Exemplo 1
	Solução
	Exemplo 2
	Solução
	Eixo z
	Eixo y
	Eixo x
	Eixo z
	Eixo y
	Eixo x
	Funcionamento
	Sistema transicional
	Aceitação de uma cadeia por AF
	Resumindo
	Atendidas
	Não atendida ou não atendidas
	Um caractere lido por vez
	A entrada para o estado recém-alcançado
	A cadeia não aceita
	Com a entrada “0”
	Com a entrada “1”
	Ao ler o caractere “0”
	Ao ler o “1”
	Ao ler o último “1”
	AF reconhece a cadeia nula
	AF reconhece cadeias com qualquer número de “0”
	AF muda para o estado q1 ao ler uma entrada “1”
	Exemplos práticos
	Exemplo 1
	Com a entrada “0”
	Com a entrada “1”
	Ao ler o caractere “0”
	Ao ler o “1”
	Ao ler o último “1”
	AF reconhece a cadeia nula
	AF reconhece cadeias com qualquer número de “0”
	AF muda para o estado q1 ao ler uma entrada “1”
	Exemplo 2
	Cadeia vazia (λ), pois o estado inicial é igual ao final.
	Cadeias do tipo “00” ou “11”.
	Cadeias como 0101 ou 1010.
	Cadeias que são compostas por um número par de zeros e uns.
	Tipos
	Autômatos Finitos com saída
	Leitura do primeiro zero
	Leitura de “1”
	Leitura do próximo “1”
	Leitura do “0”
	Autômatos finitos de duas vias ou bidirecionais
	Representação de Autômato Finito
	Conteúdo interativo
	Vem que eu te explico!
	Conceitos básicos: uso de autômatos
	Conteúdo interativo
	Autômatos finitos com saída
	Conteúdo interativo
	Verificando o aprendizado
	Questão 1
	Questão 2
	3. Autômatos Finitos Não Determinísticos
	Características e representação
	AFN e AFD
	Como representar um AFN?
	Q
	I
	F
	Três caminhos
	Estado final q2
	Cadeia 00101 aceita pela AFN
	Caminho seguido pelo AFN
	Conversão
	Como converter AFN em AFD?
	Estado inicial do AFN
	Próximos estados para o estado inicial
	Combinação de estado na coluna de estado atual
	A combinação de cada um dos estados seguintes
	Nenhuma nova combinação de estado
	Estado inicial do AFN
	A combinação de estados que contém um estado final
	Conversão de um AFN em AFD
	Conteúdo interativo
	Vem que eu te explico!
	Características e representação de AFN
	Conteúdo interativo
	Representação
	Conteúdo interativo
	Verificando o aprendizado
	4. Fundamentos de linguagens regulares
	Principais definições
	Expressões Regulares
	Relembrando
	Fechamento simples e fechamento de Kleene
	Conjuntos regulares
	{λ}
	Exemplo
	Recursividade
	λ
	(x)
	x|y ou x + y
	x.y ou xy
	Propriedades
	Lema do bombeamento
	Comprimento maior ou igual a 1
	Primeiros caracteres
	Repetição arbitrária
	Atenção
	Exemplo
	Uso de Autômato Finito Determinístico
	Implicações relativas ao AFD
	Implicações relativas ao AFD
	Implicações relativas ao AFD
	Aplicação prática
	Como usar a linguagem regular em um programa de computador?
	Exemplo
	Cinco dígitos antes do “-” separador.
	Três dígitos após o separador.
	Início com três digítos separados por um ponto
	Repetição tripla do padrão
	Resultado da expressão
	Conceitos básicos de linguagens regulares
	Conteúdo interativo
	Vem que eu te explico!
	Uso do lema do bombeamento
	Conteúdo interativo
	Aplicações de expressões regulares
	Conteúdo interativo
	Verificando o aprendizado
	5. Conclusão
	Considerações finais
	Podcast
	Conteúdo interativo
	Explore +
	Referências