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

Módulo 02 - Conceitos Fundamentais: Alfabetos, Cadeias, Linguagem e

Gramática

 Definições de Alfabeto, Cadeias, Linguagens

 Gramática: dispositivo gerador de uma Linguagem.

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

2.1 Definições de Alfabeto, Cadeias, Linguagens

Alfabeto é um conjunto finito de símbolos. Cada símbolo é portanto, uma unidade

atômica empregada na construção de cadeias e se trata de um conceito primitivo,

sendo a sua representação visual irrelevante. São exemplos de alfabetos:

1 = { a, e, i, o, u}

2 = {0, 1, 2}

3 = {+, =, #}

Uma cadeia de caracteres, é uma sequência finita de símbolos de um alfabeto

justapostos. Exemplo: Seja 1 = { a, e, i, o, u}. São exemplos de cadeias: a, aa, ai, oi,

ui, eaea, ia, uaa.

Uma cadeia vazia é uma cadeia sem símbolos e é representada pelo símbolo .

O comprimento de uma cadeia , é o número de símbolos justapostos que se

apresentam na mesma. Representa-se como ||. Exemplos:

Para  = aaaa tem-se que || = 4.

Para  = a, tem-se que || = 1.

Para  = , tem-se que || = 0.

Duas cadeias definidas sobre o mesmo alfabeto podem ser combinadas e formar

uma terceira a partir da operação de concatenação. A concatenação das cadeias v e

 é representada por v e é formada pela justaposição de v e .

Exemplo:

Seja o alfabeto  = {a, s, m, o, r}

Seja 1 = somar e 2 = as. Tem-se que 12 = somaras.

A operação de concatenação é associativa, ou seja (uv)w = u(vw) quaisquer que

sejam as cadeias u, v e w.

Uma cadeia v é uma subcadeia de uma cadeia  se e somente se há cadeias x e

y tal que = xvy.

Um prefixo (respectivamente, sufixo) de uma cadeia é qualquer seqüência de

símbolos inicial (respectivamente, final) da cadeia.

Considere, por exemplo,  = ramos. São prefixos da cadeia : r, ram, ramo,

ramos. São sufixos de : ramos, amos, mos, os, s..

Para cada cadeia  e cada número natural i, define-se i conforme se segue:

0 =  (cadeia vazia)

i+1 = i 

Exemplo: Sejam o alfabeto  = {1, 0} e a cadeia  = 01. Tem-se que:

3 = =010101

1 =  = 01

0 = 

O reverso de uma cadeia , denotada por R, é definido como:

(1) se  = , então R = = ..

(2) Se  é uma cadeia de comprimento n+1 > 0, então  = ua para algum a 

e w e wR = auR.

Exemplos:

Sejam o alfabeto  = {a, b} e  = ba. Tem-se que R = ab.

Sejam o alfabeto  = {a, t, o, r} e  = ator. Tem-se que R = rota.

Linguagem formal é um conjunto finito ou infinito, de cadeias de comprimento

finito, sobre um alfabeto finito e não vazio..

Seja o alfabeto  = {a, b}. A seguir, são apresentados exemplos de Linguagens,

cujas cadeias são definidas sobre o alfabeto .

a) L1 = 

b) L2 = {}

c) L3 = {a,ab,ba, bb, aaa}

Além das operações definidas para conjuntos 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,