View
19
Download
0
Category
Preview:
Citation preview
Linguagens Formais e Autômatos
Hisham Muhammadh@hisham.hm
PUC-Rio
Sobre o professor
● Hisham H. Muhammad– MSc. em Informática pela PUC-Rio
– Doutorando na área de Linguagens de Programação
– Grupo do LabLua, Prof. Roberto Ierusalimschy● http://www.lua.inf.puc-rio.br
O que é esta disciplina?
● Linguagens Formais e Autômatos
O que é esta disciplina?
● Linguagens Formais e Autômatos– O que são linguagens?
– O que quer dizer "formal"?
– O que são autômatos?
Teoria das linguagens formais
● Nasceu nos anos 1950 para tratar linguagens naturais
● Análise léxica, análise sintática...
Nós acreditamos sempre em dias melhores
Sujeito Predicado verbal
Adjuntoadverbial
Objeto indireto
Predicativo do objeto
Oração
Teoria de linguagens formais
● Adotada no estudo de linguagens artificiais● Aplicações
– Análise léxica e sintática de linguagens de programação
● Parsers, compiladores
– Circuitos lógicos
– Animação
– Bioinformática
– etc...
"Formal"
● Linguagens formais × informais?
"Formal"
● Linguagens formais × informais?● Forma × função
– Forma: sintaxe
– Função: semântica
"Formal"
● Linguagens formais × informais?● Forma × função
– Forma: sintaxe
– Função: semântica
● Linguagens formais são linguagens que têm uma forma bem-definida ("fórmula bem formada", matematicamente falando)– Ou seja, vamos tratar de sintaxe
"Formal"
● Linguagens formais × informais?● Forma × função
– Forma: sintaxe
– Função: semântica
● Linguagens formais são linguagens que têm uma forma bem-definida ("fórmula bem formada", matematicamente falando)– Ou seja, vamos tratar de sintaxe
– ... mas linguagens formais também são menos "informais"
Linguagens formais
● Alfabetos● Palavras● Gramáticas● Linguagens
block ::= {stat} [retstat]stat ::= ‘;’ | varlist ‘=’ explist | functioncall | break | do block end | while exp do block end | repeat block until exp | if exp then block {elseif exp then block} [else block] end | for Name ‘=’ exp ‘,’ exp [‘,’ exp] do block end | for namelist in explist do block end | function funcname funcbody | local function Name funcbody | local namelist [‘=’ explist] retstat ::= return [explist] [‘;’]funcname ::= Name {‘.’ Name} [‘:’ Name]varlist ::= var {‘,’ var}var ::= Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name namelist ::= Name {‘,’ Name}explist ::= exp {‘,’ exp}exp ::= nil | false | true | Number | String | ‘...’ | functiondef | prefixexp | tableconstructor | exp binop exp | unop exp binop ::= ‘+’ | ‘-’ | ‘*’ | ‘/’ | ‘^’ | ‘%’ | ‘..’ | ‘<’ | ‘<=’ | ‘>’ | ‘>=’ | ‘==’ | ‘~=’ | and | orunop ::= ‘-’ | not | ‘#’
Hierarquia de Linguagens Formais
● Noam Chomsky, 1956
Hierarquia de Chomsky
Tipo 0: Gramáticas irrestritas
Tipo 1: Gramáticas sensíveis ao contexto
Tipo 2: Gramáticas livres de contexto
Tipo 3: Gramáticas regulares
Hierarquia de Chomsky
Tipo 0: Linguagens recursivamente enumeráveis
Tipo 1: Linguagens sensíveis ao contexto
Tipo 2: Linguagens livres de contexto
Tipo 3: Linguagens regulares
...e Autômatos
● Estudo dos dispositivos de computação abstratos, ou "máquinas"– Década de 1930, precede os computadores
● Da axiomatização da matemática (Russell, Whitehead)...– Prove que 1+1=2... 362 páginas
● ...surgiu a necessidade de definir o que é possível ou não de se fazer– ...matematicamente?
– ...mecanicamente?
Autômatos
● Antes de nos perguntarmos sobre os limites fundamentais da computação, precisamos de modelos
● Modelo abstrato de máquina: diagrama de estados
off onInício
Liga
Desliga
Relação com linguagens
...e de fato:
Tipo 0: Máquina de Turing
Tipo 1: Autômato linearmente limitado
Tipo 2: Autômato de pilha
Tipo 3: Autômato de estados finitos
e mais:
Máquina de Turing D/ND
Autômato linearmente limitado D (=?...)
Autômato de pilha ND
Autômato finito D/ND
Autômato de pilha D
Autômato linearmente limitado ND
Diferença de abordagens
● Autômatos
– Abordagem operacional
– Máquinas abstratas com estados, instruções primitivas
– Permitem a análise de uma entrada para verificar se é "reconhecida" pela máquina
● Gramáticas
– Abordagem axiomática
– Associam-se regras aos componentes da linguagem
– Permitem verificar se uma cadeia pode ser "gerada" a partir dos axiomas
LFA: Convergência de disciplinas
● Matemática discreta● Linguística formal● Computação teórica
Objetivos do curso
● Formativos
– Projetar gramáticas para especificar linguagens
– Projetar autômatos para reconhecer linguagens
– Classificar linguagens formais em função dos seus reconhecedores e gramáticas
– Entender o papel do não-determinismo na computação● Informativos
– História da Computação
– Limitações do processo computacional
– Hierarquia de Chomsky
– Hierarquia de complexidade
Programa da disciplina
● Alfabetos, cadeias e linguagens● Gramáticas, derivação, linguagem definida por
gramática● Linguagens regulares e autômatos finitos● Linguagens livres de contexto e autâmatos de pilha● Linguagens sensíveis ao contexto e autômatos
linearmente limitados● Linguagens recursivamente enumeráveis e
Máquinas de Turing● Decidibilidade e computabilidade
Bibliografia
● Livro texto: Paulo Blauth Menezes, "Linguagens Formais e Autômatos", 6.ed. Bookman 2011
● Referência: Hopcroft, Ullman & Motwani "Introdução à Teoria de Autômatos, Linguagens e Computação", 2.ed, Campus 2002
● Complementar: Apostila do Prof. José Lucas Rangel http://www.tecmf.inf.puc-rio.br/LFA
● Complementar: Notas complementares e material suplementar http://www.tecmf.inf.puc-rio.br/LFA
● Site desta turma, slides das aulas:
http://hisham.hm/puc-rio/lfa/
Créditos e referências
● Slides do Prof. Hermann
– http://www.tecmf.inf.puc-rio.br/LFA?action=AttachFile&do=view&target=Aulas-LFA-1.pdf
● Slides da Profª. Clarisse
– http://www.inf.puc-rio.br/~inf1626/docs/Aula01-Introducao.pdf
Recommended