Teoria de Linguagens Formais - cear.ufpb.br · Linguagens Enumeráveis Recursivamente (Tipo 0)...

Teoria de Linguagens Formais

Prof. Juan Moises Mauricio Villanueva

jmauricio@cear.ufpb.br

www.cear.ufpb.br

1

• 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

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

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

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

1. Linguagens Formais

6

0

1

2

{ }

{ , }

{ , , , }

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

1. Linguagens Formais

8

1 2 3

1

* 0 1 2 3

0

...

.. { }

k

k

k

k

1. Linguagens Formais

9

1. Linguagens Formais

10

1. Linguagens Formais

11

*{ : ^ }

Por tanto :

L u v uv L

L L

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

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)

2. Linguagens Regulares

14

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

2. Linguagens Regulares

16

palavra nula .