Estudo Dirigido Ling Formais Autom Comput

Prévia do material em texto

Prof. Dr. Boente, Alfredo (PhD)
COMPUTAÇÃO
Linguagens Formais, Autômatos e 
Computabilidade
COMPUTAÇÃO
Bibliografia Recomendada
COMPUTAÇÃO
UNIDADE 1:
Programas, Máquinas, 
Computação e Função 
Computada
COMPUTAÇÃO
Introdução
O perfeito entendimento acerca dos principais pontos que
cercam a teoria da computação, perfaz um cientista da
computação com ideias e atitudes mais eficientes e eficazes,
quando está em busca de uma solução ótima (S*) para certo
problemas de computação.
Na aula de hoje iremos compreender melhor a relação
existente entre programas, máquinas, computação e função
computada.
COMPUTAÇÃO
Programas
Os programas são sequências finitas de passos que foram
definidas por um programador para alcançar um objetivo
específico.
Os programas...
- expressam um algoritmo lógico computacional
- representado por um conjunto de operações e testes
compostos de diversas estruturas lógicas
- é classificado como MONOLÍTICO, ITERATIVO
ou RECURSIVO
COMPUTAÇÃO
Programas
Um programa monolítico é estruturado, usando desvios
condicionais e incondicionais, não fazendo uso explícito de
mecanismos auxiliares de programação. A lógica é distribuída
por todo o bloco (monólito) que constitui o programa.
COMPUTAÇÃO
Programas
Exemplo de
programa monolítico
COMPUTAÇÃO
Programas
Os programas iterativos são baseados em três mecanismos de
composição (sequenciais) de programas, os quais podem ser
encontrados em um grande número de linguagens de alto
nível: sequencial, condicional e repetitivo.
COMPUTAÇÃO
Programas
Exemplo de programa iterativo
COMPUTAÇÃO
Programas
O programa recursivo é baseado em sub-rotinas recursivas, ou
seja, ele faz chamada a si mesmo.
COMPUTAÇÃO
Programas
Exemplo de programa recursivo
Algoritmo Fatorial
Variável
numero : inteiro
Função fat (n : inteiro) : inteiro
Início
Se n = 0
Então retorne 1
Senão retorne n * fat (n – 1) Declaração da
Fim-Se Função Recursiva
Fim_fat
COMPUTAÇÃO
Programas
Início
Escreva(“Digite um número:”)
Leia (numero)
Escreva (“O fatorial de “, numero, “ é “, fat (numero))
Fim
Realiza a chamada da função recursiva
COMPUTAÇÃO
Máquinas
As máquinas interpretam os programas de acordo com os
dados fornecidos desde que possua uma interpretação para
cada operação ou teste que constitui o programa.
São classificadas como simples ou poderosas (complexas).
As máquinas possuem aplicações práticas restritas devido ao
fato das informações de saída serem limitadas a lógica binária
Aceitar/Rejeitar.
COMPUTAÇÃO
Máquinas
As máquinas podem representar:
- Um computador (hardware)
- Uma modelagem computacional
- Uma estruturação de modelo físico com
modelo lógico (robô, androides etc.)
COMPUTAÇÃO
Programa para uma Máquina
Sejam: M = (V, X, Y, πX, πY, ΠF, ΠT) uma máquina
P um programa onde PF e PT são os conjuntos de
identificadores de operações e de testes de P,
respectivamente.
P é um Programa para a Máquina M se, e somente, se:
• para qualquer F ∈ PF, existe uma única função
πF:V→V em ΠF;
• para qualquer T ∈ PT, existe uma única função
πT: V→ {verdadeiro, falso} em ΠT.
COMPUTAÇÃO
Computação e Função Computada
A computação representa a aplicação de um modelo
matemático que consiga expressar algo realmente
computável.
Representa historicamente o funcionamento da máquina para
o programa considerando um valor inicial.
Uma função é uma relação na qual cada elemento do domínio
está relacionado, com no máximo, um elemento de cada co-
domínio.
COMPUTAÇÃO
Computação e Função Computada
Faz-se relação com as funções parciais representada por f  A
x B e denotada por
f : A → B
Essa função sendo computada pode assumir os estados de
função Injetora (monomorfismo), Sobrejetora (epimorfismo)
ou Bijetora (isomorfismo).
Elas são aplicadas ao estudo da lógica da Teoria da
Computação aplicada às máquinas, através do uso de
Autômatos.
COMPUTAÇÃO
Computação e Função Computada
Função Injetora (monomorfismo): Uma função injetora,
também chamada de função injetiva, é aquela em que cada
elemento da imagem está ligado a um único elemento
do domínio.
A ilustração do diagrama a seguir, mostra o comportamento da
função f(x)=2x, em que o domínio é o conjunto dos números
naturais menores que 4, e o contradomínio é o conjunto dos
naturais menores que 9.
COMPUTAÇÃO
Computação e Função Computada
Observe que nenhuma das flechas liga um elemento
do conjunto B a dois elementos do conjunto A.
COMPUTAÇÃO
Computação e Função Computada
Isso é possível nas funções, como é o caso da função f(x)=x2,
na qual f(2)=f(–2)=4, ou seja, em que há elementos de B
relacionados a dois elementos distintos em A.
Logo, a função f(x)=2x, no domínio e contradomínio definidos,
é injetora. Vale ressaltar que uma função pode ter dois
elementos distintos de A ligados a um único elemento de B,
mas o contrário não é possível pela definição de função.
Portanto, o conceito mais fundamental de função injetora é:
qualquer elemento que pertence à imagem de uma função
injetora está relacionado a um único elemento de seu
domínio.
COMPUTAÇÃO
Computação e Função Computada
Função Sobrejetora (epimorfismo): Uma função é sobrejetora
quando seu contradomínio e imagem são o mesmo conjunto.
Em outras palavras, uma função é sobrejetora quando todos os
elementos do contradomínio estão relacionados a, pelo menos,
um elemento do domínio.
A ilustração do diagrama a seguir, representa uma função na
qual a imagem e o contradomínio são iguais.
COMPUTAÇÃO
Computação e Função Computada
Esse diagrama realmente representa uma função, pois cada
elemento do primeiro conjunto está relacionado a um único
elemento do segundo.
COMPUTAÇÃO
Computação e Função Computada
Observe também que essa função é sobrejetora, já que
o contradomínio (ou seja, o segundo conjunto) é igual à
imagem da função.
A imagem de uma função é o conjunto dos elementos
do contradomínio que estão ligados a algum elemento do
domínio.
Dessa forma, as funções sobrejetoras também podem ser
compreendidas como aquelas nas quais não “sobram”
elementos no contradomínio.
COMPUTAÇÃO
Computação e Função Computada
Função Bijetora (isomorfismo): A função bijetora, também
chamada de bijetiva, é um tipo de função matemática que
relaciona elementos de duas funções.
Desse modo, os elementos de uma função A possuem
correspondentes em uma função B.
É importante notar que elas apresentam o mesmo número de
elementos em seus conjuntos, conforme ilustrado na próxima
figura a seguir.
COMPUTAÇÃO
Computação e Função Computada
A partir desse diagrama, podemos concluir que:
O domínio dessa função é o conjunto {1, 2, 3, 4}.
COMPUTAÇÃO
Computação e Função Computada
O contradomínio reúne os elementos: {1, 3, 5, 7}.
O conjunto imagem da função é definido por:
Im(f)={1, 3, 5, 7}
A função bijetora recebe esse nome pois ela é injetora e
sobrejetora ao mesmo tempo.
Portanto, uma função f:A→B é bijetora quando f é injetora e
sobrejetora, também.
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Tanto os programas quanto máquinas usam algoritmos para a
interpretação e execução de certa função para alcançar ou
superar as expectativas de uma dada solução.
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Sua real equivalência consiste em:
Programas equivalentes fortemente
Programas equivalentes
Máquinas equivalentes
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Relação Equivalência Forte de Programas
Um par de programas pertence à relação se as
correspondentes funções computadas coincidem para qualquer
máquina.
Relação Equivalência de Programas em uma Máquina
Um par de programas pertence à relação se as
correspondentes funções computadas coincidem para uma
dada máquina.
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Relação Equivalência de Máquinas
Um par de máquina pertence à relação se as máquinas podem
se simular mutuamente. A simulação de uma máquina por
outra pode ser feita usando programas diferentes.A Relação Equivalência Forte de Programas é especialmente
importante pois, ao agrupar diferentes programas em classes
de equivalências de programas cujas funções coincidem,
fornece subsídios para analisar propriedades de
programas como complexidade estrutural.
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Um importante resultado é que programas recursivos são mais
gerais que os monolíticos, os quais, por sua vez, são mais
gerais que os iterativos.
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Exemplo de equivalência de programas:
COMPUTAÇÃO
Equivalência de Programas e Máquinas
Exemplo de equivalência de máquinas:
COMPUTAÇÃO
UNIDADE 2:
Máquinas Universais
COMPUTAÇÃO
Introdução
Uma máquina de estados finita ou autômato finito é um
modelo matemático usado para representar programas de
computadores ou circuitos lógicos.
O conceito é concebido como uma máquina abstrata que deve
estar em um de um número finito de estados. A máquina está
em apenas um estado por vez, este estado é chamado
de estado atual.
Um estado armazena informações sobre o passado, isto é, ele
reflete as mudanças desde a entrada num estado, no início do
sistema, até o momento presente.
COMPUTAÇÃO
Introdução
Uma transição indica uma mudança de estado e é descrita por
uma condição que precisa ser realizada para que a transição
ocorra.
No caso da transição quando é realizada no mesmo estado
atual, dizemos ter uma recursão, ou seja, uma transição ou
chamada recursiva.
Uma ação é a descrição de uma atividade que deve ser
realizada num determinado momento.
COMPUTAÇÃO
Máquinas Universais
- Hipótese de Church (1936) por Alonzo Church;
- Máquina de Turing (1936) por Alan Turing;
- Máquina de Post (1943) Emil Post;
- Máquina de Mealy (1955) George Mealy;
- Máquina de Moore (1956) Edward Moore;
- Máquina de Norma (1976) Richard Bird;
COMPUTAÇÃO
Tese de Church
A Tese ou Hipótese de Church foi apresentada por Alonzo
Church em 1936.
Church afirma que qualquer função computável pode ser
processada por uma Máquina de Turing. Essa MT apresenta um
algoritmo expresso na forma de interpretação dessa máquina,
capaz de processar a função computável.
Como a noção intuitiva de algoritmo não é matematicamente
precisa, é impossível formalizar uma demonstração de que a
MT é, efetivamente, o mais genérico dispositivo de
computação.
COMPUTAÇÃO
Tese de Church
Todas as evidências internas e externas imaginadas foram
sempre verificadas, reforçando a Hipótese de Church.
Os demais modelos de máquinas propostos, bem como
qualquer extensão de suas capacidades, possuem, no máximo,
a mesma capacidade computacional da Máquina Turing.
Baseado nisso, Alan Mathison Turing (1936) propôs um
formalismo para a representação de procedimentos efetivos
(identificação de programas escritos para uma “máquina
computacional autômata”, como noções intuitivas de
efetividade, o que mais tarde acenderia a chama da
computabilidade efetiva). Esse formalismo era representado
por uma Máquina de Turing (MT).
COMPUTAÇÃO
Tese de Church
Assim, a hipótese de Church (1936) diz:
A capacidade de computação representada pela 
Máquina de Turing é o limite máximo que pode ser atingido 
por qualquer dispositivo de computação
Alonzo Church
COMPUTAÇÃO
Tese de Church
Tal capacidade computacional é requerida nos modelos
matemáticos desenvolvidos com objetivo de gerar modelos
computacionais, baseados na lógica matemática, visando
alcançar ou superar as expectativas de seus contratantes.
Portanto, torna-se necessário uma sessão prática da lógica
matemática aplicada a teoria da computação para
solucionabilidade de problemas através dos chamados de
Métodos de Provas.
COMPUTAÇÃO
Máquina de Turing
A máquina de Turing é uma máquina universal que apresenta
um controle finito, com todas as máquinas universais
existentes, e uma fita, que pode servir como dispositivo de
entrada, como área de trabalho ou como dispositivo de saída.
Inventada por Allan Mathison Turing em 1936.
Por convenção a fita é finita podendo ser aumentada sempre
que houver necessidade de mais espaço, com mais de uma
célula em branco.
COMPUTAÇÃO
Máquina de Turing
De acordo com a tese de Church, detalhes de funcionamento
da máquina de Turing (MT) são determinantes e influenciam
em sua capacidade de computação.
COMPUTAÇÃO
Máquina de Turing
A MT é uma oito-upla representada por M=(, Q, , q0, F, V,
, ☼), onde:
 é o alfabeto de símbolos de entrada
