Baixe o app para aproveitar ainda mais
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
Compartilhar