Autômatos - Conceitos Básicos

Prévia do material em texto

Prof. Willian Magalhães
wmagalhaes@unipar.br
Autômatos 
Conceitos Básicos
UNIPAR – Universidade Paranaense
Curso de Sistemas de Informação
Autômatos?
 A teoria dos autômatos é um estudo dos dispositivos de 
computação abstratos [HOPCROFT]
 Em 1930 (antes de existirem computadores) Alan Turing 
realizou um estudo sobre uma maquina abstrata que 
possuía algumas características dos computadores atuais
 Seu objetivo era descrever o limite entre o que uma 
máquina de computação podia ou não fazer
Prof. Willian Magalhães 2
Definição
 Um autómato pode ser considerado um modelo 
matemático de um sistema cujo comportamento pode ser 
descrito como uma sequência simples
Prof. Willian Magalhães 3
Motivações
 Como expressar formalmente uma linguagem 
computacional?
 Enfoque teórico no problema da sintaxe
• Sintaxe vs. Semântica
• Auxílio na evolução dos algoritmos de compilação
 Desenho de hardware
 Reconhecimento de padrões
Prof. Willian Magalhães 4
Aplicações práticas
 Os autómatos estão presentes nas mais variadas situações 
do dia-a-dia
• Em casa: lâmpadas
• Nos prédios: elevadores
• Na rua: semáforos
• Nos computadores: processadores
• Na computação: definição de limites computacionais
Prof. Willian Magalhães 5
Conceitos básicos
 Antes de criarmos nossos próprios autômatos é necessário 
compreendermos alguns conceitos elementares
Prof. Willian Magalhães 6
Alfabetos
 Conjunto de símbolos finito e não-vazio
 Convencionalmente utilizamos o símbolo Σ (sigma)
 Exemplos:
• Σ = {𝑎, 𝑏, 𝑐, … , 𝑧}
• Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• Σ = 0, 1
• Σ = 00, 11 , 01
Prof. Willian Magalhães 7
Símbolos
 Todo elemento que pertence à um alfabeto
 Também conhecido como letra
 Exemplo:
• Σ = {0, 1, 23}
• 0 é símbolo de Σ
• 1 é símbolo de Σ
• 23 é símbolo de Σ
Prof. Willian Magalhães 8
Cadeias
 Sequencia finita de símbolos escolhidos de um alfabeto
 Também conhecido como palavra ou string
 Exemplos:
• Σ = 0, 1
• 𝑥 = 01001
Prof. Willian Magalhães 9
• Σ = 𝑎, 𝑏, 𝑐𝑑
• 𝑦 = 𝑎𝑐𝑑𝑏
• 𝑧 = 𝑎
Cadeia vazia
 Uma cadeia que não possui ocorrência de símbolos é 
considerada um cadeia vazia
 Essa cadeia é denotada por 𝜀 (épsilon) ou λ (lambda)
 É uma cadeia que pode ser escolhida em qualquer alfabeto
Prof. Willian Magalhães 10
Comprimento de uma cadeia
 Número de símbolos que compõem uma dada cadeia
 O comprimento da cadeia 𝑥 é denotado por |𝑥| (módulo)
 Exemplo
• Σ = 0, 1
• 0110 = 4
• 𝜆 = 0 (cadeia nula)
Prof. Willian Magalhães 11
Exemplo
 Dado o alfabeto Σ = {a, b, c, de} verifique se as cadeias a
seguir são formadas sobre este alfabeto, e se for, verifique
qual o comprimento das mesmas:
• 𝑎 = 𝑎𝑏𝑎𝑏𝑎𝑐
• 𝑏 = 𝑎𝑏𝑑𝑒𝑐
• 𝑐 = 𝑎𝑏𝑒𝑑𝑐
• 𝑑 = 𝑎𝑏𝑑𝑐𝑒𝑎𝑏𝑎
• 𝑒 = 𝑑
• 𝑓 = 𝑎
Prof. Willian Magalhães 12
Potências de um alfabeto
 Também conhecida como exponenciação de alfabetos
 Onde Σ𝑘 é o conjunto de todas as cadeias com tamanho 𝑘,
