alfabeto e linguagem

alfabeto e linguagem

(Parte 1 de 2)

Alfabetos e Linguagens

Alfabeto conjunto finito não vazio de símbolos símbolo é um elemento qualquer de um alfabeto usualmente designado por Σ exemplos: Σ = {a,b} Σ = {0,1,2,3,4,5,6,7,8,9}

Cadeia (string, palavra) concatenação de símbolos de um alfabeto Σ exemplos: aab , 123094 cadeia vazia: não contém nenhum símbolo, anotada com ε

Comprimento de cadeia número de símbolos de uma cadeia. exemplos: |aab| = 3 , |123094|=6 , |ε|=0

formando a cadeia xy. Obs:|z| = |x| + |y|

Concatenação de cadeias define-se a concatenação z de uma cadeia x com uma cadeia y, como sendo a concatenação dos símbolos de ambas as cadeias, exemplo: x = abaa; y = ba ⇒ z = abaaba x = ba; y = ε ⇒ z = ba

Potências de um alfabeto

Denotamos Σk o conjunto de todas as palavras de comprimento k, sobre o alfabeto Σ. Exemplos, para o alfabeto Σ = {0, 1} :

Σ0 = { ε } Σ1 = {0, 1} Σ2 = {0, 01, 10, 1} Σ3 = {0, 001, 010, 011, 100, 101, 110, 1}

Fechamento de um Alfabeto

Fecho transitivo e reflexivo: Σ*

Σ* = Σ0∪ Σ1∪ Σ2∪ Σ3

É o conjunto de todas as palavras sobre o alfabeto Σ

Σ+ = Σ1∪ Σ2∪ Σ3

Fecho transitivo é obtido excluindo a palavra vazia: Σ+ Σ* = Σ+∪ { ε }

Σ* = { ε, 0, 1, 0, 01, 10, 1,}
Σ+ = {0, 1, 0, 01, 10, 1,}

Para o alfabeto Σ = {0, 1}

Linguagem

Coleção de cadeias de símbolos, de comprimento finito. Estas cadeias são denominadas sentenças da linguagem, e são formadas pela justaposição de elementos individuais, os símbolos ou átomos da linguagem. Exemplos: {ab, bc} ( linguagem formada pelas cadeias ab e bc)

por exemplo a, ab, abb, b, aab, aaab,)

{abn, anb; n ≥ 0} ( linguagem formada por todas as cadeias que começam com a seguido de um número qualquer de b's ou começam com um número qualquer de a's seguidos de um b,

Mecanismos de Representação de Linguagens

• enumeração das cadeias de símbolos que formam as suas sentenças (somente linguagens finitas podem ser representadas por este método)

• conjunto de leis de formação das cadeias: Gramática

• regras de aceitação de cadeias: Reconhecedor Exemplos:

• enumeração L = {a, b, ab, ba} ( linguagem formada pelas cadeias a, b, ab e ba)

• leis de formação – gramática G

B → ε} gera L(G) = {0n1m, n ≥ 1 m ≥ 0}