Q é o conjunto de estados possíveis da MT
 é o programa ou função de transição (função parcial - : Q 
× (Σ  V  { ß, ☼}) → Q × (Σ  V  { ß, ☼ }) × { E, D })
q0 é o estado inicial da máquina tal que q0 é elemento de Q
F é o conjunto de estados finais tal que F está contido em Q
V é o alfabeto auxiliar
 é o símbolo especial branco
☼ é símbolo especial de marcador de início da fita
COMPUTAÇÃO
Máquina de Turing
O programa poder ser representado por um grafo finito (p,
au)= (q, av, m)
COMPUTAÇÃO
Máquina de Turing
O programa também pode ser representado por meio de uma
tabela de transição, conforme figura abaixo para (p, au)= (q,
av, m) :
COMPUTAÇÃO
Máquina de Turing
O processamento de uma Máquina de Turing M=(Σ,Q,  , q0, F,
V, ß, ☼) para uma palavra de entrada w consiste na sucessiva
aplicação da função programa, a partir do estado inicial q0 e
da cabeça posicionada na célula mais à esquerda da fita até
ocorrer uma condição de parada.
O processamento de M para a entrada w pode parar ou ficar
em loop infinito.
A parada pode ser de duas maneiras: aceitando ou rejeitando
a entrada w.
COMPUTAÇÃO
Máquina de Turing
As condições de parada são as seguintes:
 Estado Final: A máquina assume um estado final: a
máquina pára, e a palavra de entrada é aceita;
 Função Indefinida: A função programa é indefinida para
o argumento (símbolo lido e estado corrente): a máquina
pára, e a palavra de entrada é rejeitada;
 Movimento Inválido: O argumento corrente da função
programa define um movimento à esquerda e a cabeça da
fita já se encontra na célula mais à esquerda: a máquina
pára, e a palavra de entrada é rejeitada.
COMPUTAÇÃO
Máquina de Turing
Uma das abordagens do estudo das Máquinas de Turing ou das
Máquinas Universais em geral é como reconhecedores de
linguagens, ou seja, dispositivos capazes de determinar se uma
dada palavra sobre o alfabeto de entrada pertence ou não a
certa linguagem.
A Linguagem Aceita por uma Máquina de Turing procede da
seguinte forma:
Seja M = (Σ, Q,  , q0, F, V, ß, ☼) uma Máquina de Turing.
Então:
COMPUTAÇÃO
Máquina de Turing
a) A linguagem aceita por M, denotada por ACEITA(M) ou L(M),
é o conjunto de todas as palavras pertencentes a Σ* aceitas
por M, ou seja:
ACEITA(M)={w|M ao processar wΣ*, pára em um estado qfF}
b) A linguagem rejeitada por M, denotada por REJEITA(M), é o
conjunto de todas as palavras de Σ* rejeitadas por M, ou seja:
REJEITA(M) = {w|M ao processar wΣ*, pára em um estado
qF}
c) A linguagem para a qual M fica em loop infinito, denotada
por LOOP(M) é conjunto de todas as palavras de Σ* para as
quais M fica processando indefinidamente.
COMPUTAÇÃO
Máquina de Turing
Assim, as seguintes afirmações são verdadeiras:
ACEITA(M)  REJEITA(M) = 
ACEITA(M)  LOOP(M) = 
REJEITA(M)  LOOP(M) = 
ACEITA(M)  REJEITA(M)  LOOP(M) = 
ACEITA(M)  REJEITA(M)  LOOP(M) = Σ*
Consequentemente, o complemento de:
ACEITA(M) é REJEITA(M)  LOOP(M)
REJEITA(M) é ACEITA(M)  LOOP(M)
LOOP(M) é ACEITA(M)  REJEITA(M)
COMPUTAÇÃO
Máquina de Turing
Ex: MT para o problema de Duplo Balanceamento:
COMPUTAÇÃO
Máquina de Turing
Representando a MT através da
tabela de transição para o
problema apresentado
(Duplo Balanceamento):
COMPUTAÇÃO
Máquina de Turing
A Máquina de Turing
Alan Turing
COMPUTAÇÃO
Máquina de Post
O conceito de computador abstrato de Post é simples. Foi
apresentado por Emil Leon Post em 1943.
O computador ou máquina de Post permite formular tudo
aquilo que é passível deser computado.
A máquina de Post (MP) apresenta o estado “ativo” ou
“inativo” de cada neurônio (0 ou 1, na linguagem do
computador de Post) que forma a base dos processos do
pensamento humano e que é responsável pelo nosso
comportamento.
COMPUTAÇÃO
Máquina de Post
Exemplo da Máquina de Post:
Emil Leon Post
COMPUTAÇÃO
Máquina de Post
A principal característica da Máquina de Post é que usa
estrutura de dados do tipo fila para entrada, saída e memória
de trabalho.
Estruturalmente, a principal característica de uma fila é que o
primeiro valor gravado é também o primeiro a ser lido (FIFO).
COMPUTAÇÃO
Máquina de Mealy
Uma máquina de Mealy é uma máquina de estado finito que
produz um resultado (saída de dados) baseando-se no estado
em que se encontra e na entrada de dados. Inventada por
George H. Mealy em 1955.
Assim, o diagrama de estado irá incluir tanto o sinal de
entrada como o de saída para cada vértice de transição.
Em contraste, a saída de uma máquina de Moore depende
apenas do estado atual da máquina, sendo que as transições
não possuem qualquer sinal em anexo.
COMPUTAÇÃO
Máquina de Mealy
Mesmo assim, por cada máquina de Mealy existe uma máquina
de Moore equivalente cujos estados consistem na união dos
estados da máquina de Mealy e o produto cartesiano dos
estados da máquina de Mealy com o alfabeto de entrada de
sinais.
COMPUTAÇÃO
Máquina de Mealy
Exemplo da Máquina de Mealy:
George H. Mealy
COMPUTAÇÃO
Máquina de Moore
Uma máquina de Moore é uma máquina de estado finita cujos
valores de saída são determinados somente pelo estado atual.
Inventada por Edward F. Moore em 1956.
A máquina de Moore é diferente de uma máquina de Mealy,
cujos valores de saída são determinados tanto pelo estado
atual quanto por suas entradas.
COMPUTAÇÃO
Máquina de Moore
Exemplo da Máquina de Moore:
Edward F. Moore
COMPUTAÇÃO
Máquina de Norma
O nome da máquina universal Norma vem de Number
TheOretic Register MAchine (NORMA). Foi proposta por
Richard S. Bird em 1976.
Apresenta um conjunto de registradores naturais associados a
três instruções:
- Operação de incremento a um (adição)
- Operação de decremento a um (subtração)
- Teste coexistente para verificar se o valor
armazenado é igual a zero
COMPUTAÇÃO
Máquina de Norma
Sabe-se que N o conjunto de todas as uplas (conjunto de
valores advindos de uma função).
Para evitar subscritos os componentes das uplas são denotados
por letras maiúsculas, as quais denotam os registradores da
máquina de Norma.
Ela é uma sete-upla. Dessa forma, suponha que K seja um
registrador, K  {A, B, X, Y, ...} :
Norma = (N, N, N, ent, sai, {addK, subK}, {zeroK})
COMPUTAÇÃO
Máquina de Norma
A máquina de Norma simula características de máquinas reais
como: operações, testes, valores numéricos, dados
estruturados, endereçamento indireto, recursão e cadeia de
caracteres.
Exemplo do uso da máquina de Norma para atribuir o valor
zero a um registrador A:
Programa Iterativo
A  0
: até A=0
faça (AA-1)
COMPUTAÇÃO
Máquina de Norma
Exemplo da máquina de Norma
Richard S. Bird
COMPUTAÇÃO
UNIDADE 3:
Linguagem Lambida
COMPUTAÇÃO
Introdução
Linguagem lambida ou lambida linguagem é uma
representação notacional utilizada na teoria da computação,
através do estudo das linguagens formais, autômatos e
Computabilidade.
Introduzida por Church, permeou o trabalho com o cálculo
lambida com o principal objetivo de evitar ou minimizar as
denominadas ambiguidades de notação adotadas na teoria da
computação.
COMPUTAÇÃO
 - Linguagem
É apresentada a notação conhecida como Linguagem Lambda
(λ-Linguagem), introduzida por Alonzo Church em 1941, no
Cálculo Lambda (λ-Cálculo), cujo principal objetivo é evitar
ambiguidades de notação.
O λ-cálculo é um ramo da lógica matemática que sustenta
desenvolvimentos importantes na teoria das linguagem de
programação, tais como:
- estudo de questões fundamentais da computação;
- design de linguagens de programação;
- semântica das linguagens de programação;
- arquitetura de computadores;
- modelagem de autômatos.
COMPUTAÇÃO
 - Linguagem
