1.3 Linguagens x problemas de decisão

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.

Operações e Relações entre Cadeias

Sejam 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

Vamos 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