Linguagens Formais e Autômatos - Introdução

Prévia do material em texto

LINGUAGENS FORMAIS E
AUTÔMATOS
Marcelo Guerra
PROFESSOR
 Marcelo Roberto Bastos Guerra Vale
 marceloguerra@ufersa.edu.br
 DCEN sala 31.
 Horário de atendimento: a combinar
 Mestre em Engenharia Elétrica na UFRN
 Doutorando no PPGEEc – UFRN
 Todo o material do curso foi cedido pela professora 
Mara Bonates.
 Adaptações feitas pelo professor Marcelo Guerra
ESTRUTURA DO CURSO
Aulas teóricas
 Aulas expositivas.
 Resolução de exercícios.
Avaliações
 Provas escritas.
 Trabalhos de implementação.
Nota dos trabalhos não ultrapassam 30% da nota
da unidade.
 Resolução de exercícios em aula.
Créditos extras.
OBJETIVOS
Estudar classes de linguagens e seus
respectivos formalismos reconhecedores, os
autômatos.
Estudar linguagens em ordem crescente de
complexidade e suas aplicações.
 Entender os modelos fundamentais de
computação e suas propriedades.
 Provocar curiosidade e interesse em
aspectos mais abstratos (e gerais) da Ciência
da Computação
EMENTA
 Linguagens Regulares
 Autômatos Finitos
 Linguagens Livres de Contexto
 Autômatos com Pilha
 Máquinas de Turing 
 O Problema da Parada da Máquina de Turing
 Hierarquia das Classes de Linguagem
BIBLIOGRAFIA
 Hopcroft, J.E.; Ullman, J.D,
Introdução à Teoria de
Autômatos, Linguagens e
Computação. Segunda Edição,
Ed. Campus/Elsevier. 2003.
BIBLIOGRAFIA
 Blauth, P. M. Linguagens Formais e
Autômatos. Série Livros Didáticos 3, Edição 2,
UFRGS, 1998.
BIBLIOGRAFIA
 Harry Lewys & Christos Papadimitriou,
Elementos de Teoria da Computação, Editora
Bookman, Porto Alegre, 2a. ed., 2000.
BIBLIOGRAFIA
Michael Sipser, Introdução à Teoria da
Computação, Editora Thompson, Tradução 2a.
ed., 2007.
 Rosa, J. L. G. Linguagens Formais e
Autômatos. Editora LTC, 2010.
 Acióly B. M.; Bedregal B. R., Introdução à Teoria
das linguagens formais, dos autômatos e da
computabilidade, Editora UnP, 1a. ed., 2002.
MOTIVAÇÃO
O que podemos fazer com os computadores?
O que jamais poderemos fazer com eles?
Como encontrar respostas a essas
perguntas?
INTRODUÇÃO
 Alan Turing foi um grande
matemático, lógico e criptoanalista.
 pioneiro na inteligência artificial e na
ciência da computação.
 A homossexualidade de Turing
resultou em um processo criminal em
1952
 Morreu em 1954, algumas semanas
antes de seu aniversário de 42 anos
 Em 10 de setembro de 2009, após uma campanha de
internet, o primeiro-ministro britânico Gordon
Brown fez um pedido oficial de desculpas público, em
nome do governo britânico
INTRODUÇÃO
 Alan Turing estudou uma máquina
abstrata que tinha todas as
características dos computadores
atuais.
 O objetivo era descrever o limite entre
o que uma máquina de computação
podia fazer e aquilo que ela não podia
fazer.
 As conclusões de Turing se aplicam não apenas às
suas máquinas de Turing abstratas, mas também
às máquinas reais de hoje.
INTRODUÇÃO
A Teoria dos Autômatos é o estudo dos
dispositivos de computação abstratos, ou
“máquinas”.
INTRODUÇÃO
 Teoria da computação
 A importância da teoria para a prática, em qualquer
ciência é imensa.
 Se entendermos por computação tudo o que um
computador pode realizar, devemos primeiro
entender o que um computador é.
 A resposta poderia ser dada em termos de hardware e
tecnologia, mas não podemos nos limitar à tecnologia
do momento.
 Isto nos levará, irremediavelmente, a definir uma noção
abstrata de computador.
 A construção de modelos é essencial em qualquer
disciplina científica.
INTRODUÇÃO
 Teoria da Computação:
 Fundamenta diversas aplicações computacionais, tais como:
 Software de verificação de circuitos digitais
 Analisadores léxicos
 Motores de busca na Web
 Software para verificar sistemas com número de estados finito,
