Autômatos - Linguagens

Prévia do material em texto

Prof. Willian Magalhães
wmagalhaes@unipar.br
Autômatos 
Linguagens
UNIPAR – Universidade Paranaense
Curso de Sistemas de Informação
Aula anterior
 Alfabeto
 Símbolo
 Cadeias
 Comprimento de cadeias
 Potenciais de um alfabeto
 Fechamento
 Prefixo, Sufixo, Subcadeia
 Concatenação de cadeias
 Concatenação sucessiva de cadeias
Prof. Willian Magalhães 2
Linguagem
 Dado um alfabeto Σ, o conjunto de palavras 𝐿 é uma
linguagem sobre Σ, se 𝐿⊆ Σ∗
Prof. Willian Magalhães 3
Linguagem
Σ∗
Operações sobre linguagens
 União
• 𝐿1 ∪ 𝐿2
 Intersecção
• 𝐿1 ∩ 𝐿2
 Diferença
• 𝐿1 − 𝐿2
 Concatenação
• 𝐿1. 𝐿2
Prof. Willian Magalhães 4
Operação - União
Prof. Willian Magalhães 5
 Σ = {0, 1}
 𝐿1 = 0, 11
 𝐿2 = 0, 1, 00
 𝐿1 ∪ 𝐿2 = {0, 11, 1, 00}
Operação - Intersecção
Prof. Willian Magalhães 6
 Σ = {0, 1}
 𝐿1 = 0, 11
 𝐿2 = 0, 1, 00
 𝐿1 ∩ 𝐿2 = 0
Operação - Diferença
Prof. Willian Magalhães 7
 Σ = {0, 1}
 𝐿1 = 0, 11
 𝐿2 = 0, 1, 00
 𝐿1 − 𝐿2 = 11
Operação - Concatenação
Prof. Willian Magalhães 8
 Σ = {0, 1}
 𝐿1 = 0, 11
 𝐿2 = 0, 1, 00
 𝐿1. 𝐿2 = {00, 01, 000, 110, 111, 1100}
Alfabeto, Símbolo, Cadeia, Linguagem
Prof. Willian Magalhães 9
Símbolo
Cadeia Linguagem
Alfabeto
elemento de
conjunto de
item de
sequência de
elemento de
conjunto de
Linguagens formais
Prof. Willian Magalhães 10
 Para descrever uma linguagem, sendo ela finita ou infinita, 
existem os formalismos matemáticos
 Existem 3 tipos de formalismos...
Tipos de formalismos
Prof. Willian Magalhães 11
 Reconhecedores
• Recebe uma palavra e retorna um valor para dizer se ela
faz parte ou não da linguagem
 Geradores
• Define um conjunto de regras que podem ser
combinadas para gerar cadeias
 Denotacionais
• Uma expressão que denota de modo geral as palavras
da linguagem
Linguagens formais
Prof. Willian Magalhães 12
 Para cada um dos três tipos veremos que existem diversos
formalismos
 Linguagens são classificadas segundo os formalismos que
as reconhecem
Hierarquia de Chomsky
Prof. Willian Magalhães 13
 Quatro categorias hierárquicas
 Categorias superiores incluem todas as demais
 Cada categoria é reconhecida por certos formalismos
característicos
Hierarquia de Chomsky
Prof. Willian Magalhães 14
Linguagens
Livres de Contexto
Linguagens
Sensíveis ao Contexto
Linguagens 
Enumeráveis Recursivamente
Linguagens Regulares
Tipo 0
Tipo 1
Tipo 2
Tipo 3
MT
NORMA
POST
AP
GLC
AFD
AFND
AFS
GR
ER
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 15