Teste

Aula passada
• O que é linguagem

Linguagens formais e autômatos • Linguagem formal
• Alfabeto, palavra
• Concatenação

Americana, 12 de agosto de 2013
Prof. Alexandre Mello Ferreira

2

Aula de hoje

36

Entendendo asLinguagens Formais - Teoria, Modelagem e Implementação relações • Entendendo as relações
• Gramática

Figura 2.4: a, b, cadeias, sentenças e linguagem
3

4

2

A concatenação de duas linguagens X e Y , denotada por X · Y ou simplesmente
XY , corresponde a um conjunto Z formado pela coleção de todas as cadeias que possam ser obtidas pela concatenação de cadeias x ∈ X com cadeias y ∈ Y , nesta ordem.

Gramática

Gramática

• Gramática é o disposivito gerador de palavras

• Seja G=(V,T,P,S) uma gramática, a linguagem gerada

• Baseada em Regras de Produção

por G, denotada por L(G), é composta por todas as

• Formada pela quádrupla G=(V,T,P,S), onde:

palavras de símbolos terminais deriváveis a partir de

– V: conjunto de símbolos não terminais

S, ou seja:

– T: conjunto de símbolos disjuntos de V

L(G)={w∈T∗|S⇒w}

– P: conjunto de regras de produção
– S: elemento de V denominado inicial

5

Gramática

6

Gramática
Exemplo1: gerar qualquer número natural válido em uma

• Conjunto de regras de produção:

linguagem de programação. G=(V,T,P,N):

P é um conjunto finito de pares, tal que
P: (V ∪ T)+ → (V ∪ T)*

V={N,D}

• Uma regra de produção (α,β) é representada:

T={0,1,2,3,4,5,6,7,8,9}

α→β

P={N→D, N→DN, D→0|1|...|9}

7

8

Gramática

Gramática

Exemplo1: gerar qualquer número natural válido em uma

Derivando o número 243, temos:

linguagem de programação. G=(V,T,P,N):
Interpretação:

1. (N→DN): DN⇒
2. (D→2) : 2N⇒

Base: todo dígito é um número natual

3. (N→DN): 2DN⇒

V={N,D} se n é um número natural, então a
Passo:

4. (D→4) : 24N⇒

concatenação de n com qualquer dígito também é
T={0,1,2,3,4,5,6,7,8,9}
um número natural.

5.