como protocolos para comunicações
 Sub-áreas:
 Teoria das linguagens formais
 Teoria da computabilidade e os limites da computação
INTRODUÇÃO
 Teoria da Computação e os limites da computação:
 A Teoria da Computação nos permite deduzir se temos a
chance de, ao nos depararmos com um problema, sermos
capazes de resolve-lo, ou se teremos de descobrir algum
modo de contornar o problema intratável.
 Encontrar uma aproximação, uma heurística ou limitar o período
de tempo de execução do programa.
LINGUAGENS FORMAIS
TEORIA DAS LINGUAGENS FORMAIS
 Linguagens formais são mecanismos formais para
representação e especificação de linguagens, baseados na
chamada Teoria da Computação.
 As representações podem ser feitas por:
 Reconhecedores: dispositivos formais que servem para
verificar se uma sentença pertence ou não à determinada
linguagem.
 Autômatos.
 Geradores: dispositivos formais que permitem a geração
sistemática de todas as sentenças de uma linguagem.
 Gramáticas.
LINGUAGENS FORMAIS
 Em nossa linguagem natural usamos letras, palavras e
sentenças.
 Grupos de letras constituem uma palavra e grupos de
palavras constituem uma sentença.
 Mas, nem toda concatenação de letras forma uma palavra,
nem toda sequência de palavras uma sentença.
 A situação também se verifica para as linguagens de
programação, na qual certos agrupamentos de palavras
chave são um comando e algumas sequências de comandos
são programas.
LINGUAGENS FORMAIS
 É necessária uma teoria geral que unifique todos
esses casos.
 Definição de uma estrutura onde a decisão de quando
uma cadeia de unidades constitui uma unidade maior
válida seja baseada na aplicação de regras
explicitamente definidas.
LINGUAGENS FORMAIS
 Em linguagens naturais não podemos dar regras
para descrever todas as frases, pois nos permite
construir frases sem sentido.
 Ex: <artigo><substantivo><verbo> => “o gato late”
 É difícil estabelecer quais frases fazem sentido,
porque dependem de nossa habilidade para
interpretar metáforas poéticas.
LINGUAGENS FORMAIS
 Isto não acontece com as linguagens de
programação, pois elas são formais.
 O compilador de uma linguagem de programação
é um procedimento que analisa a corretude de
uma seqüência de símbolos e determina se ela
constitui um programa válido ou não.
 Assim, o compilador não procura saber o que o
programa faz, mas se ele está corretamente
escrito.
LINGUAGENS FORMAIS
 A palavra “formal” nos diz que todas as regras
para a linguagem são explicitamente declaradas
em termos das cadeias de símbolos que podem
ocorrer nela.
 Sentenças são consideradas como meros
símbolos e não como expressões de idéias na
mente humana.
CONCEITOS ELEMENTARES
DA TEORIA DOS AUTÔMATOS
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 Alfabeto
 É um conjunto não-vazio e finito de símbolos. 
 Representação: Σ (sigma)
 Exemplos:
 Σ = {0,1}, o alfabeto binário.
 Σ = {a,b,...,z}, o alfabeto de todas as letras minúsculas.
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 String, cadeia ou palavra
 É uma seqüência finita de símbolos escolhidos de algum
alfabeto.
 Representação:
 letras minúsculas do inicio do alfabeto para representar elementos
do alfabeto (a,b,c...).
 letras minúsculas do final do alfabeto para indicar nomes de cadeias
(...w,x,y,z).
 Exemplos:
 Se o alfabeto for Σ = {a,b} então w = abab e z = aaabba são cadeias
sobre Σ.
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 A cadeia vazia é a cadeia com zero ocorrências de
símbolos.
 Representação: ε (Épsilon) ou λ (Lambda).
 A concatenação de duas cadeias w e v, é denotado por
wv.
 Se w=a1...an e v=b1...bm então wv=a1...anb1...bm. O comprimento de uma cadeia w, denotado por |w|, é
o número de símbolos que figuram na cadeia.
 Exemplos:
 |abba|= 4
 | ε |=0.
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 Potências de um alfabeto
 Se Σ é um alfabeto, podemos expressar o conjunto de todas