O λ-cálculo é universal no sentido de que qualquer função
computável pode ser expressa e avaliada usando esses
formalismo. Isto é equivalente para Máquina de Turing.
O λ-cálculo enfatiza o uso de regras de transformação e não se
importa em relação a implementação em uma máquina real.
Esta é uma abordagem mais relativa ao software do que ao
hardware propriamente dito.
Chamada de menor linguagem universal do mundo.
COMPUTAÇÃO
 - Linguagem
O λ-cálculo pode ser considerado como uma linguagem de
programação abstrata: funções podem ser combinadas para
formar outras funções.
É uma linguagem sem complicações sintáticas. Refere-se a
uma maneira de formalizar o conceito de computabilidade
efetiva.
Alonzo Church (1936) inventou o cálculo lambda e definiu a
noção de função computacional através deste sistema.
Enquanto isso, Alan Turing (1936) inventou uma classe de
máquinas (conhecida mais tarde como Máquinas de Turing) e
definiu a noção de função computacional através dessas
máquinas.
COMPUTAÇÃO
 - Linguagem
Ainda em 1936, Alan Turing provou que ambos os modelos são
igualmente fortes no sentido que elas definem a mesma classe
de funções computáveis.
Em 1941, Alonzo Church introduz a notação de λ-Linguagem.
Função: Correspondência biunívoca de membros de um
conjunto domínio com o conjunto imagem.
A λ-Linguagem fornece um meio de definir funções sem nome,
onde uma λ-expressão especifica o parâmetro e a
correspondência biunívoca de uma função.
COMPUTAÇÃO
 - Linguagem
