Cap 01 Introdu O E Conceitos B Sicos

Li nguagensFor mai se Aut ômat os
Paul
oBl aut hMenez es Linguagens Formais e Autômatos
P. Blauth Menezes
1
2
3
4
5
6
7
8
9

Linguagens Formais e Autômatos

Introdução e Conceitos Básicos
Linguagens e Gramáticas
Linguagens Regulares
Propriedades das Linguagens Regulares
Autômato Finito com Saída
Linguagens Livres do Contexto
Propriedades e Reconhecimento das Linguagens
Livres do Contexto
Linguagens Recursivamente Enumeráveis e
Sensíveis ao Contexto
Hierarquia de Classes de Linguagens e Conclusões

2

1 – Introdução e Conceitos
Básicos
1.1 Introdução
1.1.1 Sintaxe e Semântica
1.1.2 Abordagem
1.2 Conjuntos, Relações e Funções
1.3 Noções de Lógica
1.4 Técnicas de Demonstração
1.5 Indução
Linguagens Formais e Autômatos

3

1 – Introdução e Conceitos Básicos
Linguagens Formais e Autômatos

4

1.1 Introdução
Teoria das linguagens formais
• desenvolvida na década de 1950
• o objetivo inicial foi desenvolver teorias relacionadas com as linguagens naturais
• entretanto, logo foi verificado que era importante:
∗ estudo de linguagens artificiais
∗ em especial, para as linguagens originárias da computação e informática • desde então, desenvolveu-se significativamente

Linguagens Formais e Autômatos

5

Exemplos de aplicações
• análise léxica e análise sintática de linguagens de programação
• modelagem de circuitos lógicos ou redes lógicas
• modelagem de sistemas biológicos

Mais recentemente
• animações
• hipertextos e hipermídias
• linguagens não lineares
∗ planares
∗ espaciais
∗ n-dimensionais

Linguagens Formais e Autômatos

6

1 – Introdução e Conceitos
Básicos
1.1 Introdução
1.1.1 Sintaxe e Semântica
1.1.2 Abordagem
1.2 Conjuntos, Relações e Funções
1.3 Noções de Lógica
1.4 Técnicas de Demonstração
1.5 Indução

Linguagens Formais e Autômatos

7

1.1.1

Sintaxe e Semântica

Linguagens formais
• problemas sintáticos das linguagens

Importante apresentar os conceitos de
• sintaxe e semântica

Historicamente, o problema sintático
• reconhecido antes do problema