16
Teoria de Linguagens Formais Prof. Juan Moises Mauricio Villanueva [email protected] www.cear.ufpb.br 1

Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

  • Upload
    others

  • View
    12

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

Teoria de Linguagens Formais

Prof. Juan Moises Mauricio Villanueva

[email protected]

www.cear.ufpb.br

1

Page 2: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

• Usando para expressar formalmente uma linguagem computacional

• Abordagem teórica de Sintaxe e Semântica

Sintaxe: Checagem de instruções de programa

Semântica: Erros de programas em lógicas (mais complicados de serem identificados)

2

1. Linguagens Formais

Page 3: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Um símbolo designado por é uma entidade.

• Letras e dígitos são exemplos típicos de símbolos

• A partir de um conjunto de símbolos, é possível definir um alfabeto.

• Definição de Alfabeto

Alfabeto é um conjunto não vazio de símbolos, representado por

={, , } é um alfabeto formado pelos símbolos , , .

A combinação dos símbolos de um alfabeto é denominado palavra.

3

Page 4: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Definição de Palavra

A palavra sobre o alfabeto é qualquer combinação de um número finito de símbolos (com ou sem repetição) de , na forma:

4

0,1 010101 ; 1010111

, , ,..., ;

Alfabetos Palavras

a b c z automatica abc

Palavras com os símbolos dos alfabetos

Page 5: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Definição de Comprimento de uma Palavra

O comprimento de uma palavra s, representada por |s|, é igual ao número de símbolos que a compõem.

5

0,1 010101 010101 6

, , ,..., 10

Alfabetos Palavras Comprimento

a b c z automatica automatica

Page 6: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

6

0

1

2

{ }

{ , }

{ , , , }

Page 7: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Concatenação de palavras

Dada duas palavras s1 e s2 sobre um alfabeto , com

s1=12...k

s2=k+1k+2...n

A concatenação de s1 e s2, definido por “s1s2” é dada por:

s1 s2 =12...kk+1k+2...n

7

Page 8: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

8

1 2 3

1

* 0 1 2 3

0

...

.. { }

k

k

k

k

Page 9: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

9

Page 10: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

10

Page 11: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

11

*{ : ^ }

Por tanto :

L u v uv L

L L

Page 12: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Tipos de Formalismos

Reconhecedores: recebe uma palavra e retorna um valor para indicar se é ou não da linguagem

Geradores: define um conjunto de regras que podem ser combinadas para gerar palavras

12

Page 13: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

1. Linguagens Formais

• Classificação das Linguagens

13

Linguagens Enumeráveis Recursivamente (Tipo 0)

Linguagens Sensíveis ao Contexto (Tipo 1)

Linguagens Livres do Contexto (Tipo 2)

Linguagens Regulares (Tipo 3)

Page 14: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

2. Linguagens Regulares

14

Page 15: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

2. Linguagens Regulares

• Formalismo Reconhecedor

Recebe uma palavra de entrada contida em uma linguagem

Dada uma linguagem deve-se indicas se a palavra é aceita ou rejeitada

15

Page 16: Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0) Linguagens Sensíveis ao Contexto (Tipo 1) Linguagens Livres do Contexto (Tipo 2) Linguagens

2. Linguagens Regulares

16

palavra nula .