Vejamos:
Possui duas construções básicas: 
Abstração: abstrai a definição da função.
Aplicação: determina o valor da função aplicada a um dado
parâmetro.
xxxxcubo =)(
xxxx .
8)2)(.( = xxxx
COMPUTAÇÃO
 - Linguagem
Identificando elementos:
x. x + a
escopo de x
local de ligação
ocorrência ligada
ocorrência livre
COMPUTAÇÃO
 - Linguagem
Variáveis Livres
A mesma variável pode aparecer como livre e ligada numa
única expressão.
(x.z x) (y.y x)
ligada livre
COMPUTAÇÃO
 - Linguagem
Linguagem Não-Tipada
A λ-Linguagem e LISP são linguagens não-tipadas:
- Programas x Dados: não distinguíveis.
A associação de tipo a um termo lambda é como uma definição
tradicional. Porém, a definição formal de termos lambda
tipada é omitida:
f(x)=x+4 f=λx.x+4 : N→N
f(x)=g(x2) f=λx.λx(x) : NxN
COMPUTAÇÃO
 - Linguagem
Linguagem Não-Tipada
Por ser “free-type” a λ-linguagem é útil para a simulação de
recursão, ou seja, aplicação junto às funções recursivas.
Considerando (F.A) onde a expressão F é um algoritmo, e a
expressão A um entrada, podemos ter a expressão (F.F), sendo
uma recursão de uma expressão chamando a si mesmo.
COMPUTAÇÃO
-redução
Corresponde ao conceito de substituição do parâmetro formal
de uma função por seu parâmetro real.
Permite a simplificação de expressões- sem alterar o seu
significado, enquanto houver uma redex (expressão reduzível).
() (x.P) Q → [Q/x] P
COMPUTAÇÃO
UNIDADE 4:
Funções Recursivas
COMPUTAÇÃO
Introdução
Inúmeros cientistas tiveram o propósito da buscar um
“procedimento mecânico” que justificasse as transformações
funcionais de números.
As funções recursivas mostram-se como um método eficiente
para se encontrar valores de uma função. Um exemplo clássico
disso é a escrita algorítmica da função FATORIAL.
Pode ser construída para simular numericamente as
computações de uma Máquina de Turing.
COMPUTAÇÃO
Funções Recursivas
Uma função recursiva (FR) é uma função que se refere a si
própria. Em toda a função recursiva, existem os componentes:
- Um passo básico (ou mais) cujo o resultado é imediatamente
conhecido;
- Um passo recursivo (ou mais) em que se tenta resolver um
subproblema do problema inicial;
- Geralmente possui expressão condicional;
- Sua execução consiste em ir resolvendo subproblemas mais
simples, até se atingir omais simples de todos (resultado
conhecido de imediato).
COMPUTAÇÃO
Funções Recursivas
Padrão comum para se escrever uma FR:
1. Testar os casos mais comuns
2. Fazer chamada(s) recursivas com subproblemas cada vez
mais próximo dos casos mais simples.
Nos problemas mais comuns, busca-se:
- Não detectar casos mais simples;
- Perda de desempenho a nível de implementação
computacional (tempo de resposta);
- Fazer a abstração necessária não é tão intuitivo.
COMPUTAÇÃO
Formalismo para Algoritmos
Na busca da formalização do conceito de formalismo utiliza-se
3 classificações:
Operacional: Define-se uma máquina abstrata, baseada em
estados, em instruções primitivas e na especificação de como
cada instrução modifica cada estado.
Exemplo: Formalismos tais como Máquina de Norma e MT.
COMPUTAÇÃO
Formalismo para Algoritmos
Axiomático: Associam-se regras às componentes da linguagem.
As regras permitem afirmar o que será verdadeiro após a
ocorrência de cada cláusula considerando o que era verdadeiro
antes da ocorrência.
Exemplo: Aqui temos a visão da gramática, e como esquema
de procedimento temos a Máquina de Post, por exemplo, sob
esta montagem de regra.
COMPUTAÇÃO
Formalismo para Algoritmos
Denotacional ou Funcional: Trata-se de uma função
construída a partir de funções elementares de forma
composicional no sentido em que o algoritmo denotado pela
função pode ser determinado em termos de suas funções
componentes.
Esta é a visão que será tratada neste estudo.
COMPUTAÇÃO
Funções Recursivas Parciais
Tipo de formalismo denotacional, introduzidas por Sephen
Kleene (1936). Kleene tinha o objetivo de formalizar a noção
intuitiva de função computável.
Verifica-se que a composição de três funções naturais simples:
Constante zero; Sucessor; Projeção.
Juntamente com as estratégias de recursão e
minimização, constituem uma forma compacta e
natural para definir muitas funções e capaz de
descrever toda e qualquer função intuitiva
computável.
Stephen Kleene
COMPUTAÇÃO
Funções Parciais e Total
Função Parcial: Dados dois conjuntos A e B. Dizemos que uma
função é parcial se f  AxB onde cada elemento do domínio
(conjunto A) está relacionado com, no máximo, um elemento
do contradomínio.
f  A x B é denotada por f: A → B
O tipo de f é A → B
(a,b)  f é denotado por f(a)=b
COMPUTAÇÃO
Funções Parciais e Total
Exemplo:
Sejam os conjuntos A={a, b, c}, B={3,5,7}, e as relações f, g de
A em B:
f={(a,2), (a,8)} Não é função parcial
g={(b,3), (c,3)} É função parcial
Se {x  A, y  B | f(x) = y} É função total
Então, com base no exemplo anterior:
g={(a,3), (b,5), (c,7)} É função total
COMPUTAÇÃO
Argumento da Função
Dadas as três funções parciais, onde as variáveis X e Y têm
seus valores em N.
f(x) = x3 + 4
g(x,y) = (x2, y-x)
h(f,x) = f(f(x))
A função f possui só um argumento, uma variável, portanto seu
tipo é:
f: N → N
A função g possui dois argumentos:
g: N x N → N x N ou N2 → N2
COMPUTAÇÃO
Argumento da Função
A função h é um exemplo de função que possui funções como
argumentos. Sendo composta pelo produto cartesiano do tipo
de f:
h: (N → N) x N → N
Tem-se o conceito de funcional, que é a função que possui
uma ou mais funções como argumentos.
Esse tipo ocorre com frequência em programação.
COMPUTAÇÃO
Argumento da Função
Considere um programa que receba como parâmetro um par
constituído por um arranjo A de números naturais e um
número natural n e que calcula o máximo entre...
A(1), A(2), ..., A(n)
Arranjo: A: N → N
Função: f: (A, n) = max {A(i) | 1  i  n}
Tipo: (N → N) x N → N
COMPUTAÇÃO
Hierarquia das Funções Recursivas
Todas as funções de números 
naturais
Funções recursivas 
primitivas
Funções recursivas 
Parciais que são totais
Funções recursivas 
Parciais
COMPUTAÇÃO
Função Computada
Então a função computada W, M é tal que, para qualquer x 
X:
W, M(x) = fY(x)
Cada função computável por Norma pode ser definida
recursivamente. A função recursiva fornece uma abordagem
(denotacional) diferente da operacional. A quase totalidade
das linguagens de programação modernas possui recursão
como um construtor básico de programas.
As arquiteturas da maioria dos atuais computadores possuem
facilidades para implementar recursão.
COMPUTAÇÃO
Princípio da Recursão
No princípio da recursão o problema como um todo e reduz-se
o problema a subproblemas menores, até que se chega a um
problema base, iniciando assim o processo reverso, com a
resolução de cada instância do problema.
COMPUTAÇÃO
Definições Recursivas de Bird
Considere a seguinte definição recursiva da função fatorial:
fatorial = λx.(x = 0 → 1, x• fatorial (x - 1))
fatorial(0) = 1.
fatorial(0) = (0 = 0 →1, 0•fatorial(0 - 1)) = 1
Observa-se que:
0•fatorial(0-1) não tem valor definido, pois fatorial(0-1) é
indefinido.
Como x=0 é verdadeira, a função tem valor igual a 1.
COMPUTAÇÃO
Definições Recursivas de Bird
Adição, Multiplicação e Potenciação
Considere as seguintes definições recursivas das funções
adição (adição), multiplicação (mult) e potenciação (pot):
adição = λ(x, y).(x = 0 → y, adição(x - 1, y) + 1)
mult = λ(x, y).(x = 0 → 0, adição( mult(x - 1, y), y) )
pot = λ(x, y).(y = 0 → 1, mult( pot(x, y - 1), x) )
Observa-se que:
A adição é definida em termos da função sucessor (sucessor=
λy.y+1);
A multiplicação é definida em termos de adições de y;
A potenciação é definida em termos de multiplicações de x.
COMPUTAÇÃO
Definições Recursivas de Bird
Divisão, Multiplicação
Considere a definição da função multiplicação mult,
juntamente com as definições recursivas das funções divisão
inteira (div) de x por y (indefinida para y = 0) e a
multiplicação (m) dessa por y:
div = λ(x, y).(x < y → 0, div(x - y, y) + 1)
m = λ(x, y).mult(y, div(x, y))
Entretanto, para y = 0, m(x,0) admite as seguintes
interpretações:
• m(x,0) = mult(0, div(x, 0)) = 0 e, portanto, é definida;
• m(x,0) = mult(0, div(x, 0)) é indefinida pois div(x, 0) é
indefinida.
COMPUTAÇÃO
Definições Recursivas de Bird
Portanto, o argumento (0, div(x, 0)) é indefinido;
logo, mult(0, div(x, 0)) é indefinida.
Observação: Problemas de dupla interpretação
(definida/indefinida) são solucionados usando regras de
avaliação de funções recursivas.
COMPUTAÇÃO
UNIDADE 5:
Classes de Solucionabilildade de 
Problemas
COMPUTAÇÃO
Introdução
Programas mais rápidos são aqueles que apresentam tamanhos
menores quando alocados na memória real do computador
para sua execução (run-time).
Os problemas em uma Máquina de Turing podem ser
considerados tratáveis e intratáveis.
A complexidade computacional nos permite analisar o quão
complexo é a execução de um programa, nos permitindo,
muitas das vezes, adotando o princípio da redução, a ter
soluções computacionais para o mesmo programa, com
complexidade menor que o original, sem que seja perdido a
sua essência na solucionabilidade de problemas.
COMPUTAÇÃO
Complexidade Computacional
A complexidade computacional diz respeito à quantidade de
trabalho envolvida na resolução do problema pelo algoritmo
(tempo de execução), medida, muitas vezes, pela quantidade
de trabalho que uma determinada instância do problema
necessita para resolvê-lo.
Também se pode considerar a quantidade de memória
necessária (espaço) e, no caso de processamento paralelo e
distribuído, o número de processadores necessários para a
conclusão do programa executado.
COMPUTAÇÃO
Problemas Previamente Tratados
Soluções algorítmicas de ordem limitado polinomialmente,
representadas por (Θ(n3))
Com solução polinomial: tratável
Sem solução polinomial conhecida: intratável
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Coloração de Grafos: dados G = (V, E) e S, achar C : V → S tal
que se (u, v) ∈ V, então C(u)  C(v).
Número cromático de G: mínima |Imagem(C(V))|, denota X(G)
Problema de otimização: dado G, determine X(G) e produza
uma coloração ótima
Problema de decisão: dados G e k ≥ 0,
determine se existe Ccom
|Imagem(C(V))| ≤ k
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Execução de tarefas com penalidades: dadas sequências, j1,
..., jn , t1, ...,tn , d1, ..., dn , p1, ..., pn respectivamente, de
tarefas, tempos de execução, prazos limite e penalidades,
uma execução das tarefas é uma permutação π de [1, ..., n].
A penalidade de π é,
Pπ := σ𝑘=1
𝑛 k=1[if tπ(1) + · · · + tπ(k) > dπ(k) then pπ(k) else 0]
Problema de otimização: determine a penalidade mínima.
Problema de decisão: dado, adicionalmente
k ∈ N, determine se existe uma execução π
com Pπ ≤ k.
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Empacotamento (bin packing): Dado um número ilimitado de
caixas de capacidade 1 e n objetos com tamanhos s1, ..., sn,
onde 0 ≤ si ≤ 1, para todo 1 ≤ i ≤ n.
Problema de otimização: determine o menor número de caixas
para empacotar os n objetos
Problema de decisão: dado, adicionalmente k ∈ N, determine
se existe um empacotamento dos n objetos
em k caixas
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Soma de subconjuntos: Dados C ∈ N e n objetos com tamanhos
s1, ..., sn.
Problema de otimização: encontre o subconjunto de objetos
com máximo tamanho total que não exceda C
Problema de decisão: determine se existe um subconjunto de
objetos com tamanho total de exatamente C
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Forma Normal Conjuntiva - Satisfatibilidade (CNF-SAT –
Conjuntive Normal Form Satisfiability): Um literal é uma
variável booleana p ou sua negação ¬p. Uma cláusula é uma
disjunção de literais. Uma fórmula lógica em forma normal
conjuntiva é uma conjunção de cláusulas.
Exemplo: (p ∨ q ∨ r ∨ ¬s) ∧ (r ∨ ¬q ∨ ¬p) ∧ (s ∨ ¬r)
Problema de decisão: determine se existe uma atribuição de
valores true e false para as variáveis booleanas de uma
fórmula lógica em CNF tal que a fórmula é true.
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Caminhos e circuitos Hamiltonianos: Dado um grafo não
dígrafo, G = ({v1, ..., vn}, E), um caminho Hamiltoniano em G é
uma permutação π de [1, ..., n], tal que para todo 1 ≤ i < n,
(vπ(i) , vπ(i+1)) ∈ E.
Se adicionalmente (vπ(n), vπ(1)) ∈ E, diz-se que o caminho é
um circuito Hamiltoniano.
Problema de decisão: dado um dígrafo G, determine se existe
um caminho (circuito) Hamiltoniano em G.
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Problema do caixeiro viajante: Dado um dígrafo com pesos, G
= ({v1, ..., vn}, E, p), onde p : E → R
∗, um circuito
Hamiltoniano π em G tem custo,
෍
𝑖=1
𝑛−1
p((𝑣 𝑖 , 𝑣 𝑖 + 1 )) + 𝑝((𝑣 𝑛 , 𝑣 1 ))
Problema de otimização: dado um dígrafo com pesos, encontre
o circuito hamiltoniano de custo mínimo.
Problema de decisão: dado adicionalmente um
inteiro k, determine se existe um circuito
Hamiltoniano com peso menor ou igual que k.
COMPUTAÇÃO
Problemas de Decisão e de Otimização
Tentativa e Erro (Backtraking): decompor o processo em um
número finito de subtarefas parciais que devem ser exploradas
exaustivamente numa Máquina de Turing.
Problema de otimização: encontre o melhor movimento para
gerar o menor grau de impacto negativo às jogada realizada
Problema de decisão: determine se existe um espaço
disponível válido para movimentar, por exemplo, a
peça de xadrez, cavalo. Caso não existam espaços
disponíveis para a movimentação, deve-se escolher
outra peça para movimentar.
COMPUTAÇÃO
Complexidade Computacional
Problema abstrato de decisão:
conjunto I de instâncias e
função f : I → {SIM, NÃO}
Exemplo: Problema circuito hamiltoniano.
I: conjunto de todos os grafos.
Para todo G em I,
SIM se G tem um circuito hamiltoniano
f(G) =
NÃO caso contrário
O valor f(X) é a resposta do problema para a instância X em I.
COMPUTAÇÃO
Complexidade Computacional
Para um problema abstrato ser resolvido, instâncias devem
estar convenientemente codificadas.
Problema concreto de decisão: problema abstrato de decisão
em que as instâncias estão codificadas convenientemente em
um alfabeto finito Σ.
Exemplo: Problema circuito hamiltoniano.
G dado pelas suas listas de adjacências.
Considere, sem perda de generalidade, que Σ = {0, 1}.
Logo, daqui para frente, todos os problemas são concretos.
COMPUTAÇÃO
Modelo de Computação
Algoritmo: programa escrito em uma linguagem “X”.
Custo de uma operação: proporcional ao número de bits dos
operandos.
Custo de um acesso à memória: proporcional ao número de
bits dos operandos.
(Isto é polinomialmente equivalente à Máquina de Turing)
Um algoritmo resolve ou decide um problema de decisão (I, f)
se, para cada X em I, o algoritmo encontra a resposta para X,
isto é, o algoritmo calcula f(X).
COMPUTAÇÃO
Problemas Indecidíveis
Existem problemas para os quais não existe um algoritmo:
Estes são os ditos problemas indecidíveis.
Exemplo: Problema da parada dado um programa e um arquivo
de entrada para ele, decidir se tal programa pára ou não
quando executado com este arquivo de entrada.
Não existe algoritmo que resolva o problema da parada
COMPUTAÇÃO
As Classes P, NP e NP-Completude
A Classe P
Um algoritmo resolve um problema de decisão (I, f) em tempo
O(T(n)), se para cada n em N e cada X em I com |X| = n, o
algoritmo encontra a resposta f(X) para X em tempo O(T(n)).
Para uma Máquina de Turing, um problema de decisão é
solúvel em tempo polinomial, se existe algum k para o qual
existe um algoritmo que resolve o problema em tempo O(nk).
Tais problemas são ditos tratáveis.
Portanto, a classe de complexidade P, apresenta um
Conjunto dos problemas de decisão tratáveis.
COMPUTAÇÃO
As Classes P, NP e NP-Completude
A Classe NP
Considere o problema circuito hamiltoniano. Se a resposta
para uma instância G for SIM, então existe um circuito
hamiltoniano C no grafo.
Dados G e C, é possível verificar em tempo polinomial em |G|
se C é de fato um circuito hamiltoniano em G ou não. Ou seja,
temos como certificar eficientemente que a resposta SIM está
correta.
COMPUTAÇÃO
As Classes P, NP e NP-Completude
A Classe NP
Conseguimos certificar eficientemente a resposta NÃO?
Surpreendentemente, não se conhece nenhum método de
certificação eficiente para a resposta NÃO no caso do
problema circuito hamiltoniano.
Portanto, a classe de complexidade NP, apresenta problemas
para os quais a resposta SIM pode ser certificada e verificada
em tempo polinomial.
COMPUTAÇÃO
As Classes P, NP e NP-Completude
A Classe NP
Mais precisamente, um problema de decisão está em NP se
existe um algoritmo A tal que:
1. para qualquer instância X do problema com resposta SIM,
existe um Y em Σ∗ tal que A(X, Y) devolve SIM;
2. para qualquer instância X do problema com resposta NÃO,
para todo Y em Σ∗, A(X, Y) devolve NÃO;
3. A consome tempo polinomial em |X|.
Y é chamado de certificado para SIM da instância X.
COMPUTAÇÃO
As Classes P, NP e NP-Completude
A Classe NP-Completude
Complemento de um problema de decisão Q: problema de
decisão obtido invertendo-se o SIM e o NÃO na resposta ao
problema Q.
Exemplo: Problema não-hamiltoniano Resposta é SIM sempre
que o grafo não tem um circuito hamiltoniano e NÃO caso
contrário, independentemente do modelo da MT utilizada.
Classe de complexidade NP-Completude: problemas de decisão
que são complemento de problemas de decisão em NP.
Problemas para os quais existe um certificado (curto) para a
resposta NÃO.
COMPUTAÇÃO
As Classes P, NP e NP-Completude
P x NP x NP-Completude (coNP)
O problema circuito hamiltoniano é um exemplo de problema
em NP enquanto que o problema não-hamiltoniano é um
exemplo de problema em coNP.
Note ainda que P ⊆ NP ∩ coNP.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A complexidade de tempo de uma computação mede a
quantidade de trabalho gasto pela computação.
O tempo de uma computação de uma Máquina de Turing é
quantificado pelo número de transições processadas.
Seja uma máquina de Turing M que aceita palíndromos sobre o
alfabeto Σ = {a, b}
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Máquinade Turing
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Tabela de Transição
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Como esperado, o número de transições em uma computação
depende da cadeia de entrada.
De fato, a quantidade de trabalho difere para cadeias de
mesmo comprimento.
Ao invés de tentar determinar o número exato de transições
para cada cadeia de entrada, a complexidade de tempo de
uma Máquina de Turing é medida pelo trabalho necessário
para cadeias de um comprimento fixo.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Definição: Seja M uma Máquina de Turing. A complexidade de
tempo (“tempo de execução”) de M é a função ctM : N → N tal
que ctM (n) é o número máximo de transições processadas por
uma computação de M quando iniciada com uma cadeia de
entrada de comprimento n, independente de M aceitar ou
não.
Quando se avalia a complexidade de tempo de uma Máquina
de Turing, assume-se que a computação termina para toda
cadeia de entrada.
Não faz sentido discutir a eficiência de uma computação que
continua indefinidamente.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A definição serve para máquinas que aceitam linguagens e
computam funções.
A complexidade de tempo de máquinas determinísticas multi-
trilhas e multi-fitas é definida de maneira similar.
A complexidade de tempo dá a performance de pior caso da
Máquina de Turing. Analisando um algoritmo, escolhe-se a
performance do pior caso por duas razões:
1. Considera-se as limitações da computação algorítmica. O
valor ctM (n) especifica os recursos mínimos necessários para
garantir que a computação de M termina quando iniciada com
uma cadeia de entrada de comprimento n.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
2. A performance do pior caso é frequentemente mais fácil de
avaliar do que a performance média.
A máquina M que aceita os palíndromos sobre Σ = {a, b} é
usada para demonstrar o processo de determinar a
complexidade de tempo de uma Máquina de Turing.
Uma computação de M termina quando toda a cadeia de
entrada foi substituída por brancos ou o primeiro par de
símbolos não previsto é descoberto.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Como a complexidade de tempo mede a performance do pior
caso, há necessidade de se preocupar apenas com as cadeias
cujas computações fazem com que a máquina faça o maior
número possível de ciclos acha-e-apaga. Esta condição é
satisfeita quando a entrada é aceita por M.
Usando estas observações, pode-se obter os valores iniciais da
função ctM da computações da tabela .
ctM (0) = 2
ctM (1) = 3
ctM (2) = 7
ctM (3) = 10
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Quando M processa uma cadeia de comprimento par, a
computação alterna entre sequências de movimentos a direita
e a esquerda da máquina.
Inicialmente a cabeça é posicionada no símbolo mais a
esquerda da porção não branca da fita e então:
Movimentos à direita: a máquina se move à direita, apagando
o símbolo não-branco mais à esquerda. O resto da cadeia é
lida e a máquina entra no estado q4 ou q7. Isto requer k + 1
transições, onde k é o comprimento da porção não-branca da
cadeia.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Movimentos à esquerda: M se move para a esquerda, apagando
o símbolo correspondente, e continua através da porção não-
branca da fita. Isto requer k transições.
As ações acima reduzem o comprimento da porção não-branca
da fita por dois.
O ciclo de comparações e apagamentos é repetido até que a
fita esteja completamente em branco.
Como observado, a performance do pior caso para uma cadeia
de comprimento par ocorre quando M aceita a entrada.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A computação que aceita uma cadeia de comprimento n
requer n/2 iterações do loop anterior.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
O número máximo de transições em uma computação de uma
cadeia de comprimento par n é a soma dos primeiros n + 1
números naturais.
Uma análise de cadeias de comprimento ímpar produz o
mesmo resultado.
Consequentemente, a complexidade de tempo de M é dada
pela função:
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A máquina de duas fitas M’
também aceita o conjunto de palíndromos sobre Σ = {a, b}.
Uma computação de M’ percorre a entrada fazendo uma cópia
na fita 2.
A cabeça da fita 2 é depois movida à posição inicial.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Então, as cabeças se movem ao longo da entrada, fita 1 para a
esquerda e fita 2 para a direita, comparando os símbolos das
fitas 1 e 2.
Se as cabeças encontrarem símbolos diferentes, a entrada não
é um palíndromo e a computação para num estado de não-
aceitação.
Quando a entrada é um palíndromo, a computação para e
aceita quando brancos são simultaneamente lidos nas fitas 1 e
2.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
Para uma entrada de comprimento n, o número máximo de
transições ocorre quando a cadeia é um palíndromo.
Uma aceitação requer três passos completos:
 a cópia
 a volta
 a comparação
Contando o número de transições em cada passo, vê-se que a
complexidade de tempo de M’ é
ctM’(n) = 3(n + 1) + 1
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A definição da complexidade de tempo ctM é baseada nas
computações da máquina M e não na linguagem aceita pela
máquina.
Sabe-se que muitas máquinas diferentes podem ser
construídas para aceitar a mesma linguagem, cada qual com
diferentes complexidades de tempo.
Diz-se que uma linguagem L é aceita em tempo determinístico
f(n) se houver uma Máquina de Turing determinística M
qualquer com ctM (n) ≤ f(n) para todo n ∈ N.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A máquina M mostrou que o conjunto de palíndromos sobre Σ =
{a, b} é aceito em tempo
(n2+3n+2) 
2 
enquanto que a máquina de duas fitas M’ exibiu aceitação no
tempo 3n + 4.
Uma transição de uma máquina de duas fitas utiliza mais
informação e realiza uma operação mais complicada do que a
máquina de uma fita.
COMPUTAÇÃO
Complexidade de Tempo e Espaço de uma MT
A estrutura adicional da transição de duas fitas permitiu a
redução no número de transições de M’ necessárias para
processar uma cadeia em relação à máquina de uma fita M.
Portanto, vê-se um equilíbrio entre a complexidade das
transições e o número que deve ser processado.
Há formas de “acelerar” uma máquina que aceita uma
linguagem L para produzir uma nova máquina que aceita L
num tempo menor.
COMPUTAÇÃO
Complexidade de MT em Casos Reais
Buscaremos aqui fazer aplicações reais do dia-a-dia que
requerem uma modelagem das mesmas por meio de máquinas
de estado, baseadas na estrutura e complexidade lógica da
máquina de turing, MT.
Vejamos um exemplo prático: Modele uma máquina de estado
computável, semelhante a uma MT, que simule o
funcionamento de uma lâmpada padrão comum, assumindo os
estados de ACESA ou APAGADA, mediante o acionamento de
um interruptor com as funções de Liga (ON) e Desliga (OFF).
COMPUTAÇÃO
Complexidade de MT em Casos Reais
Solução do problema:
COMPUTAÇÃO
UNIDADE 6:
Sistemas de Estados Finitos
COMPUTAÇÃO
Introdução
A computabilidade tem por objetivo o estudo da
solucionabilidade de problemas. Isso significa investigar a
existência ou não de algoritmos que solucionem determinada
classe de problemas.
A computabilidade permite a investigação dos limites
computacionais das classes de problemas e,
consequentemente, os limites do que pode efetivamente ser
implementado em um computador.
O Sistema de Estados Finitos tem que proporcionar a
computabilidade parcial ou total de certo problema.
COMPUTAÇÃO
Computabilidade
Em 1901, David Hilbert formulou uma lista de
problemas que contia vinte e três problemas
matemáticos, até o momento insolúveis.
Em 1970, Yuri Matijasevic provou que um
problema pode ter uma solução satisfatível ou
não, independente de comoele é classificado.
COMPUTAÇÃO
Computabilidade
A verificação da solucionabilidade de um problema pode ser
tratada como a verificação se determinada linguagem é
recursiva, associando as condições de ACEITA/REJEITA de
uma Máquina Universal às respostas sim/não,
respectivamente, caracterizando-o solúvel ou não.
A Classe dos Problemas Solucionáveis (solúveis) é equivalente
à Classe das Linguagens Recursivas. Ainda existem muitos
problemas que são considerados não-solucionáveis
(insolúveis).
COMPUTAÇÃO
Computabilidade
Alguns Problemas Clássicos:
a) Equivalência de Compiladores: Não existe algoritmo
genérico que seja capaz de comparar quaisquer dois
compiladores de linguagens livres do contexto (reconhecidas
pelo formalismo Autômato Não-Determinístico com uma Pilha);
b) Detector Universal de Loops: Dados um programa e uma
entrada quaisquer, Não existe algoritmo genérico capaz de
verificar se o programa vai parar ou não, para a entrada dada.
Este problema é universalmente conhecido como o Problema
da Parada.
COMPUTAÇÃO
Computabilidade
Alguns problemas não-solucionáveis, são parcialmente
solucionáveis (parcialmente solúvel), ou não.
Exemplo:
Existe um algoritmo capaz de responder sim, embora,
eventualmente, possa ficar em loop infinito para uma resposta
que deveria ser não.
COMPUTAÇÃO
Computabilidade
Problemas parcialmente solúveis são computáveis!
A Classe dos Problemas Parcialmente Solúveis é equivalente à
Classe das Linguagens Enumeráveis Recursivamente.
Classe dos Problemas = Computáveis × Não-Computáveis
Um solução aparentemente solúvel, quando não-solúvel, pode
tanto ser caracterizada como insolúvel, quanto parcialmente
solúvel, dependendo do caso a que ela for aplicada.
COMPUTAÇÃO
Classe de Solucionabilidade de Problema
Um problema é dito Solúvel ou Totalmente Solúvel se existe
um algoritmo (Máquina Universal) que solucione o problema
tal que sempre pára, para qualquer entrada, com uma
resposta afirmativa (ACEITA) ou negativa (REJEITA).
Um problema é dito insolúvel ou não-solúvel se não existe um
algoritmo (Máquina Universal) que o solucione que sempre
pára, para qualquer entrada.
COMPUTAÇÃO
Classe de Solucionabilidade de Problema
Um problema é dito Parcialmente Solúvel ou Computável se
existe um algoritmo (Máquina Universal) que solucione o
problema tal que pára quando a resposta é afirmativa
(ACEITA). Entretanto, quando a resposta for negativa, o
algoritmo pode parar (REJEITA) ou continuar indefinidamente
(LOOP).
Um problema é dito Completamente Insolúvel ou Não-
Computável se não existe um algoritmo (Máquina Universal)
que solucione o problema tal que pára quando a resposta é
afirmativa (ACEITA).
COMPUTAÇÃO
Problemas de Decisão
Dado um programa P para uma máquina universal M, decidir se
a função computada 〈P, M〉 é total (ou seja, se a
correspondente computação é finita). Dessa forma, quando P
precisa decidir entre duas ou mais alternativas válidas, através
de uma dada função computada, dizemos ter um Problema de
Decisão.
LD = { p|<P, M> (p) → p1 ou p2 }
COMPUTAÇÃO
Problemas de Decisão
Dado um programa P para uma máquina universal M, decidir se
a função computada 〈P, M〉 é total (ou seja, se a
correspondente computação é finita). Dessa forma, quando P
precisa decidir entre duas ou mais alternativas válidas, através
de uma dada função computada, dizemos ter um Problema de
Decisão.
COMPUTAÇÃO
Problemas da Auto Aplicação
Dado um programa monolítico arbitrário P para a Máquina
Norma, decidir se a função computada <P, Norma> é definida
para p, onde p é a codificação de P.
Dado um programa monolítico arbitrário P para Norma, decidir
se a computação de P em Norma termina ou não, para a
entrada p.
LAA = { p|<P, Norma>(p) é definida, 
P programa de Norma, p= código(P) }
COMPUTAÇÃO
Problemas da Auto Aplicação
Dessa forma, a questão da solucionabilidade do Problema da
Auto Aplicação é a investigação se a linguagem é recursiva.
Portanto, constata-se que o Problema da Auto Aplicação é
Parcialmente Solúvel.
COMPUTAÇÃO
Princípio da Redução
Sejam dois problemas A e B e as correspondentes linguagens
LA e LB.
Para uma Máquina de Redução R de LA para LB é tal que (w 
Σ):
- Se w  LA, então R(w)  LB
- Se w  LA, então R(w)  LB
Portanto, o mapeamento de linguagens é uma função
computável total.
COMPUTAÇÃO
Princípio da Redução
Sejam dois problemas A e B e as correspondentes linguagens
LA e LB.
Se existe uma máquina de redução R de LA para LB (sobre um
alfabeto Σ), então os seguintes resultados podem ser
estabelecidos:
a) Se LB é recursiva, então LA é recursiva;
b) Se LB é enumerável recursivamente, então LA é
enumerável recursivamente;
c) Se LA não é recursiva, então LB não é recursiva;
d) Se LA não é enumerável recursivamente, então LB não é
enumerável recursivamente.
COMPUTAÇÃO
Princípio da Redução
Seja R Máquina de Turing de Redução que sempre pára e que
reduz LA a LB.
COMPUTAÇÃO
Princípio da Recursão
Na recursão, vê-se o problema como um todo e reduz-se o
problema a subproblemas menores, até que se chega a um
problema base, iniciando assim o processo reverso, com a
resolução de cada instância do problema.
COMPUTAÇÃO
Problema da Parada
Dada uma Máquina Universal M qualquer e uma palavra w
qualquer sobre um alfabeto de entrada, existe um algoritmo
que verifique se M pára, aceitando ou rejeitando, ao processar
a entrada w?
Isso requer um entendimento referente ao problema da
parada, obviamente.
COMPUTAÇÃO
Problema da Parada
O Problema da Parada é um problema de decisão (do tipo
sim/não) e pode ser redefinido assim:
LP = { (m, w) | m = código(M) e 
w  ACEITA(M)  REJEITA(M) }
O Teorema do Problema da Parada é Não-Solúvel.
COMPUTAÇÃO
Problema da Parada
A linguagem LP (Problema da Parada) não é recursiva:
LP = { (m, w) | m = código(M) e w  ACEITA(M)  REJEITA(M) }
COMPUTAÇÃO
Problema da Parada da Palavra Vazia
Dada uma Máquina Universal M qualquer, existe um algoritmo
que verifique se M pára, aceitando ou rejeitando, ao processar
a entrada vazia.
COMPUTAÇÃO
Problema da Totalidade
Dada uma Máquina Universal M qualquer, existe um algoritmo
que verifique se M pára, aceitando ou rejeitando, ao processar
qualquer entrada.
COMPUTAÇÃO
Problema da Equivalência
O Problema da Equivalência é um problema de decisão (do
tipo sim/não) que verifica a equivalência de duas máquinas
universais.
COMPUTAÇÃO
Problema da Correspondência de Post
O Problema da Correspondência de Post é definido sobre um
Sistema de Post.
Um Sistema de Post S definido sobre um alfabeto Σ é um
conjunto finito e não-vazio de pares ordenados de palavras
sobre Σ.
O Problema da Correspondência de Post é a investigação da
existência de um algoritmo que análise qualquer Sistema de
Post e determine se ele tem pelo menos uma solução.
COMPUTAÇÃO
Problema da Correspondência de Post
Teorema Problema da Correspondência de Post é Não-
Solucionável
A linguagem que traduz o Problema da Correspondência de
Post não é recursiva:
LCP={s|s = código(S) e S é Sistema de Post
com pelo menos uma solução }
Prova:
A partir de uma Máquina de Post M qualquer sobre o alfabeto Σ
e de uma palavra w ∈ Σ* qualquer, constrói-se um Sistema
Normal de Post baseado na sequência de comandos executados
por M para a entrada w, de tal forma que o Sistema Normal
tenha solução se, e somente se, M pára para a entrada w.
COMPUTAÇÃO
Problema da Correspondência de Post
Portanto, o Problema da Parada é reduzido ao Problema da
Correspondência de Post.
A linguagem LP que traduz o Problema da Parada (que não é
recursiva) é reduzida à linguagem LCP.
COMPUTAÇÃO
Propriedades da Solucionabilidade
Dado:
• o complemento de uma linguagem recursiva é uma
linguagem recursiva;
• uma linguagem é recursiva se, e somente se, a linguagem e
seu complemento são enumeráveis recursivamente;
• o complemento de um problema solucionável é solucionável;
• um problema é solucionável se, esomente se, o problema e
seu complemento são parcialmente solucionáveis.
EXEMPLO: Problema da Parada
• o Problema da Parada é parcialmente solucionável;
• o Problema da Parada é não-solucionável;
• portanto, o Problema da Não-Parada é não-solucionável.
COMPUTAÇÃO
Propriedades da Solucionabilidade
Teorema: Complemento de uma Linguagem Recursiva
- é uma Linguagem Recursiva
- se uma linguagem L sobre um alfabeto Σ qualquer é
recursiva, então o seu complemento Σ* - L também é uma
linguagem recursiva.
Prova:
Suponha L uma linguagem recursiva sobre Σ.
Então existe M, Máquina Universal, que aceita a linguagem e
sempre para para qualquer entrada. Ou seja:
ACEITA(M) = L
REJEITA(M) = Σ* - L
LOOP(M) = ∅
COMPUTAÇÃO
Propriedades da Solucionabilidade
Seja M' uma Máquina Universal construída a partir de M, mas
invertendo-se as condições de ACEITA por REJEITA e vice-
versa.
Portanto, M' aceita Σ* - L e sempre pára para qualquer
entrada. Ou seja:
ACEITA(M') = Σ* - L
REJEITA(M') = L
LOOP(M') = ∅
Logo Σ* - L é uma linguagem recursiva.
COMPUTAÇÃO
Sistema de Estados Finitos
Um estado descreve um nó de comportamento do sistema em
que está à espera de uma condição para executar uma
transição. Normalmente, um estado é introduzido quando o
sistema não reage da mesma forma para uma mesma
condição.
No exemplo de um sistema de rádio de carro, quando se está
ouvindo uma estação de rádio, o estímulo "próximo" significa ir
para a próxima estação. Mas quando o sistema está no estado
de CD, o estímulo "próximo" significa ir para a próxima faixa. O
mesmo estímulo desencadeia ações diferentes, dependendo do
estado atual.
COMPUTAÇÃO
Sistema de Estados Finitos
Em algumas representações de máquinas de estado finitas,
também é possível associar ações a um estado:
•Ação de entrada: o que é realizado ao entrar no estado,
•Ação de saída: o que é executado ao sair do estado.
A transição é um conjunto de ações a serem executadas
quando uma condição for cumprida ou quando um evento é
recebido.
Máquinas de estado são utilizadas para descrever circuitos
sequenciais. Diferentemente de um contador que em geral
conta eventos, uma máquina de estado costuma ser usada
para controlar o evento.
COMPUTAÇÃO
Sistema de Estados Finitos
A máquina está em apenas um estado por vez, este estado é
chamado de estado atual. Um estado armazena informações
sobre o passado, isto é, ele reflete as mudanças desde a
entrada num estado, no início do sistema, até o momento
presente.
Uma transição indica uma mudança de estado e é descrita por
uma condição que precisa ser realizada para que a transição
ocorra. Uma ação é a descrição de uma atividade que deve ser
realizada num determinado momento.
O sistema de estados finitos são representados na teoria da
computação através do estudo dos autômatos finitos.
COMPUTAÇÃO
UNIDADE 7:
Autômatos Finitos
COMPUTAÇÃO
Introdução
Os sistemas de estados finitos representa um modelo
matemático de sistema com entradas e saídas discretas.
Podem possuir um número finito e predefinido de estados.
Cada estado assume somente as informações necessárias para
determinar as ações para a próxima entrada.
O fato de possuir um número finito e predefinido de estados
significa que todos os estados possíveis do sistema podem ser
mecanicamente explicitado antes de iniciar o processamento,
ou seja, podem ser definidos de partida, por extensão. Um
forte motivacional para estudo de sistemas de estados finitos é
o fato de poderem ser associados a diversos tipos de sistemas
naturais e construídos.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
Autônomos Finitos Determinísticos refere-se a um sistema de
estados finitos o qual constitui um modelo computacional do
tipo sequencial muito comum em diversos estudos teórico-
formais da Computação e da Informática. Cmo destaque dessa
aplicabilidade, temos:
- Linguagens Formais;
- Compiladores;
- Semântica Formal;
- Modelos para Concorrência.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
Veja o sistema de estados com suas funções de transição:
f(pq) – Função de transição que permite a mudança do estado
p para o estado q;
f(qp) – Função de transição que permite a mudança do estado
q para o estado p;
f(p) – Função recursiva que permanece no estado p de origem;
f(q) – Função recursiva que permanece no estado q de origem;
COMPUTAÇÃO
Autômatos Finitos Determinísticos
Um Autômato Finito Determinístico ou simplesmente Autômato
Finito pode ser visto como uma máquina constituída
basicamente de três partes:
Fita: Dispositivo de entrada que contém a informação a ser 
processada;
Unidade de Controle: Reflete o estado corrente da
máquina. Possui uma unidade de leitura (cabeça de leitura
da fita) a qual acessa uma célula da fita de cada vez e
movimenta-se exclusivamente para a direita.
Programa, Função Programa ou Função de Transição:
Função que comanda as leituras define o estado da
máquina.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
Autômato Finito como Máquina de Estado
- A fita é finita, sendo dividida em células, cada uma das quais
armazena um símbolo.
- Os símbolos pertence a um alfabeto de entrada.
- Não é permitido gravar sobre a fita.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
A unidade de controle possui um número finito e predefinido
de estados (controle finito).
A unidade de controle lê o símbolo de uma célula um de cada
vez.
Como método de construção de um AF nem sempre é
importante considerar desde logo a obrigatoriedade acima
referida.
Muitas vezes o problema resolve-se nos seus aspectos
essenciais deixando alguns estados sem transição para algumas
entradas.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
As transições acrescentam-se depois e vão para o mesmo
estado único denominado estado “armadilha” (trap state).
A função de transição estendida, *, materializa a ideia da
dinâmica do autômato. Em certos problemas, é mais simples
desenhar o autômato que reconhece a linguagem
complementar e, depois, transformar os estados finais em não
finais e vice-versa.
Este fato pode ser provado e a situação de termos a função 
total é um elemento importante para a prova.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
As linguagens associadas aos autômatos finitos dizem-se
regulares.
Em problemas do tipo, “Desenhe um autômato que reconheça
a linguagem sobre o alfabeto  = {a1, a2 , ..., an} cujas
palavras têm a característica x...”, o método usual é começar
por desenhar a parte do autômato que satisfaz a característica
x e depois preocuparmos-nos como o fato de todas as
transições terem que estar definidas.
Um AF pode ser representado por um grafo de transição
(também chamado de diagrama de estados) ou por uma tabela
de transição.
COMPUTAÇÃO
Autômatos Finitos Determinísticos
Exemplo de um Autômato Finito Determinístico:
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Símbolo do alfabeto de entrada:  (lambda).
A tabela de transições de um AFND passa a ter mais uma
coluna. Esta transição simboliza a possibilidade da máquina
mudar de estado sem consumir nenhum símbolo da entrada.
Sua utilização facilita determinadas construções com os
autômatos, mas obriga a alguma atenção relativamente às
situações de não determinismo que a sua utilização determina.
As transições, se fazem para subconjuntos dos estados do
autômato.
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
É possível a situação de não haver, para determinados
símbolos do alfabeto de entrada, nenhuma transição, ou seja,
é possível (q, a) = 0.
Daqui também decorre não ser necessário o uso do estado
“armadilha” (trap state) para completar a especificação.
Logo, podem existir no autômato de estados “armadilha”.
O não determinismo consiste na possibilidade de um autômato
transitar para um dado estado e um símbolo do alfabeto de
entrada para mais do que um estado.
A transição pode não consumir nenhum símbolo da entrada.
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Um AFND define-sepor: M = (Q, , , q0, F)
onde:
: Q x   {} → 2Q
Veja no exemplo:
As transições () são importantes em determinados processos
construtivos mas elas podem ser eliminadas.
O algoritmo de eliminação tem duas fases:
1. Eliminação de ciclos de transições - 
2. Eliminação de transições -  ”simples”
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Algoritmo elimina_ciclos
Entrada: Autômato
Saída: Autômato equivalente sem ciclos de transição - 
Início
Marcar todos os estados com 0;
Enquanto existirem estados com 0 faça
Escolhe um;
Constrói a sua árvore de transição - 
Se o estado aparece repetido
então Funde o respectivo caminho
senão Marca o estado com 1
Fim-se
Fim-Enquanto
Fim
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Situação inicial de um autômato com dois ciclos de transição -
 :
Elimina o primeiro ciclo:
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Eliminando o próximo ciclo, teremos então a situação final
(sem ciclos):
O segundo, e último passo, será a eliminação de transição - 
simples. Para tanto, vejamos o algoritmo responsável.
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Algoritmo elimina_transição_simples
Entrada: autômato sem ciclos de transições - 
Saída: autômato equivalente sem transições - 
Início
Enquanto existirem transições-  faça
Escolher um estado p tal que (p, ) = q
Faz (p, ) = 0
Acrescentar (p, ai) = qi para todo ai : (p, ai) = qi
Acrescentar p a F, caso q seja estado final
Fim-Enquanto
Fim
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Considere o exemplo a seguir (situação inicial):
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Aplicando o algoritmo obtemos numa primeira iteração a
situação intermediária mostrada na figura a seguir:
COMPUTAÇÃO
Autômatos Finitos Não Determinísticos
Numa nova iteração obtemos como resultado final (autômato
sem transições vazias):
COMPUTAÇÃO
Transformação Não Determinísticos em Determinismo
Os AFND são métodos cômodos de especificação de solução
para problemas complexos. Sua implementação tem custos
operacionais elevados. Veja o algoritmo a seguir:
Algoritmo transforma_ND_D
Entrada: AFND, tabela de transição
Saída: AFD equivalente
Início
Transforma todos os estados qi em {qi}=, mantendo a
indicação do estado inicial e dos finais
Se ({qi}, a) = {qj, qk, ..., qm}
Então Introduzir este subconjunto na tabela, caso seja novo
Fim-Se
COMPUTAÇÃO
Transformação Não Determinísticos em Determinismo
Enquanto existirem subconjuntos de estados novos faça
Para cada estado novo {qj, qk, ..., qm} faça
Determine suas transições conforme definição:
({qj, qk, ..., qm}, a) =  (qj, a)
qi{qj, qk, ..., qm}
Fim-Para
Acrescentar à tabela de transições novos estados,
caso existam
Fim-Enquanto
Fim
COMPUTAÇÃO
Transformação Não Determinísticos em Determinismo
É fácil concluir que o algoritmo apresentado termina, pois,
para um autômato que inicialmente tem n estados, o número
de estados possíveis é igual ao número de subconjuntos que se
podem formar, ou seja, 2n. Observe o autômato a seguir:
COMPUTAÇÃO
Transformação Não Determinísticos em Determinismo
Segue a tabela de transição correspondente ao autômato:
Estado final
COMPUTAÇÃO
Transformação Não Determinísticos em Determinismo
Para fixar o conceito, vamos representar o autômato abaixo,
por meio da tabela de transição:
Estado final
COMPUTAÇÃO
UNIDADE 8:
Expressão Regular e
Gramática Regular
COMPUTAÇÃO
Alfabetos e Linguagens
LINGUAGEM
Linguagem é um conceito fundamental no estudo da Teoria da
Computação, pois trata-se de uma forma precisa de expressar
problemas, permitindo um desenvolvimento formal adequado
ao estudo da computabilidade.
O dicionário Aurélio define linguagem como:
"o uso da palavra articulada ou escrita como meio de
expressão e comunicação entre pessoas".
Esta definição não é suficientemente precisa para permitir o
desenvolvimento matemático de uma teoria sobre linguagens.
COMPUTAÇÃO
Alfabetos e Linguagens
As definições que seguem são construídas usando como base a
noção de Símbolo ou Caractere, que é uma entidade abstrata
básica, não sendo definida formalmente. Letras e dígitos são
exemplos de símbolos frequentemente usados.
ALFABETO
Um Alfabeto é um conjunto finito de símbolos ou caracteres.
• um conjunto infinito não é um alfabeto;
• o conjunto vazio é um alfabeto.
Os seguintes conjuntos são exemplos de alfabetos:
• {a, b, c};
• conjunto vazio.
COMPUTAÇÃO
Alfabetos e Linguagens
Os seguintes conjuntos não são exemplos de alfabetos:
• conjunto dos números naturais;
• {a, b, aa, ab, ba, bb, aaa,...}.
CADEIA DE SÍMBOLOS E PALAVRA
Uma Cadeia de Símbolos sobre um conjunto é uma sequência
de zero ou mais símbolos (do conjunto) justapostos. Uma
Cadeia de Símbolos Finita é usualmente denominada de
Palavra.
ε denota a cadeia vazia ou palavra vazia.
Se Σ representa um conjunto de símbolos (um alfabeto),
Σ* => o conjunto de todas as palavras possíveis sobre Σ;
Σ+ denota Σ* - { ε }.
COMPUTAÇÃO
Alfabetos e Linguagens
COMPRIMENTO OU TAMANHO DE UMA PALAVRA
O Comprimento ou Tamanho de uma palavra w, representado
por |w|, é o número de símbolos que compõem a palavra.
PREFIXO, SUFIXO E SUBPALAVRA
Um Prefixo (respectivamente, Sufixo) de uma palavra é
qualquer sequência inicial (respectivamente, final) de
símbolos da palavra. Uma Subpalavra de uma
palavra é qualquer sequência de símbolos
contígua da palavra.
COMPUTAÇÃO
Alfabetos e Linguagens
Exemplos de Palavra, Prefixo, Sufixo, Tamanho:
a) abcb é uma palavra sobre o alfabeto {a, b, c};
b) Se Σ = {a, b}, então:
Σ+ = {a, b, aa, ab, ba, bb, aaa,...}
Σ* = {ε , a, b, aa, ab, ba, bb, aaa,...}
c) |abcb| = 4 e |ε| = 0;
d) Relativamente à palavra abcb, tem-se que:
ε, a, ab, abc, abcb são os prefixos;
ε, b, cb, bcb, abcb são os respectivos sufixos.
e) Qualquer prefixo ou sufixo de uma palavra
é uma subpalavra.
COMPUTAÇÃO
Alfabetos e Linguagens
LINGUAGEM FORMAL
Uma Linguagem Formal ou simplesmente Linguagem é um
conjunto de palavras sobre um alfabeto.
Suponha o alfabeto Σ = {a, b}.
Então:
a) O conjunto vazio e o conjunto formado pela palavra vazia
são linguagens sobre Σ. Obviamente, { } ≠ { ε }.
b) O conjunto de palíndromos (palavras que têm a mesma
leitura da esquerda para a direita e vice-versa) sobre Σ é um
exemplo de linguagem infinita.
ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa,...
COMPUTAÇÃO
Alfabetos e Linguagens
Dados L1={r, rs} e L2=(r, sr}, linguagens sobre {s, r}.
Qual o resultado de L1L2 ?
L1L2 = {r, rs, sr}
Qual o resultado de L1L2 ?
L1L2 = {r}
Qual o resultado de L1–L2 ?
L1–L2 = {rs}
COMPUTAÇÃO
Alfabetos e Linguagens
Dados L1={r, rs} e L2=(r, sr}, linguagens sobre {s, r}.
Qual o resultado de L1.L2 ?
L1.L2 = {r, rr, rsr, rs, rsr, rssr}
Qual o resultado de L12=L1.L1 ?
L12=L1.L1 = {rr, rrs, rsr, rsrs}
Qual o resultado de 2L1 ?
2L1 = {2r, 2rs}
COMPUTAÇÃO
Alfabetos e Linguagens
CONCATENAÇÃO DE PALAVRAS
A Concatenação de Palavras é uma operação binária, definida
sobre uma linguagem L, a qual associa a cada par de palavras
uma palavra formada pela justaposição da primeira com a
segunda tal que:
• não necessariamente é fechada em L; a concatenação de
duas palavras de uma linguagem não necessariamente resulta
em uma palavra da linguagem.
• é associativa; v(wt) = (vw)t = vwt
• possui elemento neutro à esquerda e à direita, o qual é a
palavra vazia. ε w = w = wε
COMPUTAÇÃO
Alfabetos e Linguagens
Suponha o alfabeto Σ = {a, b}.
Então, para as palavras v = baaaa e w = bb, tem-se que:
• vw = baaaabb
• vε = v = baaaa
CONCATENAÇÃO SUCESSIVA DE UMA PALAVRA
A Concatenação Sucessiva de uma Palavra (com ela mesma) ou
simplesmente Concatenação Sucessiva, representada na forma
de um expoente (suponha w uma palavra):
wn onde n é o número de concatenações sucessivas, é definida
indutivamente a partir da operação de concatenação binária.
COMPUTAÇÃO
Alfabetos e Linguagens
Veja:
w0 = ε;
wn = wn-1w, para n > 0.Vamos a um exemplo: Sejam w uma palavra e a um símbolo.
Então:
w3 = www
w1 = w
a5 = aaaaa
an = aaa...a (o símbolo a repetido n vezes)
COMPUTAÇÃO
Linguagens Regulares
O estudo das linguagens regulares ou tipo 3, é abordado
usando o seguinte formalismo:
a) Expressão Regular: Trata-se de um formalismo
denotacional, também considerado gerador, o qual é
definido a partir de conjuntos (linguagens) básicos e das
operações de concatenação e de união;
b) Gramática Regular: Trata-se de um formalismo axiomático
ou gerador, o qual, como o nome indica, é uma gramática,
mas com restrições de forma das regras de produção.
c) Autômatos Finitos: Trata-se de um formalismo operacional
ou reconhecedor, sendo, basicamente, um sistema de
estados finitos;
COMPUTAÇÃO
Linguagens Regulares
As linguagens regulares constituem a classe das linguagens
mais simples, sendo possível desenvolver algoritmos de
reconhecimento, de geração ou conversão entre formalismo de
pouca complexidade, de grande eficiência e de fácil
implementação.
Nesta aula iremos abordar a expressão regular e a gramática
regular, deixando para a próxima aula o estudo dedicado aos
Autômatos Finitos.
COMPUTAÇÃO
Linguagens Regulares
EXPRESSÃO REGULAR
As Linguagens Regulares são classes de linguagem simples de
cunho importante para o contexto. Elas estão presentes,
direta ou indiretamente, na modelação de sistemas físicos, nos
compiladores etc. Elas são, em geral, infinitas, pelo que se
torna necessário a existência de caracterizações finitas dessa
linguagem.
Uma possibilidade é o recurso à teoria dos conjuntos, como no
exemplo: L = {anbm, n, m ≥ 0}
Estas descrições com base em conjuntos têm, no entanto, um
problema: não são operacionais.
COMPUTAÇÃO
Linguagens Regulares
EXPRESSÃO REGULAR
Elementos e instrumentos de descrição de linguagem:
- Expressões regulares
- Gramáticas regulares
- Autômatos finitos
COMPUTAÇÃO
Linguagens Regulares
Dada uma expressão regular sobre um alfabeto  se define por
indução:
Ø,  e a  a  , são expressões regulares.
Se r1 e r2 são expressões regulares, então:
r1 + r2
r1 . r2
r*1
(r1)
Também são expressões regulares.
Nada mais é uma expressão regular que não resulte
especificamente da aplicação das regras 1 e 2.
COMPUTAÇÃO
Linguagens Regulares
Existe uma relação evidente entre expressões regulares sobre
um alfabeto  e uma linguagem sobre este mesmo alfabeto.
Assim:
COMPUTAÇÃO
Linguagens Regulares
GRAMÁTICA REGULAR
Uma gramática G = (N, T, , P) diz-se regular se e somente se
todas as suas produções forem da forma:
e diz-se que a gramática é linear à direita ou exclusivo.
e agora dizemos que é linear à esquerda. As
gramáticas regulares são utilizadas, como um exemplo prático,
em projetos de desenvolvimento de compiladores para
linguagens de programação.
COMPUTAÇÃO
Propriedades de Linguagens Regulares
Como ilustração de uma abordagem das Linguagens Formais às
linguagens n-dimensionais, no que segue é apresentada a
noção de Gramática de Grafos.
No caso de reescrita de grafos como termos, os grafos têm que
ser necessariamente dirigidos, etiquetados e com ordenação
nas arestas, e as operações são caracterizadas sobre
uma especificação de grafo, definida como:
G = <|{1=t1, ..., n=tn}>
COMPUTAÇÃO
Propriedades de Linguagens Regulares
Em que 1 é um par disjunto de nós (com variáveis) e ti um
termo. Também, o nó  indica a raíz do grafo.
nó raíz (  )
COMPUTAÇÃO
Propriedades de Linguagens Regulares
A idéia básica da gramática de grafos é análoga à das
gramáticas de Chomsky, ou seja:
- regras de produção são pares (mas de grafos);
- uma derivação é a substituição de um sub-grafo de acordo
com uma regra de produção.
As gramáticas de grafos constituem um caso particular de
gramáticas das categorias.
A idéia básica é substituir palavras por grafos no conceito do
contexto.
COMPUTAÇÃO
Gramáticas Livres de Contexto
Uma gramática livre de contexto é uma quádrupla (V, Σ, P, S)
onde:
• V é um conjunto de variáveis;
• Σ é o conjunto de símbolos terminais;
• P é um conjunto de regras que são elementos de um
conjunto V × {V ∪ Σ} ∗ , sendo, em geral, uma regra (A, w)
escrita como A → w.
• S ∈ V é um símbolo (uma variável) inicial.
COMPUTAÇÃO
Gramáticas Livres de Contexto
A gramática G = ({S, A}, {a, b}, P, S) com o conjunto P de
regras...
S→ AA
A→ AAA
A→ bA
A→ Ab
A→ a
gera strings com um número positivo de a’s.
COMPUTAÇÃO
Gramáticas Livres de Contexto
Quando temos diferentes regras para uma mesmo símbolo,
como A → Ab e A → a, podemos simplificar a escrita usando
uma barra vertical para separar as regras.
Poderíamos escrever o exemplo como A → Ab | a.
O conjunto P de regras da gramática G = ({S, A}, {a, b}, P, S),
ilustrado anteriormente, pode ser simplificada como:
S → AA
A → AAA | bA | Ab | a
COMPUTAÇÃO
Gramáticas Livres de Contexto
O processo fundamental para a geração de uma string é a
aplicação de regras. A aplicação de uma regra A → w sobre um
string uAv ∈ {V ∪ Σ} ∗ , produz a string uwv.
Os prefixo u e o sufixo v definem o contexto em que a regra é
aplicada.
Uma gramática livre de contexto é aquela em que os prefixos
e sufixos não definem restrições sobre quando e onde a regra
pode ser aplicada.
COMPUTAÇÃO
Gramáticas Livres de Contexto
Uma string w ∈ {V ∪ Σ} ∗ é derivada de v ∈ {V ∪ Σ} ∗ , se existe
uma sequência finita de aplicações de regras que transformam
v em w:
v ⇒ w1 ⇒ w2 ⇒ . . . ⇒ wn = w
Essa derivação pode ser representada por v ∗⇒= w.
Seja G = (V, Σ, P, S) uma gramática livre de contexto e v ∈ {V
∪ Σ} ∗ . O conjunto de strings deriváveis de v é definido como:
• Base: v é derivável de v;
• Passo: Se u = xAy é derivável de v e A → w ∈ P, então xwy é
derivável de v.
COMPUTAÇÃO
Gramáticas Livres de Contexto
Uma derivação da string ababaa na gramática G = ({S, A}, {a,
b}, P, S) com o conjunto P de regras
S → AA
A → AAA | bA | Ab | a
pode ser escrita como
S ⇒ AA
⇒ aA
⇒ abA
⇒ abAAA
⇒ abaAA
⇒ ababAA
⇒ ababaA
⇒ ababaa
COMPUTAÇÃO
Gramáticas Livres de Contexto
A derivação de uma string pode também ser visualizada como
uma árvore.
Seja G = (V, Σ, P, S) uma gramática livre de contexto e S ∗⇒=
w uma derivação de G. A árvore de derivação de S ∗⇒= w,
pode ser construída da seguinte forma:
1. Inicia a árvore com raiz S
2. Se A → x1x2 ... xn com xi ∈ {V ∪ Σ} é a regra de derivação
aplicada à string uAv, então adicione x1, x2, ... , xn como
nós filhos de A na árvore
3. Se A → λ é a regra de derivação aplicada à string uAv,
então adicione λ como filho de A na árvore
COMPUTAÇÃO
Gramáticas Livres de Contexto
pode ser visualizada como Árvore
S ⇒ AA
⇒ aA
⇒ abA
⇒ abAAA
⇒ abaAA
⇒ ababAA
⇒ ababaA
⇒ ababaa
COMPUTAÇÃO
Autômato Finito Determinístico e Não-Determinístico
Os Autômatos Finitos que vimos até agora funcionam da
seguinte forma: quando a máquina está em um dado estado e
lê o próximo símbolo de entrada, sabemos qual será o próximo
estado, está determinado. Chamamos isso, portanto, de
computação determinística.
Segundo Messis(2013), “em um AFND, autômato finito não-
determinístico, várias escolhas podem existir para o próximo
estado em qualquer ponto”.
Em um AF, autômato finito, um estado pode ter zero, uma ou
várias setas saindo para cada símbolo do alfabeto.
COMPUTAÇÃO
Autômato de Pilha
Analogamente às Linguagens Regulares, a Classe das
Linguagens Livres do Contexto pode ser associada a um
formalismo do tipo autômato, denominado Autômato com
Pilha. O Autômato com Pilha é análogo ao Autômato Finito
que reconhece as Linguagens Livre de Contexto, basicamente
um AFNDε incluindo uma pilha como memória auxiliar e a
facilidade de não-determinismo.
A pilha é independente da fita de entrada e não possui limite
máximo de tamanho ("infinita"). Estruturalmente, sua principal
característica é que o último símbolo gravado é o primeiro a
ser lido (LIFO last in first out).
COMPUTAÇÃO
Autômato de Pilha
Ao contrário da fita de entrada, a pilha