Nada

CAPÍTULO 2

PALAVRAS E LINGUAGENS

2.1. PALAVRAS

Chamaremos de alfabeto um conjunto não vazio de símbolos ou letras, geralmente denotado por .

Exemplo 2.1.1

1 = { 0, 1 }, 2 = { a, b }, 3 = { begin, end, if }

Os símbolos de  são indivisíveis. Assim, em 3 do exemplo acima, begin, end e if são símbolos indivisíveis.

Uma palavra sobre um alfabeto  é uma seqüência finita de símbolos de .

Exemplo 2.1.2

Seja 1 = { a, b } e 2 = { ,  }.

Desse modo, a, b, aa, ab, bb e aaabba são palavras sobre o alfabeto 1, enquanto ,  e  são palavras sobre o alfabeto 2.

O comprimento de uma palavra w sobre um alfabeto  é o número de ocorrências das letras de  em w.

Exemplo 2.1.3

Seja a palavra w = a1a2a3...ak, k  1 e ai  , para 1  i  k. O comprimento de w é k, sendo este denotado por w = k.

É conveniente considerar uma palavra sem símbolos, a palavra nula, denotada por , e cujo comprimento é zero, isto é,  = 0.

Denotaremos por * o conjunto de todas as palavras sobre , enquanto + consistirá de todas as palavras sobre , exceto a palavra . Assim, += *- {  }.

Podemos definir * de uma maneira formal, recursivamente, como segue:
Definição 2.1.1

Seja  um alfabeto. *, o conjunto de todas as palavras sobre , é definido, recursivamente, do seguinte modo:

i) Base:   * ii) Recursão: Se w  * e a  , então wa  *.

Conforme evidenciado no capítulo 1, observe que omitimos o Fecho na definição recursiva acima. Tal Fecho diz que “w  * somente se w pode ser obtido a partir de  pela aplicação da recursão um número finito de vezes”.

O alfabeto  é um conjunto finito não-vazio, enquanto * é um conjunto infinito.

Exemplo 2.1.4

Se  = { a }, então * = { , a, aa, aaa, aaaa, ...........}.

Vamos usar a notação k para representar o conjunto de todas as palavras sobre  cujo comprimento é k.

Exemplo 2.1.5

Seja  = {a, b}. Assim, 0 = {}