Notas de Aula Teoria da Computação

1. Linguagem Formal:

- Sofre um grande número de restrições, sem teor “nebuloso”. Está montada sobre estrutura finita (alfabeto). A linguagem é um conjunto (palavras, textos). Por exemplo, dicionário -> linguagem mais simples.

Nossa linguagem é obtida pela concatenação de um alfabeto. Ela tem significado pluridimensional.

Linguagens são formadas por cadeias finitas de símbolos pertencentes a um alfabeto.

Cadeias de símbolos tem comprimento definido pelo número de posições ocupadas pelos símbolos ao longo da mesma.

Seja w uma cadeia de símbolos sobre um alfabeto Σ = {ό1, ό2, ..., όn} , com w= όw1, όw2... όwl, então o comprimento de w, denota-se |w| é dado por |w|=L.

A linguagem pode ser infinita, exemplo: números inteiros positivos, mas o alfabeto é finito {0,1,2,3,4,5,6,7,8,9}. Conjuntos finitos são enumeráveis. O conjunto dos números reais é enumerável.

Σ = {a,b}

L= {w = ay| y possui 0 ou mais ocorrências de a ou b}

Ex: a, ab, abb, aba...

Neste caso a linguagem é infinita.

2. Operações sobre cadeias e linguagens:

• Concatenação de duas Cadeias

u e v é definida como uma nova cadeia cuja primeira parte é a cadeia u seguida da cadeia v. Sobre u e v são definidas as seguintes operações:

1. u= u1u2...un v=v1v2...vn

2. uv= u1v1...umv1v2...vm

3. Ǝε |Uε = εU =U, |ε|=0 ε é um Elemento Neutro, uma palavra vazia ou cadeia vazia.

• Concatenação de Linguagens

A e B é definida como sendo a seguinte linguagem AB= {w= uv| u ∈ A ^ v ∈ B}

A(Σa), B(Σb)

AB (ΣA U ΣB)

1. AB ≠ BA

2. {ε}A = A{ε} = A

3. Ǝ ∅| A U ∅ = ∅ U A = A

Atenção: a operação de concatenação é diferente da operação de união, se concatenasse A com Vazio, teria Vazio como resultado.

• Potência de Concatenações de Cadeia

|w| = k

W sobre Σ, define-se wn = w.w.w.w...w (n fatores)

|wn|= n. |w| = nk

Wn.W = Wn+1

Valem as regras para multiplicação de potências de bases iguais.

Então, Ǝ w0 | w0. wn = wn.w0= wn -> w0 = ε

Se apresentarmos uma string tal que w=uv, u é prefixo sw w. Se u = w então u é prefixo impróprio(ou seja, é a própria palavra) de w. Se u ≠ w então, u é prefixo próprio de w.

ε não tem prefixo próprio.

• Potência de Linguagens