Conceitos Fundamentais: Alfabetos, Cadeias, Linguagem e Gramática

...

apresentadas no capítulo 1, definemse

a seguir as operações de concatenação e fechamentos;

Sejam L1, L2, duas linguagens, a concatenação L1.L2 , ou simplesmente L1L2 é

definida formalmente como:

L1L2 = {w = w1w2 | w1 L1 e w2  L2 }

O fechamento recursivo e transitivo de um alfabeto  é definido como o conjunto

infinito que contém todas as possíveis cadeias que podem ser construídas sobre o

alfabeto dado, incluindo a cadeia vazia, e é denotado por *.

O fechamento transitivo denotado por + representa o conjunto de todas as

cadeias sobre o alfabeto  excetuando-se a cadeia vazia, ou seja:

+ = * - {}

Exemplo: Seja o alfabeto unário  = { 0 }, tem-se que :

* = {, 0, 00, 000, 0000, 00000, ...}

+ = {0, 00, 000, 0000, 00000, ...}

A complementação de uma linguagem L definida sobre um alfabeto é:

L’ = * - L

Exemplo: Seja o alfabeto  = { 0, 1 }, seja a Linguagem L definida sobre o alfabeto

, com L = {w | w começa com o símbolo 0}. Tem-se que:

L’ = {w | w começa com o símbolo 0}  {}

2.2 Gramática: dispositivo gerador de uma Linguagem.

Gramáticas são dispositivos geradores das cadeias que pertencem a uma

Linguagem.

Formalmente, uma gramática é uma quádrupla G = (V, , P, S), onde:

V = conjunto finito de símbolos não-terminais.

 = conjunto finito de símbolos terminais da gramática. Este conjunto também é

denominado alfabeto.

S  V e é denominado símbolo inicial ou raiz da gramática;

P = conjunto de produções ou regras de substituição da gramática.

Uma regra de produção é representada da seguinte forma:

 onde,   (V )+ e  (V )*.

Naturalmente,   (V  )+ informa que no lado esquerdo da produção deve existir

um ou mais símbolos, terminais ou não-terminais. Analogamente, a expressão  

(V T)* indica que no lado direito da produção podem figurar quaisquer cadeias de

símbolos terminais, não-terminais e até mesmo isoladamente, a cadeia vazia.

Exemplo: Seja G1 = (V, , P, S), onde:

V = {S, X, Y}

 = {a, b, c }

P = { S  a X

X  c Y | bX

Y  c Y |  }

S é o símbolo inicial da gramática.

Observação: O símbolo “|” é traduzido como “ou”. Assim sendo, escrever

X  c Y | bX , equivale a representar o seguinte conjunto de regras:

X  cY ; X  b X ;

Exemplo:

G2 = (V, , P, S), onde:

V = {Declaracao, Tipo, Lista, Id}

 = {int, real, x, y, ; , , }

Declaracao é o símbolo inicial da gramática.

O conjunto das produções é representado por:

P = { Declaracao  Tipo Lista ;

Tipo  int | real

Lista  Id | Id, Lista

Id  x | y

}

2.3 Derivação de cadeias e árvores de derivação.

A aplicação de uma regra de produção  é denominada derivação. A derivação

é representada pelo símbolo  .

Exemplo: Considere a Linguagem:

L = {w | w começa com o símbolo a ou b e termina com a subcadeia aa}

A gramática geradora da Linguagem L é G3 = (V,  , P, S},

onde: V = {S, X, Y, Z} é o conjunto dos símbolos não terminais;

 = {a, b} é o alfabeto;

S é o símbolo inicial da gramática;

P = { S  aX | bX; X  bX | aY; Y aZ | bX; ZaZ | } é o conjunto das

produções.

Naturalmente, a palavra w = bbaa pertence a L, o que pode ser verificado através

da seguinte sequência de aplicações das produções:

S  b X  a  bbX  bbaY  bbaaZ  bbaaZ  bbaa  bbaa

Exemplo: Considere a gramática G2 apresentada na seção anterior.

A seguir, a título de ilustração, são apresentadas aplicações sucessivas das regras

da gramática G2. Para ainda mais claramente se explanar, as produções são

apresentadas novamente, enumeradas.

Declaracao  Tipo Lista ; (regra 1)

Tipo  int (regra 2)

Tipo  real (regra 3)

Lista  Id (regra 4)

Lista  Id , Lista (regra 5)

Id  x (regra 6)

Id  y (regra 7)

Considere-se a seguinte sequência de derivações, a partir do símbolo inicial

Declaracao.