03_automatos_finitos (1)

Prévia do material em texto

Autômatos Finitos
Prof. Andrei Braga
Conteúdo
● Alfabetos, Strings e Linguagens
● Autômatos Finitos
● Exercícios
● Referências
2
Conceitos básicos
● A seguir, vamos definir os conceitos básicos necessários para iniciarmos o 
nosso estudo de Autômatos
● Entre estes conceitos, estão alfabeto, string e linguagem
3
Alfabeto e símbolo
● Um alfabeto é um conjunto finito não-vazio
● Os elementos de um alfabeto são chamados de símbolos
● As letras gregas Σ e Γ são comumente usadas para denotar um alfabeto
● Exemplos:
○ Σ = { 0, 1 }
○ Σ = { a, b, ... , z }
○ Γ = { 0, 1, x, y, z }
(alfabeto binário)
4
Strings
● Uma string é uma sequência finita de símbolos escolhidos a partir de um 
alfabeto
● Exemplos:
○ 01001 é uma string do (ou sobre) o alfabeto Σ = { 0, 1 }
○ abracadabra é uma string do (ou sobre) o alfabeto Σ = { a, b, ... , z }
○ Considere que Σ é o conjunto de todos os caracteres válidos em um programa 
escrito na linguagem C –
○ Σ = { 0, 1, …, 9, a, b, ... , z, A, B, ..., Z, {, }, (, ), [, ], , =, !, +, -, *, /, %, _, &, \, … }
■ Um programa em C é uma string do (ou sobre) o alfabeto Σ
5
Strings
● O comprimento (ou tamanho) de uma string é o número de símbolos (mais 
precisamente, o número de posições para símbolos) contidos na string
○ O comprimento de 01001 é 5
● Denotamos o comprimento de uma string w por |w|
● Exemplo:
○ |01001| = 5
● A string de comprimento zero é chamada de string vazia e é denotada por ε 
(em alguns livros, a string vazia também é denotada por ϵ ou λ)
○ |ε| = 0
○ A string vazia é uma string de (ou sobre) qualquer alfabeto
6
Strings
● A concatenação de duas strings x e y é a string obtida concatenando-se y ao 
fim de x
○ Se x = x1x2...xn e y = y1y2...ym, então a concatenação de x e y é x1x2...xny1y2...ym
● A concatenação de x e y é denotada por xy
● Exemplos:
○ x = 01101 e y = 110, xy =
○ x = 01, xx =
○ εx =
7
Strings
● A concatenação de duas strings x e y é a string obtida concatenando-se y ao 
fim de x
○ Se x = x1x2...xn e y = y1y2...ym, então a concatenação de x e y é x1x2...xny1y2...ym
● A concatenação de x e y é denotada por xy
● Exemplos:
○ x = 01101 e y = 110, xy = 01101110
○ x = 01, xx = 0101
○ εx = xε = x
8
● Em relação à concatenação de duas strings x e y, podemos notar o seguinte:
○ |xy| = |x| + |y|
○ Em geral, xy ≠ yx
Strings
● Seja a um símbolo
● Vamos denotar por ak uma string que consiste em k símbolos a
● Exemplos:
○ 05 = 00000
○ 1n = 111…1 ➡ String que consiste em n 1’s
● Seja w uma string
● Vamos denotar por wk a concatenação de k cópias de w
● Exemplos:
○ w = 01, w3 =
○ w = 110, wn =
9
Strings
● Seja a um símbolo
● Vamos denotar por ak uma string que consiste em k símbolos a
● Exemplos:
○ 05 = 00000
○ 1n = 111…1 ➡ String que consiste em n 1’s
● Seja w uma string
● Vamos denotar por wk a concatenação de k cópias de w
● Exemplos:
○ w = 01, w3 = 010101
○ w = 110, wn = 110110…110 ➡ Concatenação de n cópias de 110
10
● Para qualquer string w, temos que w0 = ε
Exercícios
● Exercício 1 da Lista de Exercícios “Autômatos Finitos”.
11
Exercícios
● Exercício 2 da Lista de Exercícios “Autômatos Finitos”.
12
Reversa de uma string
● A reversa de uma string w, denotada por wR, é a string w escrita de trás para 
frente
● Exemplos:
○ w = 1110, wR =
○ w = baab, wR =
13
● A reversa de uma string w, denotada por wR, é a string w escrita de trás para 
frente
● Exemplos:
○ w = 1110, wR = 0111
○ w = baab, wR = baab
Reversa de uma string
14
● A definição acima é suficientemente precisa para os nossos propósitos
● No entanto, poderíamos ser mais formais ao tratar o conceito de reversa de 
uma string
○ Isto poderia ser feito utilizando uma definição recursiva (o que não faremos agora)
Exercícios
● Exercício 3 da Lista de Exercícios “Autômatos Finitos”.
15
Exercícios
● Exercício 4 da Lista de Exercícios “Autômatos Finitos”.
16
Potências de um alfabeto
● Σk é o conjunto das strings de comprimento k do alfabeto Σ
● Exemplos para Σ = { 0, 1 }:
○ Σ1 = 
○ Σ2 = 
○ Σ3 = 
○ Σ0 = 
17
Potências de um alfabeto
● Σk é o conjunto das strings de comprimento k do alfabeto Σ
● Exemplos para Σ = { 0, 1 }:
○ Σ1 = { 0, 1 }
○ Σ2 = { 00, 01, 10, 11 }
○ Σ3 = { 000, 001, 010, 011, 100, 101, 110, 111 }
○ Σ0 = { ε }
18
Note que, para todo 
alfabeto Σ, ε ∊ Σ*
● Σ* é o conjunto de todas as strings de um alfabeto Σ
○ Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪ ...
○ Se Σ = { 0, 1 }, então Σ* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, … }
○ Também podemos escrever
{ 0, 1 }* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, … }
Exercícios
● Exercício 5 da Lista de Exercícios “Autômatos Finitos”.
19
Linguagens
● Uma linguagem L é um conjunto de strings escolhidas a partir de Σ* para um 
dado alfabeto Σ
○ L ⊆ Σ*
○ L é uma linguagem de (ou sobre) Σ
● Exemplos:
○ A linguagem L = { 1010, 11111, 0000001 }
○ L é uma linguagem do (ou sobre o) alfabeto { 0, 1 }
○ A linguagem L de todas as strings consistindo em n 0’s seguidos de n 1’s
para n ≥ 0:
○ L = { ε, 01, 0011, 000111, ... }
○ L é uma linguagem do (ou sobre o) alfabeto { 0, 1 }
20
Linguagens
● Uma linguagem L é um conjunto de strings escolhidas a partir de Σ* para um 
dado alfabeto Σ
○ L ⊆ Σ*
○ L é uma linguagem de (ou sobre) Σ
● Exemplos:
21
○ A linguagem L de todas as strings de 0’s e 1’s com o mesmo número de 0’s e 1’s:
○ L = { ε, 01, 10, 0011, 0101, 1001, ... }
○ L é uma linguagem do (ou sobre o) alfabeto { 0, 1 }
○ A linguagem L consistindo em todos os nomes de variáveis em Python
○ L = { idade, num_linhas, cont1, cont2, ... }
○ L é uma linguagem do (ou sobre o) alfabeto { a, b, …, z, A, B, ... , Z, 0, 1, …, 9, _ }
● A concatenação de duas linguagens L1 e L2, denotada por L1L2, é o conjunto 
das strings que podem ser formadas pela concatenação de uma string de L1 
com uma string de L2
● Exemplos:
○ L1 = { 00, 0 } e L2 = { 1, 111 },
○ L1L2 =
○ L1 = { a, aa, aaa, … } e L2 = { ε, b, bb, bbb, … },
○ L1L2 =
Linguagens
22
● A concatenação de duas linguagens L1 e L2, denotada por L1L2, é o conjunto 
das strings que podem ser formadas pela concatenação de uma string de L1 
com uma string de L2
● Exemplos:
○ L1 = { 00, 0 } e L2 = { 1, 111 },
○ L1L2 = { 001, 00111, 01, 0111 }
○ L1 = { a, aa, aaa, … } e L2 = { ε, b, bb, bbb, … },
○ L1L2 = { a, ab, abb, abbb, ... , aa, aab, aabb, aabbb, ... , aaa, ... }
● Em geral, L1L2 ≠ L2L1
Linguagens
23
● Dada uma linguagem L, vamos denotar por Lk o conjunto das strings que 
podem ser formadas pela concatenação de k strings de L
● Exemplos para L = { 00, 1 }:
○ L1 =
○ L2 =
○ L3 =
○ L0 =
Linguagens
24
● Dada uma linguagem L, vamos denotar por Lk o conjunto das strings que 
podem ser formadas pela concatenação de k strings de L
● Exemplos para L = { 00, 1 }:
○ L1 = { 00, 1 }
○ L2 = { 0000, 001, 100, 11 }
○ L3 = { 000000, 00001, 00100, 0011, 10000, 1001, 1100, 111 }
○ L0 = { ε }
● Para qualquer linguagem L, temos que L0 = { ε }
Linguagens
25
● O fechamento de uma linguagem L, denotado por L*, é o conjunto das strings 
que podem ser formadas pela concatenação de uma quantidade qualquer de 
strings de L
○ L* = L0 ∪ L1 ∪ L2 ∪ ...
● Exemplos:
○ L = { 00, 1 },
○ 00 L*, 001111 L*, 100100100 L*, ε L*
○ L = { 0, 11 },
○ 011 L*, 11110 L*, 101 L*, 01011 L*
Linguagens
26
● O fechamento de uma linguagem L, denotado por L*, é o conjunto das strings 
que podem ser formadas pela concatenação de uma quantidade qualquer de 
strings de L
○ L* = L0 ∪ L1 ∪ L2 ∪ ...
● Exemplos:
○ L = { 00, 1 },
○ 00 ∈ L*, 001111 ∈ L*, 100100100 ∈ L*, ε ∈ L*
○ L = { 0, 11 },
○ 011 ∈ L*, 11110 ∈ L*, 101 ∉ L*, 01011 ∉ L*
Linguagens
27
Note que, para toda 
linguagem L, ε ∊ L*
Exercícios
● Exercício 6 da Lista de Exercícios “Autômatos Finitos”.
28
Exercícios
● Exercício 7 da Lista de Exercícios “Autômatos Finitos”.
29
Exercícios
● Exercício 8 da Lista de Exercícios “Autômatos Finitos”.
30
Autômatos finitos
● Dissemos antes que autômatos finitos são modelos adequados para 
representardispositivos computacionais que têm uma pequena quantidade de 
memória
○ Estamos nos referindo a dispositivos que servem apenas a propósitos específicos 
(diferente de um computador de propósito geral)
● Dispositivos computacionais como estes são úteis?
● Sim! Estes dispositivos estão presentes em vários equipamentos 
eletromecânicos do nosso dia a dia!
● Exemplo: controlador de porta automática
31
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
○ Vamos considerar uma porta automática de modelo mais antigo, que permite a 
passagem de pessoas por um único sentido
Frente Fundo
Porta automática Abre para trás
■ Há algum tempo, poderíamos encontrar em um shopping
● uma porta deste tipo para a entrada de pessoas e
● outra porta deste tipo para a saída de pessoas
32
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
○ Vamos considerar uma porta automática de modelo mais antigo, que permite a 
passagem de pessoas por um único sentido
Frente Fundo
Porta automática Abre para trás
○ A porta tem um sensor apontado para a frente para detectar uma pessoa se 
aproximando
○ A porta também tem um sensor apontado para os fundos para garantir que a pessoa já 
tenha passado completamente pela área da porta e para evitar atingir uma pessoa 
localizada na parte de trás
33
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
○ Como funciona um controlador deste tipo?
Frente Fundo
Porta automática
○ O controlador pode estar em dois estados: ABERTO ou FECHADO
○ O controlador pode receber como entrada FRENTE, FUNDO, AMBOS, ou NENHUM
○ O controlador muda de um estado para outro dependendo da entrada recebida
Abre para trás
34
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
○ Como funciona um controlador deste tipo?
○ O controlador pode estar em dois estados: ABERTO ou FECHADO
○ O controlador pode receber como entrada FRENTE, FUNDO, AMBOS, ou NENHUM
○ O controlador muda de um estado para outro dependendo da entrada recebida
FRENTE FUNDO AMBOS NENHUM
FECHADO
ABERTO
ABERTO
ABERTO ABERTO ABERTO
FECHADO FECHADO FECHADO
FECHADO
○ A seguir, vamos representar as informações da tabela acima através de um diagrama
Início
35
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
FECHADO ABERTO
FRENTE
NENHUM
FUNDO, AMBOS, NENHUM FRENTE, FUNDO, AMBOS
FRENTE FUNDO AMBOS NENHUM
FECHADO
ABERTO
ABERTO
ABERTO ABERTO ABERTO
FECHADO FECHADO FECHADO
FECHADO
Início
Início
36
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
FECHADO ABERTO
FRENTE
NENHUM
FUNDO, AMBOS, NENHUM FRENTE, FUNDO, AMBOS
Início
○ No diagrama abaixo, temos o seguinte:
■ os possíveis estados do controlador são representados por círculos
■ o estado inicial do controlador é indicado por um arco (uma seta) acompanhada da 
palavra “Início”
37
Autômatos finitos – Exemplo 1
● Exemplo: controlador de porta automática
○ No diagrama abaixo, temos o seguinte:
FECHADO ABERTO
FRENTE
NENHUM
FUNDO, AMBOS, NENHUM FRENTE, FUNDO, AMBOS
Início
■ uma transição de um primeiro estado para um segundo estado que ocorre quando 
uma determinada entrada é recebida é indicada por um arco (uma seta) que vai do 
primeiro estado para o segundo estado e tem a entrada como rótulo
■ um arco que contém mais de um rótulo representa que a transição indicada ocorre 
para cada um destes rótulos
38
Autômatos finitos – Exemplo 1
● Um diagrama como o abaixo é chamado de diagrama de estados finitos (ou 
diagrama de estados), máquina de estados finitos ou autômato finito
● Através de um diagrama deste tipo, podemos representar o funcionamento de 
uma máquina física
● No entanto, fazemos isto não detalhando o hardware envolvido, mas apenas 
indicando os estados internos do funcionamento da máquina
FECHADO ABERTO
FRENTE
NENHUM
FUNDO, AMBOS, NENHUM FRENTE, FUNDO, AMBOS
Início
39
Autômatos finitos – Exemplo 1
● Uma máquina abstrata como a do diagrama abaixo não utiliza 
explicitamente uma memória para armazenar dados sobre os 
processamentos feitos
● Em vez disso, a máquina consegue lembrar (ou armazenar dados sobre) os 
processamentos feitos apenas através dos seus estados
● Esta capacidade de lembrar ficará mais clara no próximo exemplo
FECHADO ABERTO
FRENTE
NENHUM
FUNDO, AMBOS, NENHUM FRENTE, FUNDO, AMBOS
Início
40
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Para simplificar o exemplo, vamos considerar uma máquina que
■ vende chocolates de apenas um tipo e que custam 1 real
■ aceita como pagamento apenas moedas de 25 centavos, 50 centavos e 1 real e
■ não dá troco 😁
41
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
○ O controlador recebe como entrada moedas de 25 centavos, 50 centavos e 1 real
■ Vamos usar v, c e r, respectivamente, para representar estas moedas
○ O controlador deve contabilizar o valor total recebido e, se este valor for igual ou maior a 
1 real, deve fazer cair um chocolate
42
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
○ O controlador pode estar em cinco estados:
■ 0c: o valor total recebido é maior ou igual a 0 centavos
■ 25c: o valor total recebido é maior ou igual a 25 centavos
■ 50c: o valor total recebido é maior ou igual a 50 centavos
■ 75c: o valor total recebido é maior ou igual a 75 centavos
■ 1r: o valor total recebido é maior ou igual a 1 real
○ O controlador muda de um estado para outro dependendo
da entrada recebida
43
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
0c 25cv 50cv 75cv 1rv, c, r
c
r
c
r
c, r v, c, r
Início
○ Podemos representar o funcionamento do controlador através do diagrama abaixo:
44
Autômatos finitos – Exemplo 2
● No exemplo anterior, consideramos o funcionamento de um controlador sem 
um início ou um fim definidos
● No exemplo atual, vamos considerar o funcionamento do controlador para 
cada uso da máquina de venda de chocolates
○ Um uso da máquina de venda de chocolates corresponde a uma situação 
onde um usuário fornece uma sequência de moedas para a máquina com a 
intenção de obter um chocolate
● É este tipo de funcionamento que vamos considerar
daqui em adiante para um autômato
45
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
○ A cada uso da máquina de venda de chocolates, sabemos que o controlador deve 
contabilizar o valor total recebido e, se este valor for igual ou maior a 1 real,
deve fazer cair um chocolate
○ Sendo assim, podemos redefinir a entrada do controlador da seguinte forma:
■ O controlador recebe como entrada uma sequência de moedas de 25 centavos,
50 centavos e 1 real
■ Isto é equivalente a dizer que
■ O diagrama anterior recebe como entrada
uma sequência de símbolos v, c e r – ou seja,
■ uma string do alfabeto { v, c e r }
46
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
○ A cada uso da máquina de venda de chocolates, sabemos que o controlador deve 
contabilizar o valor total recebido e, quando este valor for igual ou maior a 1 real,
deve fazer cair um chocolate
○ Além disso, podemos definir a saída do controlador da seguinte forma:
■ Se o valor total recebido for igual ou maior a 1 real, o controlador deve fazer cair um 
chocolate; senão o controlador não deve fazer nada
■ No diagrama anterior, vamos considerar o seguinte:
■ Se a string recebida representar um valor total igual ou
maior a 1 real, o diagrama anterior deve aceitar a string;
senão o diagrama anterior deve rejeitar a string
47
Autômatos finitos – Exemplo2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Em um diagrama de estados finitos, vamos usar estados finais (ou de aceitação) para 
definir se a string de entrada vai ser aceita ou rejeitada:
■ Se o processamento da string de entrada fizer com que o último estado atingido 
seja um estado final (ou de aceitação), então a string de entrada será aceita
■ Caso contrário, a string de entrada será rejeitada
○ Em um diagrama de estados finitos, um estado final será representado por um círculo 
duplo
48
Autômatos finitos – Exemplo 2
● Exemplo: controlador de máquina de venda automática de chocolates
○ Como funciona um controlador deste tipo?
○ Podemos representar o funcionamento do controlador através do diagrama abaixo:
0c 25cv 50cv 75cv v, c, r
c
r
c
r
c, r v, c, r
Início 1r
Estado final (ou 
de aceitação)
49
Exercícios
● Exercício 9 da Lista de Exercícios “Autômatos Finitos”.
50
Autômatos finitos – Exemplos
● Outros exemplos de dispositivos computacionais com memória muito limitada: 
controladores de elevadores, lavadoras de louça e termostatos e controladores 
que são componentes de relógios e calculadoras
● Entender as propriedades dos autômatos finitos é útil para o desenvolvimento 
de dispositivos como estes
● Autômatos finitos também são úteis para o reconhecimento de padrões em 
dados (por exemplo, para aplicações na área de processamento de fala)
51
Autômatos finitos – Definição formal
● Um autômato finito é uma 5-upla (Q, Σ, 𝛿, q0, F), onde
○ Q é um conjunto finito chamado de conjunto de estados do autômato,
○ Σ é um alfabeto chamado de alfabeto de entrada do autômato,
○ 𝛿: Q ⨯ Σ → Q é uma função chamada de função de transição do autômato,
○ q0 ∊ Q é o estado inicial do autômato e
○ F ⊆ Q é o conjunto de estados finais (ou de aceitação) do autômato
● O conjunto F pode ser vazio, ou seja, o autômato pode não ter nenhum 
estado final (ou de aceitação)
52
Autômatos finitos – Definição formal
● Um autômato finito é uma máquina abstrata que funciona da seguinte maneira:
○ O autômato recebe como entrada uma string do alfabeto de entrada Σ
○ O autômato começa no estado inicial q0
○ O autômato lê os símbolos da string de entrada um por vez da esquerda para a direita
○ Depois de ler um símbolo da entrada, o autômato segue o que é determinado pela 
função de transição 𝛿 e vai para um novo estado (que pode ser igual ao anterior)
○ O autômato termina o seu processamento quando tiver lido toda a string de entrada
○ Os possíveis resultados do processamento do autômato (as possíveis saídas) são os 
seguintes:
■ O autômato aceita a string de entrada caso termine em um estado final (ou de 
aceitação)
■ O autômato rejeita a string de entrada caso contrário
53
Autômatos finitos – Definição formal
● Função de transição 𝛿: Q ⨯ Σ → Q
● 𝛿(q1, a) = q2 determina que
○ se o autômato
■ se encontra no estado q1 e
■ lê o símbolo de entrada a,
○ então o autômato
■ vai para o estado q2
● Como 𝛿 é uma função, para cada estado qi e cada símbolo de entrada a, 
existe exatamente uma transição para o par qi, a
54
Autômatos finitos – Definição formal
● Nos slides anteriores, descrevemos o que significa um autômato finito aceitar 
uma string de entrada
● Vamos aproveitar para apresentar uma definição formal para este conceito
● Seja M = (Q, Σ, 𝛿, q0, F) um autômato finito e w = w1w2...wn uma string do 
alfabeto Σ
● Dizemos o seguinte:
○ M aceita w se existe uma sequência de estados r0, r1, …, rn de Q tal que
■ r0 = q0,
■ 𝛿(ri, wi+1) = ri+1, para i = 0, 1, …, n - 1 e
■ rn ∈ F
○ M rejeita w caso contrário
55
Exercícios
● Exercício 10 da Lista de Exercícios “Autômatos Finitos”.
56
Autômatos finitos - Representação gráfica
● Um autômato finito M = (Q, Σ, 𝛿, q0, F) pode ser representado graficamente 
por um diagrama de estados onde ocorre o seguinte:
○ Cada estado em Q é representado por um círculo
○ Para cada estado q ∊ Q e cada símbolo a ∊ Σ, seja 𝛿(q, a) = r. Existe um arco (uma 
seta) saindo do círculo correspondente a q para o círculo correspondente a r com o 
rótulo a. Se a transição de q para r acontece para mais de um símbolo de entrada, 
estes símbolos podem ser combinados no mesmo arco
○ Existe um arco chegando no estado inicial q0 que não sai de nenhum outro estado. 
Este arco pode estar acompanhado da palavra “Início”
○ Estados finais (ou de aceitação) são representados por círculos duplos; os demais 
estados são representados por círculos simples
57
Exercícios
● Exercício 11 da Lista de Exercícios “Autômatos Finitos”.
58
● Um autômato finito M = (Q, Σ, 𝛿, q0, F) pode ser representado por um tabela 
onde ocorre o seguinte:
○ Cada estado em Q é representado por uma linha da tabela
○ Cada símbolo a ∊ Σ é representado por uma coluna da tabela
○ Para cada estado q ∊ Q e cada símbolo a ∊ Σ, seja 𝛿(q, a) = r. A entrada
(q, a) da tabela contém r
○ Existe uma seta identificando a linha da tabela correspondente ao estado 
inicial q0
○ As linhas da tabela correspondentes aos estados finais (ou de aceitação) são 
identificadas com *
Autômatos finitos - Representação tabular
59
● Exemplo:
○ O autômato finito M = (Q, Σ, 𝛿, q0, F) tal que
Q = { q0, q1 }, Σ = { 0, 1 }, F = { q1 } e 𝛿(q0, 0) = q0, 𝛿(q0, 1) = q1, 𝛿(q1, 0) = q0, 𝛿
(q1, 1) = q1
pode ser representado pela seguinte tabela:
Autômatos finitos - Representação tabular
60
0 1
q0 q0 q1
q1 q0 q1*
Linguagem de um autômato e linguagem regular
● Podemos descrever um autômato como uma máquina que aceita uma 
determinada linguagem. Para isso, fazemos a seguinte definição:
● A linguagem que consiste em todas as strings aceitas por um autômato finito 
M é chamada a linguagem aceita por M ou a linguagem de M - denotamos 
esta linguagem por L(M)
● De posse da definição acima, podemos introduzir uma importante classe de 
linguagens:
● Uma linguagem L é regular se existe um autômato finito M tal que L(M) = L
61
Exercícios
● Demais exercícios da Lista de Exercícios “Autômatos Finitos”.
62
Referências
● Esta apresentação é baseada nos seguintes materiais:
1. Capítulo 1 do livro
Sipser, M., Introduction to the Theory of Computation, 3rd edition, 
Cengage Learning, 2012.
2. Capítulos 2 e 3 do livro
SILVA, M. V. G. Autômatos, Computabilidade e Complexidade 
Computacional. 2023.
3. Capítulos 1 e 2 do livro
Hopcroft, J., Motwani, R., Ullman, J., Introduction to automata theory, 
languages, and computation, 3rd edition, Pearson, 2006.
63