Computação nas nuvens

Linguagens Formais e
Autômatos
P. Blauth Menezes [e-mail] Departamento de Informática Teórica
Instituto de Informática / UFRGS

Matemática Discreta para Ciência da Computação - P. Blauth Menezes

1

Linguagens Formais e Autômatos
P. Blauth Menezes
1
2
3
4
5
6
7
8
9

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 e Linguagens e Conclusões

Linguagens Formais e Autômatos - P. Blauth Menezes

2

2 – Linguagens e Gramáticas
2.1
2.2
2.3
2.4

Alfabeto
Palavra
Linguagem Formal
Gramática

Linguagens Formais e Autômatos - P. Blauth Menezes

3

2 Linguagens e Gramáticas
◆

Linguagem: Dicionário Aurélio o uso da palavra articulada ou escrita como meio de expressão e comunicação entre pessoas

◆

Não é suficientemente precisa para
• desenvolvimento matemático de uma teoria baseada em linguagens Linguagens Formais e Autômatos - P. Blauth Menezes

4

◆

Linguagem
• conceito fundamental em Computação e Informática

◆

Para definir linguagem
• alfabeto
• palavra ou cadeia de caracteres

Linguagens Formais e Autômatos - P. Blauth Menezes

5

2 – Linguagens e Gramáticas
2.1
2.2
2.3
2.4

Alfabeto
Palavra
Linguagem Formal
Gramática

Linguagens Formais e Autômatos - P. Blauth Menezes

6

2.1 Alfabeto
◆

Símbolo ou Caractere
• entidade abstrata básica, não definida formalmente
• base para definições
• exemplos: letras e dígitos

Def: Alfabeto
Conjunto finito de símbolos ou caracteres
◆

Portanto
• conjunto infinito não é alfabeto
• ∅ é um alfabeto

Linguagens Formais e Autômatos - P. Blauth Menezes

7

Exp: Alfabeto
São alfabetos
• { a, b, c }
• ∅ (conjunto vazio)
Não são