1.3 Linguagens x problemas de decisão

Linguagens x Problemas de Decisão

editar

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

editar

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

editar

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