formadas sobre o alfabeto Σ
 Exemplo
• Σ = 0, 1
• Σ0 = {λ}
• Σ1 = 0, 1 = Σ
• Σ2 = {00, 01, 10, 11}
Prof. Willian Magalhães 13
Exemplo
 Dado o alfabeto Σ = {0, 1} encontre Σ3
Prof. Willian Magalhães 14
Fechamento de um alfabeto
 Seja Σ um alfabeto qualquer, então o fechamento de Σ,
descrito por Σ∗ é definido como:
 Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪⋯ ∪ Σn
 Σ∗ é o conjunto de todas as cadeias possíveis de se formar
sobre o alfabeto Σ
 Fechamento positivo: Σ+ = Σ∗ − {λ}
Prof. Willian Magalhães 15
Prefixo, Sufixo, Subcadeia
 Prefixo
• Qualquer sequencia inicial de símbolos de uma cadeia
 Sufixo
• Qualquer sequencia final de símbolos de uma cadeia
 Subcadeia
• é qualquer sequencia que compõe a cadeia
Prof. Willian Magalhães 16
Prefixo, Sufixo, Subcadeia
 Considerando a cadeia 𝑎𝑏𝑏𝑎𝑐
 São prefixos
• 𝜆, 𝑎, 𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑏𝑏𝑎, 𝑎𝑏𝑏𝑎𝑐
 São sufixos
• λ, 𝑐, 𝑎𝑐, 𝑏𝑎𝑐, 𝑏𝑏𝑎𝑐, 𝑎𝑏𝑏𝑎𝑐
 São subcadeias
• 𝜆, 𝑎, 𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑏𝑏𝑎, 𝑎𝑏𝑏𝑎𝑐, b, bb, bba, bbac, ba, bac, ac
Prof. Willian Magalhães 17
Concatenação de cadeias
 Sejam 𝑥 e 𝑦 duas cadeias
 𝑥𝑦 denota a concatenação de x e 𝑦
 Exemplo
• Σ = 𝑎, 𝑏, 𝑐, … , 𝑧
• 𝑥 = 𝑎𝑏𝑟𝑎 e 𝑦 = 𝑐𝑎𝑑𝑎𝑏𝑟𝑎
• 𝑥𝑦 = 𝑎𝑏𝑟𝑎𝑐𝑎𝑑𝑎𝑏𝑟𝑎
• 𝑦𝑥 = 𝑐𝑎𝑑𝑎𝑏𝑟𝑎𝑎𝑏𝑟𝑎
Prof. Willian Magalhães 18
Concatenação de cadeias
 Exemplo
• Σ = 𝑎, 𝑏
• 𝑥 = 𝑎𝑏𝑎𝑎, 𝑦 = 𝑏𝑎, 𝑧 = 𝜆
• 𝑥𝑦 = 𝑎𝑏𝑎𝑎𝑏𝑎
• 𝑦𝑥 = 𝑏𝑎𝑎𝑏𝑎𝑎
• 𝑦𝑧 = 𝑏𝑎
• 𝑧𝑥𝑧 = 𝑎𝑏𝑎𝑎
 A cadeia nula (𝜆) é o elemento neutro da concatenação
Prof. Willian Magalhães 19
Concatenação sucessiva
 Concatenação de uma palavra com ela mesma
 Representada por um expoente: 𝑤𝑛
 Exemplo
• Σ = 𝑎, 𝑏
• 𝑥 = 𝑎𝑏
• 𝑥3 = 𝑎𝑏𝑎𝑏𝑎𝑏
Prof. Willian Magalhães 20
Bibliografia
 MENEZES, Paulo Blauth. Linguagens Formais e Autômatos.
Porto Alegre: Editora Sagra-Luzzatto, 1998;
 DIVERIO, Tiaraju Asmuz. Teoria da computação: maquinas
universais e computabilidade. Porto Alegre: Sagra Luzzatto,
2000;
 HOPCROFT, John. Introdução a teoria de autômatos,
linguagens e computação, trad. Vandenberg D. de Souza.
Rio de Janeiro: Elsevier, 2003.
Prof. Willian Magalhães 21