1.3 Linguagens x problemas de decisão
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.
Operações e Relações entre Cadeias
editarSejam v e w duas cadeias quaisquer.
- Tamanho ou comprimento de w : | w |
- Quantidade de símbolos da cadeia, contando também as repetições.
- O tamanho da cadeia vazia é zero.
- Exemplos:
|01| = 2
|aaa| = 3
|ε| = 0
- Reverso de w : w^R
- Seqüência de símbolos de w invertida
- Exemplos:
(abc)R = cba
(0110)R = 0110
ε^R = ε
a^R = a
- Concatenação de v com w : v.w ou vw
- É a cadeia formada tomando a sequência de símbolos de v e acrescentando ao final dela a seqüência de símbolos de w
- Exemplos:
ara.caju = aracaju
ab.db = abdb
01.ε = 01
0.ε.1 = 01
ε.ε.ε = ε
Observação: veja que a concatenação de uma cadeia com ε (cadeia vazia) dá sempre
a própria cadeia
- Concatenação sucessiva n vezes de w: w^n
- É a cadeia concatenada consigo mesma n vezes:
- w^n = wwww...w (n vezes)
- Se n for zero, o resultado é sempre a cadeia vazia ε
- Exemplos:
a^3 = aaa
(ab)4 = abababab
ab4 = abbbb
a^1= a
(xyz)^0 = ε
ε^0 = ε
- Subcadeia de w:
- É qualquer cadeia formada tornando-se uma parte contígua ("tudo junto") da sequência de simbolos de w, sem alterar a ordem dos símbolos
- Casos especiais:
- A cadeia vazia ε é subcadeia de qualquer cadeia
- Uma cadeia é sempre subcadeia de si mesma
- Exemplos de subcadeias de "entrementes":
- entre, treme, re, reme, mentes, entes, es, ε, entrementes, etc.
- Exemplos de subcadeias de "abbaaaccc":
- ab, ε,abb,bba,aa,aaa,ac,acc,ccc,abbaaaccc,etc.
Apêndice – Letras Gregas
editarVamos usar algumas letras gregas para representar alfabetos, cadeias, funções e outros conceitos
do assunto. Coloquei neste apêndice os nomes das principais letras gregas que usaremos. Con-
subltem quando precisarem.
Minúsculas:
α – alfa (corresponde à nossa letra A)
β – beta (corresponde ao B)
γ – gama (corresponde ao G, com som “guê”)
δ – delta (corresponde ao D)
ε – épsilon (corresponde ao E)
λ – lambda (corresponde ao L)
Maiúsculas:
Σ – sigma (corresponde ao S)
Γ – gama