1.2 Alfabeto, cadeias e linguagens

Nesta aula, apresentamos alguns conceitos básicos usados no restante do curso. Em especial,

vamos falar de alfabeto, cadeia e linguagem.

1.2.1 Definições

Seguem as definições dos conceitos:

Alfabeto: é conjunto finito não-vazio qualquer

• Símbolo: nome que se dá aos elementos do alfabeto
• Representaremos por letras gregas maiúsculas (veja o apêndice)
• Exemplos:

Σ1 = { a, b, c, ..., z }

Σ2 = { 0 , 1}

Γ1 = { a, b, c }

Γ2 = { 0, *, 5, +, = }

Cadeia ou Palavra1

(): é uma seqüência finita (uma tupla) de símbolos do alfabeto.

• Vamos representar sem uso de delimitadores (como vírgula ou parênteses)
• Exemplos de cadeias no alfabeto Σ1: “casa”, “faculdade”, “ensino”, “nseakjf,” “odt-nudg”, “aaa”, “b”, etc.
  • Apenas para destacar que são tuplas, poderíamos também representá-las assim,

com a notação padrão de tuplas: (c,a,s,a), (f,a,c,u,l,d,a,d,e), etc.

• Exemplos de cadeias no alfabeto Σ2: “000011”, “1”, “010”, “1000”, etc.
• Exemplos de cadeias no alfabeto Γ2: “55”, “+0”, “5=**0”, “=+=”, “0+5+0=5”,

“50=5++05”, etc.

Cadeia vazia: é uma sequência especial sem símbolos, representada como ε

Em inglês é String. Para fins didáticos, ale a pena comparar com strings de linguagens de programação.

• Pode ser formada de qualquer alfabeto
• Ela é como uma 0-tupla ( )
• Comparando com elementos de programação, ela é similar a uma string “” ou a uma lis-

ta vazia [ ]

O conjunto de todas as cadeias de um alfabeto Σ é representado como Σ*

• É sempre um conjunto infinito
• Sempre inclui a cadeia vazia ε
• Exemplos (baseados nos alfabetos dados antes):

Σ2

*

= { ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ... }

Γ1

*

= { ε, a, b, c, aa, ab, ac, ba, bb, bc, aaa, aab, aac, ... }

Linguagem (sobre um alfabeto Σ): é um conjunto de cadeias do alfabeto

• Em outras palavras: é um subconjunto de Σ
• Vamos representar com a letra L acrescido de algum sufixo ou com nomes com letras

maiúsculas

• Exemplo de linguagens finitas sobre o alfabeto Σ2:

LA = { 0, 010, 1, ε }

LB = { ε }

• Exemplo de linguagem vazia sobre o alfabeto Σ2:

LC = { } = ∅

• Exemplo de linguagens infinitas sobre o alfabeto Σ2:

LD = { w | w inicia com o símbolo 0 } = { 0, 00, 01, 000, 001, 010, ...}

LE = { w | w tem um número par de 1s } = { ε, 0, 00, 110, 101, 011, ...}

• Observe que, para representar linguagens infinitas, nós podemos descrever uma propri-

edade geral que as cadeias dela apresentam. Vamos fazer isso com freqüência nesta dis-

ciplina. Por exemplo:

• A linguagem LD acima pode ser descrita simplesmente como “as cadeias que iniciam com 0”.
• A linguagem LE acima pode ser descrita como “as cadeias que têm um número par de 1s”.
• No fundo, essa tal propriedade representa justamente um problema de decisão. Veja a seção a seguir.

1.2.2 Linguagens x Problemas de Decisão

M, brevemente, que existe uma correspondência entre o conceito de linguagem (visto nesta

aula) e o conceito de problema de decisão (problema computacional com saídas sim/ não).

(1) Dada uma linguagem L, podemos descrever um problema de decisão equivalente:

• •O problema de decidir se uma cadeia w qualquer é ou não da linguagem L.
• Isso pode ser feito verificando se a cadeia tem a propriedade descrita na definição da

linguagem.

Exemplo: Dada a linguagem das cadeias que começam com “a” e terminam com “b”, temos o

problema de decisão de “testar se uma cadeia começa com a e termina com b”.

(2) Dado um problema de decisão, podemos descrever uma linguagem associada a ele:

• A linguagem (conjunto) das cadeias para as quais o problema responde “sim”.

Exemplo: Dado o problema de decisão de testar se um número (representado como cadeia) é

par, temos a linguagem (conjunto) das cadeias que representam números pares.

Por conta desta correspondência entre os dois conceitos, vamos tratar de linguagens e proble-

mas de decisão como equivalentes.

Fonte: https://classroom.google.com/u/0/c/NTM1NDgwNjAwNzYz/a/NTM1NDgwNjAwNzky/details