Buscar

Linguagens Formais e Aut matos Aula 0 Introdu o 09.08.2017

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 32 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 32 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 32 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Introdução
Teoria dos Autômatos
• A teoria dos Autômatos é o estudo dos
dispositivos abstratos, ou “máquinas”.
• Na década de 30, antes de existirem os
computadores, Alan Turing estudou uma
máquina abstrata que tinha todas as
características dos computadores atuais.
Teoria dos Autômatos
• Seu objetivo era descrever com exatidão o limite
entre o que uma máquina de computação
poderia fazer e aquilo que ela não podia fazer.
• Nas décadas de 40 e 50, tipos de máquinas mais
simples, que hoje chamamos de Autômatos
Finitos, foram estudadas por diversos
pesquisadores, tendo sido propostas
inicialmente para modelar as funções cerebrais.
Linguagens Formais
• No fim dos anos 50, o linguista Noam Chomsky
iniciou o estudo de Gramáticas Formais.
• Embora não sejam estritamente máquinas, essas
gramáticas têm relacionamentos estreitos com
os autômatos abstratos.
• Hoje servem como base de alguns importantes
componentes de software, incluindo algumas
partes de compiladores.
Linguagens Formais e Autômatos
• Em 1969, Stephen Cook conseguiu separar os
problemas que podem ser resolvidos de forma
eficiente por computadores, daqueles que
podem em princípio ser resolvidos mas que, na
prática, levam tanto tempo que os
computadores são inúteis para solucionar todas
as instâncias do problema, exceto aquelas muito
pequenas.
• Os problemas dessa última classe são chamados
de intratáveis.
Linguagens Formais e Autômatos
• Primeiramente foi direcionado para questões
linguísticas e, representação e tratamento de
linguagem natural.
• Acabou sendo relacionada ao estudo de
linguagens artificiais, em especial, as originadas
da computação com aplicações voltadas para
compilação ou interpretação de linguagens de
programação em computadores digitais.
Aplicações clássicas na Computação
• análise léxica e análise sintática de linguagens de
programação.
• modelagem de circuitos lógicos ou redes lógicas.
• Processamento de linguagens de programação
textuais.
• Representação de Processos.
Aplicações clássicas na Computação
• Estruturas e Protocolos deComunicação.
• Fluxo lógico de Programas e Máquinas cujo
funcionamento depende de sucessiva alterações
no seu estado interno.
Aplicações Modernas na Computação
• Animações.
• Computação gráfica.
• Hipertextos e Hipermídias.
• InterfacesWeb.
• Linguagens visuais e não lineares em geral.
• Corresponde ao estudo de modelos
matemáticos que possibilitam a especificação e
o reconhecimento de linguagens (no sentido
amplo da palavra), suas classificações,
estruturas, propriedades, características e
inter-relacionamentos.
• Está associado aos estudos de linguística, mais
precisamente de sintaxe e semântica.
• Historicamente, no estudo do entendimento das
linguagens de programação, o problema
sintático foi reconhecido antes do problema
semântico e foi o primeiro a receber um
tratamento adequado.
• Houve um tempo em que foi dada uma grande
ênfase à sintaxe, ao ponto de levar à ideia de que
as questões das linguagens de programação
resumiam-se as questões da sintaxe.
• Atualmente, a teoria da sintaxe possui
construções matemáticas bem definidas e
universalmente reconhecidas como, por
exemplo, as Gramáticas de Chomsky.
• A sintaxe trata das propriedades livres da
linguagem como, por exemplo, a verificação
gramatical de programas.
• A semântica objetiva dar uma interpretação
para a linguagem como, por exemplo, um
significado ou valor para um determinado
programa.
• Consequentemente, a sintaxe basicamente
manipula símbolos sem considerar os seus
correspondentes significados.
• Sintaticamente falando, não existe uma noção
de programa “errado”.
• Por outro lado, um programa sintaticamente
valido (“correto”), pode não ser o programa que
o programador esperava escrever.
• Assim, a questão de considerar um programa
“correto” ou “errado” deve considerar se o
mesmo modela adequadamente o
comportamento desejado.
Sintaxe
• A sintaxe está relacionada com os aspectos
superficiais da linguagem – Estrutura e Forma.
• Funciona como um conjunto de regras de
combinação para formar palavras, frases e
sentenças.
Semântica
• A semântica está relacionada com o significado
dessas construções.
• Nós podemos até conhecer a estrutura (sintaxe)
de uma palavra, mas é necessário ligarmos ela a
semântica, senão nunca entenderemos o seu
significado.
• Exemplo:
roma amor ramo armo
Sintaxe e Semântica
• Exemplo:
• O que significa isso????
• Por mais que conheçamos a estrutura das
palavras acima, a sintaxe, podemos até nos
arriscar a pronunciá-las.
• Mas como não conhecemos a semântica, esse
enunciado não fará o mínimo sentido para nós.
Makemake Kuai Pihi. Pihi Momona.
Sintaxe e Semântica
• Exemplo:
• O que significa isso????
Makemake Kuai Pihi. Pihi Momona.
Quero comprar peixe. Peixe Gordo.
Sintaxe e Semântica
• Conforme a nossa convivência com linguagens
estranhas, passamos a compreendê-las de
maneiramais simples, conforme o tempo passa.
• A sintaxe e a semântica vão se articulando de
maneira automática em nossa mente.
Sintaxe e Semântica
• Exemplo:
• Você compreende isso?
• E isso?
The book is on the table.
System.out.println(“Alo Mundo !”);
Sintaxe e Semântica
• Exemplo:
“Powerful you have become, the dark side
I sense in you.”
“Poderoso você se tornou, o lado escuro 
sinto em você."
Sintaxe e Semântica
• Exemplo:
“When nine hundred years old you reach, 
look as good you will not.”
“Quando 900 anos de idade você chegar, tão 
boa aparência você não terá.”
Sintaxe e Semântica
• De quem são as frases???
MestreYoda
Sintaxe e Semântica
• Exemplo:
• Você compreende isso?
• Você compreende isso?
• Por mais que a estrutura sintática da segunda
frase esteja correta ela não faz sentido.
A mulher sorriu.
A mesa sorriu.
Sintaxe e Semântica
• Mas se a estrutura sintática for perfeita e a sua
semântica for defeituosa, podemos considerar
que o ato de comunicação foi um fracasso.
• Exemplo:
Ideias verdes incolores dormem 
furiosamente.
Sintaxe e Semântica
• Exemplo:
Os Átomos Todos Dançam
Madruga
Reluz Neblina
Crianças Cor De Romã
Entram No Vagão
Trem das cores
Caetano Veloso
Sintaxe e Semântica
• E se a estrutura de uma frase foi reorganizada
podemos obter um novo enunciado com sentido
totalmente diferente:
• Exemplo:
“Os políticos pensam que o público não 
sabe.”
“O público sabe que os políticos não 
pensam.”
Sintaxe e Semântica
• E às vezes, as falhas na estrutura sintática
podem originar falhas de entendimento
(semântica), são os casos de ambiguidades.
• Exemplo:
Márcia viu o homem no parque com o 
telescópio.
Autômato
• É uma máquina ou robô que se opera de maneira
automática.
• A palavra autômato é uma latinização da palavra
grega αὐτόματον, que significa agindo pela
vontade própria.
Autômato
• Émais comumente descrito como máquinas que
se movem sem a ajuda de eletricidade,
especialmente aquelas que realizam ações que
lembram humanos ou animais.
• Exemplo: como é o caso do cuco de um relógio
de parede.
Linguagens Formais e Autômatos
Máquinas de Turin
O Jogo da Imitação
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Introdução

Outros materiais