Conceitos Fundamentais: Alfabetos, Cadeias, Linguagem e Gramática
Por: Afonso Carvalho • 7/4/2017 • Artigo • 1.838 Palavras (8 Páginas) • 529 Visualizações
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 12 = 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,
...