as cadeias de um certo comprimento desse alfabeto, usando
uma notação exponencial Σk.
 Σ0 = { ε }, independente de qual alfabeto seja Σ.
 Seja Σ= {0,1},
 Σ1 = {0,1}, 
 Σ2={00,01,10,11}, 
 Σ3= {000,001,010,011,...,111}.
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 Fecho Estrela
 O fecho estrela de um alfabeto Σ, denotado por Σ*, é o
conjunto de todas as cadeias (finitas) sobre Σ.
 Σ* = Σ0 Σ1 Σ2 Σ3 ...
 Exemplo: {0,1}* = { ε, 0, 1, 00, 01, 10, 11, 000,... }
CONCEITOS ELEMENTARES DA TEORIA DOS
AUTÔMATOS
 Fecho positivo
 O conjunto Σ* sempre contém ε. O fecho estrela de Σ
sem a cadeia vazia é denominado fecho positivo do
alfabeto Σ, e é denotado por Σ+.
 Desse modo, duas equivalências são apropriadas:
 Σ+ = Σ1 Σ2 Σ3 ...
 Σ* = Σ+ {ε}
LINGUAGENS
 Um subconjunto qualquer de Σ* pode ser visto
como uma linguagem sobre o alfabeto Σ.
 Uma cadeia w numa linguagem L, isto é, w L,
será chamada sentença de L.
 Exemplo: seja Σ = {a,b}.
 Então Σ* = {ε, a, b, aa, ab, ba, bb, ...}.
 O conjunto {a, aa, aab} é uma linguagem sobre Σ.
LINGUAGENS
 Linguagem Finita
 Quantidade finita de palavras.
 Linguagem Infinita
 Exemplo: dado o alfabeto = {a, b}, o conjunto
L = {anbn | n ≥ 0} é uma linguagem L sobre o alfabeto
Σ.
 OBS: As cadeias aabb e aaaabbbb são palavras de L, mas
a cadeia abb não está em L.
LINGUAGENS
 Exemplos de linguagens:
 Português: coleção de palavras válidas na língua.
 C: programas válidos são um subconjunto dos strings possíveis
que podem ser formados a partir do alfabeto da linguagem.
 Linguagem de todos os strings que consistem em n 0’s seguidos
por n valores 1, para algum n ≥ 0: {ε, 01, 0011, 000111, ...}.
 O conjunto de strings de 0’s e 1’s com um número igual de cada
um deles: {ε, 01, 10, 0011, 0101, 1001,...}.
 A única restrição importante sobre o que pode ser uma
linguagem é que todos os alfabetos são finitos.
GRAMÁTICAS
GRAMÁTICAS
 Para estudar linguagens matematicamente, precisamos de um
mecanismo para descrevê-las.
 As gramáticas são uma poderosa ferramenta para definir
linguagens.
 Uma gramática para a língua portuguesa nos diz se uma
sentença, em particular, é bem formada ou não.
 <oração> : <sujeito> <predicado>
 <sujeito> : <artigo><substantivo>
 <predicado> : <verbo><complemento>
 Sentenças como: “um cão corre na praia” e “uma menina
caminha lentamente” são bem formadas.
GRAMÁTICA
 Definição: Uma gramática G é definida como uma
quádrupla G = < V, T, S, P >, onde:
 V é um conjunto finito de objetos, chamados
variáveis.
 T é um conjunto finito de objetos, disjunto de V,
chamados símbolos terminais.
 S V é um símbolo especial, chamado variável de
início.
 P é um conjunto finito de produções.
GRAMÁTICA
 Considere a gramática G = < {S}, {a,b}, S, P >
onde P é dado por:
 S aSb
 S ε
 O principal na gramática são as regras de
produção.
 Elas especificam como a gramática transforma uma
cadeia em outra, e através disso elas definem
uma linguagem associada à gramática.
GRAMÁTICA
 Assumiremos que todas as produções são da forma:
x y
onde x é um elemento de (V T)+ e y está em (V T)*.
GRAMÁTICA
 As produções são aplicadas como segue:
 dada uma cadeia da forma:
w uxv
dizemos que a produção x y é aplicável a esta
cadeia, e podemos usá-la para trocar x por y,
obtendo assim, a nova cadeia
z uyv
Neste caso, dizemos que w deriva z,
denotado por w z.
GRAMÁTICA
 G = <{S}, {a,b}, S, P>, onde P é dado por:
 S aSb
 S ε
 Então S aSb aaSbb aabb.
 Logo, podemos escrever: S aabb.
 A cadeia aabb é uma sentença na linguagem
gerada por G, enquanto aaSbb é uma forma
sentencial.