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
editarSeguem 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
editarM, 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