G = ( {A, B}, {0, 1}, P, A) P: { A → 0A A → B B → 1B

deverá verificar se a palavra começa com a ou b e se tiver mais um símbolo deverá terminar com b

• regras de aceitação – um reconhecedor para a linguagem L acima ou a, respectivamente e, também não poderá ter mais símbolos caso pertença a linguagem L.

No contexto da Teoria das Linguagens Formais e Autômatos:

Problema: dados um alfabeto Σ e uma linguagem L sobre Σ, decidir se uma dada palavra w∈Σ pertence ou não a L.

• Concatenação usualmente denotamos L1 · L2 como L1L2 . as linguagens não precisam ser sobre o mesmo alfabeto

se L1 ∈ Σ1 e L2 ∈ Σ2 , teremos L1L2 ∈ Σ1 ∪ Σ2

para qualquer linguagem L: L{ε} = {ε}L = L a linguagem que contêm somente a cadeia vazia atua como elemento neutro para a operação de concatenação.

Exemplos: considere Σ = {0, 1} e as linguagens sobre Σ: L1 = {ε, 1, 010, 1010} e L2 = {ε, 0, 1, 10, 1}.

então: L1 ∪ L2 = {ε, 0, 1, 10, 1, 010, 1010}

L1 ∩ L2 = {ε, 1} L1 - L2 = {0110, 11010}

• Potenciação

Se L ∈ Σ, definimos Ln = {ε} se n = 0, e Ln = L · Ln-1 para n > 0. Exemplo: para L = {xy}, temos L0 = {ε}, L1 = L = {xy}, L2 = L = {xyxy}. Obs: ∅0 = {ε}

• Sub - linguagem se todas as cadeias de L1 são também cadeias de L2, então L1 é definida como uma sub-linguagem de L2 , ou seja, L1 ⊆ L2 exemplo: se L1 = {1, 1, 11, 11} e L2 = {1n | n ≥ 4} temos que L1 ⊆ L2.

Note que qualquer linguagem L sobre um alfabeto Σ é uma sub-linguagem de Σ*, isto é, L ⊆ Σ*.

o transitivo ou positivo :U∞=+=

iLL o transitivo e reflexivo ou fecho de Kleene : U∞== 0i iLL* o fecho de Kleene consiste de zero ou mais concatenações de L, enquanto o fecho positivo corresponde a uma ou mais concatenações

Exemplo suponha L = {1} sobre o alfabeto Σ = { 0, 1 }. Temos

L* = {ε, 1, 12, 13,} e também L+ = { 1, 12, 13, ...}

L0 = {ε}, L1 = {1}, L2 = {12} assim

L1(L2 ∪ L3) = L1L2 ∪ L1L3e (L2 ∪ L3)L1 = L2L1 ∪ L3L1

Para as linguagens L1 , L2 e L3 sobre um mesmo alfabeto Σ:

A concatenação não interage com a intersecção da mesma forma que a união. Para ilustrar, considere que L1 = {ε, 1}, L2 = {ε} e L3 = {1}

Por outro lado, L2 ∩ L3 = ∅ e assim L1(L2 ∩ L3) = ∅ A concatenação e a diferença de linguagens também são incompatíveis.

Gramáticas

• dispositivos de geração de sentenças das linguagens que definem • caracterizadas como quádruplas ordenadas: G = (V, Σ, P, S), onde:

predicado,, verbo; e em linguagem de programação - programa, bloco de comandos,

V: é um alfabeto finito, conhecido como vocabulário não – terminal. Os símbolos de V são usados como nomes para categorias sintáticas. Temos como exemplo: em Português – sentença, procedimentos, etc.

Σ: é um alfabeto finito conhecido como vocabulário terminal. Os símbolos de Σ são aqueles que aparecem nos programas de uma linguagem de programação, ou em palavras na linguagem natural como o Português.

P: é um conjunto finito de regras ou produções da forma W → W' onde: W ∈ (V ∪ Σ)+, isto é o conjunto de cadeias não vazias sobre V e Σ e W'∈ (V ∪ Σ)*. A interpretação da regra W → W' é que W pode ser substituído por W' sempre que W aparecer. S: é o símbolo inicial , ou o axioma, da gramática. S é o nome da categoria sintática principal.

Como exemplo em Português: S = sentença. Obs.:

ƒ os elementos de Σ, são os terminais e representados por letras minúsculas a, b, c,
ƒ os elementos de V são os não – terminais e representados por letras maiúsculas A, B, C,

V ∩ Σ = ∅; V ∪ Σ = T, um conjunto com todos os símbolos terminais e não-terminais; cadeias mistas, ou seja cadeias C ∈ (V ∪ Σ)* são representadas por letras gregas α, β, ...

As gramáticas devem ser vistas como sistemas de substituição, nos quais as produções indicam as substituições possíveis para os não terminais.

Exemplos:

(Parte 1 de 2)

Comentários