Baixe o app para aproveitar ainda mais
Prévia do material em texto
27/09/2012 1 LINGUAGENS ENUMERÁVEIS RECURSIVAMENTE E SENSÍVEIS AO CONTEXTO INTRODUÇÃO À TEORIA DA COMPUTAÇÃO 1 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � Correspondência entre as classes de linguagens, gramáticas e reconhecedores 2 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Gramática Reconhecedor Tipo 0: enumerável recursivamente irrestrita máquinas de Turing Tipo 1: sensível ao contexto sensível ao contexto autômato limitado linearmente Tipo 2: livre do contexto livre do contexto autômatos com pilha Tipo 3: regular regular autômatos finitos Máquina de Turing com Fita Limitada 27/09/2012 2 Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � Para as linguagens Regulares (tipo 3) foram estudados os formalismos: � Operacional ou reconhecedor: Autômato Finito � Axiomático ou gerador – Gramática Regular � Denotacional – Expressão Regular � Para as linguagens Livres de Contexto (tipo 2) foram estudados os formalismos: � Operacional ou reconhecedor: Autômato com Pilha � Axiomático ou gerador – Gramática Livre de Contexto 3 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � Para as Linguagens Sensíveis ao Contexto (tipo 1) serão estudados os formalismos: � Operacional ou reconhecedor: Máquina de Turing com Fita Limitada � Axiomático ou gerador – Gramática Sensível ao Contexto � Para as Linguagens Enumeráveis Recursivamente (tipo 0) serão estudados os formalismos: � Operacional ou reconhecedor: Máquina de Turing � Axiomático ou gerador – Gramática Irrestrita 4 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 3 Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � Como a Máquina de Turing será usada como um formalismo reconhecedor das Linguagens Sensíveis ao Contexto e Enumeráveis Recursivamente, vamos estudar Máquina de Turing de uma forma geral 5 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � Ciência da Computação é o conhecimento sistematizado relativo à computação. � Sua origem é remota, tendo exemplos : � Na antiga Grécia (século III a.C., no desenho de algoritmos por Euclides) e � Na Babilônia (com estudos sobre complexidade e reducibilidade de problemas) 6 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 4 Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto � No início do século XX, diversas pesquisas foram desenvolvidas com o objetivo de definir um modelo computacional suficientemente genérico, capaz de implementar qualquer "função computável“ � Em 1936, Alan Turing propôs um modelo conhecido como Máquina de Turing. 7 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Alan Turing � Alan Mathison Turing � Matemático, lógico, criptoanalista e cientista da computação � Nasceu em Londres, no dia 23 de junho de 1912 8 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 5 Alan Turing � Um dos principais prêmios internacionais da área de Computação leva o seu nome, o ACM Turing Award � Este ano (2012), é celebrado o Ano Internacional de Turing em comemoração ao centenário de seu nascimento � Com 24 anos de idade, apresentou uma formalização do conceito de algoritmo e computação � Máquina de Turing � Contribuição imprescindível para o desenvolvimento do computador moderno 9 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Atualmente, a Máquina de Turing é aceita como uma formalização de um procedimento efetivo ( algoritmo ou função computável), � Isto é, uma seqüência finita de instruções, as quais podem ser realizadas mecanicamente, em um tempo finito � Ainda em 1936, Alonzo Church apresentou a Hipótese de Church: � Afirma que qualquer função computável pode ser processada por uma Máquina de Turing, ou seja, existe um procedimento expresso na forma de uma Máquina de Turing capaz de processar qualquer função. 10 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 6 Máquina de Turing � Contudo, como a noção intuitiva de procedimentos não é matematicamente precisa, é impossível demonstrar formalmente se a Máquina de Turing é, efetivamente, o mais genérico dispositivo de computação � Entretanto, foi mostrado que todos os demais modelos propostos possuem, no máximo, a mesma capacidade computacional da Máquina de Turing, o que reforça a Hipótese de Church 11 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Enumeráveis Recursivamente � As Linguagens Enumeráveis Recursivamente ou Tipo 0 são aquelas que podem ser reconhecidas por uma Máquina de Turing. � Considerando que, segundo a Hipótese de Church, a Máquina de Turing é o mais geral dispositivo de computação, então a Classe das Linguagens Enumeráveis Recursivamente representa o conjunto de todas as linguagens que podem ser reconhecidas mecanicamente e em um tempo finito. 12 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 7 Linguagens Enumeráveis Recursivamente � As Linguagens Enumeráveis Recursivamente ou Tipo 0 são aquelas que podem ser reconhecidas por uma Máquina de Turing. � Considerando que, segundo a Hipótese de Church, a Máquina de Turing é o mais geral dispositivo de computação, então a Classe das Linguagens Enumeráveis Recursivamente representa o conjunto de todas as linguagens que podem ser reconhecidas mecanicamente e em um tempo finito. 13 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Enumeráveis Recursivamente � O estudo das Linguagens Enumeráveis Recursivamente ou Tipo 0, pode ser abordado através de formalismos: � Operacional ou reconhecedor (máquina): � Máquina de Turing: modelo formal de procedimento efetivo, algoritmo ou função computável � Axiomático ou gerador (gramática): � Gramática Irrestrita: gramática que não possui qualquer restrição sobre a forma das produções 14 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 8 Linguagens Sensíveis ao Contexto � As Linguagens Sensíveis ao Contexto ou Tipo 1 estão contidas propriamente nas Enumeráveis Recursivamente 15 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Fonte: (Menezes,1999) Linguagens Sensíveis ao Contexto � O estudo das Linguagens Sensíveis ao Contexto ou Tipo 1 , pode ser abordado através de formalismos: � Operacional ou reconhecedor (máquina): � Máquina de Turing com Fita Limitada: trata-se de uma Máquina de Turing com limitação no tamanho da fita a qual, portanto, é finita � Axiomático ou gerador (gramática): � Gramática Sensível ao Contexto: o termo "sensível ao contexto" deriva do fato de que o lado esquerdo das produções da gramática pode ser uma palavra de variáveis ou terminais, definindo um "contexto" de derivação 16 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 9 Máquina de Turing � A Máquina de Turing para ser considerada como um modelo formal de procedimento efetivo, algoritmo ou função computável deve satisfazer às seguintes propriedades, entre outras: � A descrição do algoritmo deve ser finita e � Deve consistir de passos: � discretos; � executáveis mecanicamente; � em um tempo finito. 17 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � O modelo proposto por Alan Turing (1936), conhecido como Máquina de Turing, consiste de 3 partes: � Fita. Usada simultaneamente como dispositivode entrada, saída e memória de trabalho; � Unidade de Controle. Reflete o estado corrente da máquina. Possui uma unidade de leitura e gravação (cabeça da fita) a qual acessa uma célula da fita de cada vez e movimenta-se para a esquerda ou direita; � Programa ou Função de Transição. Função que comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina. 18 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 10 Máquina de Turing � A fita é finita à esquerda e infinita à direita, sendo dividida em células, onde cada uma armazena um símbolo. � Os símbolos podem pertencer � Ao alfabeto de entrada, � ao alfabeto auxiliar ou ainda, � ser "branco" ou � "marcador de início de fita” 19 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Inicialmente, a palavra a ser processada (ou seja, a informação de entrada para a máquina) ocupa as células mais à esquerda, após o marcador de início de fita, ficando as demais espaços com "branco" 20 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ b b a c β β … Unidade de Controle Cabeça da Fita Entrada Branco Marcador de iníco de fita q0 27/09/2012 11 Máquina de Turing � A unidade de controle possui um número finito e predefinido de estados � A cabeça da fita lê o símbolo de uma célula de cada vez e grava um novo símbolo. � Após a leitura/gravação, a cabeça move uma célula para a direita ou esquerda. O símbolo gravado e o sentido do movimento são definidos pelo programa. � O programa é uma função que, dependendo do estado corrente da máquina e do símbolo lido, determina o símbolo a ser gravado, o sentido do movimento da cabeça e o novo estado. 21 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Uma Máquina de Turing é uma 8-upla, onde: � ∑ alfabeto de símbolos de entrada; � Q conjunto de estados possíveis da máquina o qual é finito; � δ programa ou função de transição: � δ: Q (∑ ∪ V ∪ { β, ⊛}) → Q X (∑ ∪ V ∪ {β, ⊛}) {E,D}, a qual é parcial � q0 estado inicial da máquina tal que q0 é elemento de Q; � F conjunto de estados finais tal que F está contido em Q; � V alfabeto auxiliar (pode ser vazio); � Β símbolo especial branco; � ⊛ símbolo ou marcador de início da fita 22 Profa. Ellen Souza - https://sites.google.com/site/ellenuast M = (∑ , Q, δ, q0, F, V, β, ⊛ ) 27/09/2012 12 Máquina de Turing � O símbolo de início de fita sempre ocorre exatamente uma vez e na célula mais à esquerda da fita, auxiliando na identificação de que a cabeça da fita se encontra na célula mais à esquerda da fita. � A função programa, considera o estado corrente e o símbolo lido da fita para determinar o novo estado, o símbolo a ser gravado e sentido de movimento da cabeça onde esquerda e direita são representados por E e D, respectivamente 23 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Representação da função programa da Máquina de Turing como um grafo 24 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 13 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. 25 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � As condições de parada são as seguintes: � A máquina assume um estado final: a máquina para e a palavra de entrada é aceita; � A função programa é indefinida para o argumento (símbolo lido e estado corrente): a máquina para e a palavra de entrada é rejeitada; � 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 para e a palavra de entrada é rejeitada. 26 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 14 Máquina de Turing � Suponha que M é uma Máquina de Turing: � ACEITA(M) ou L(M): conjunto de todas as palavras de ∑* aceitas por M; � REJEITA(M): conjunto de todas as palavras de ∑* rejeitadas por M; � LOOP(M): conjunto de todas as palavras de ∑* para as quais M fica processando indefinidamente. 27 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Resumindo: 28 Profa. Ellen Souza - https://sites.google.com/site/ellenuast A aceitação de uma cadeia pela Máquina de Turing acontece quando o estado final é atingido independente de onde a cabeça está na fita. Se a Máquina de Turing para em algum estado não final ou simplesmente entrar em “loop” infinito, a cadeia não é aceita. 27/09/2012 15 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � Considere a linguagem: L1 = { an bn | n ≥ 0 } � A Máquina de Turing: M1 = ({ a, b }, { q0, q1, q2, q3, q4 }, δ1, q0, { q4 }, { A, B }, β , ⊛), onde δ1 é: 29 Profa. Ellen Souza - https://sites.google.com/site/ellenuast δ1 ⊛ a b A B β q0 (q0, ⊛, D) (q1, A, D) (q3, B, D) (q4, β, D) q1 (q1, a, D) (q2, B, E) (q1, B, D) q2 (q2, a, E) (q0, A, D) (q2, B, E) q3 (q3, B, D) (q4, β, D) q4 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento 30 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 16 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � Apresente a sequência do processamento da Máquina de Turing para a entrada w = aabb � δ1 (q0, ⊛)=(q0, ⊛, D) � δ1 (q0, a)=(q1, A, D) 31 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ a a b b β β … q0 ⊛ a a b b β β … q0 ⊛ A a b b β β … q1 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q1, a)=(q1, a, D) � δ1 (q1, b)=(q2, B, E) 32 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A a b b β β … q1 ⊛ A a B b β β … q2 ⊛ A a b b β β … q1 27/09/2012 17 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q2, a)=(q2, a, E) � δ1 (q2, A)=(q0, A, D) 33 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A a B b β β … q2 ⊛ A a B b β β … q0 ⊛ A a B b β β … q2 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q0, a)=(q1, A, D) � δ1 (q1, B)=(q1, B, D) 34 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A A B b β β … q1 ⊛ A A B b β β … q1 ⊛ A a B b β β … q0 27/09/2012 18 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q1, b)=(q2, B, E) � δ1 (q2, B)=(q2, B, E) 35 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A A B B β β … q2 ⊛ A A B b β β … q1 ⊛ A A B B β β … q2 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q2, A)=(q0, A, D) � δ1 (q0, B)=(q3, B, D) 36 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A A B B β β … q0 ⊛ A A B B β β … q2 ⊛ A A B B β β … q3 27/09/2012 19 Máquina de Turing � Exemplo 1: Máquina de Turing - Duplo Balanceamento � δ1 (q3, B)=(q3, B, D) � δ1 (q3, β)=(q4, β, D) 37 Profa. Ellen Souza - https://sites.google.com/site/ellenuast ⊛ A A B B β β … q3 ⊛ A A B B β β … q4 ⊛ A A B B β β … q3 Máquina de Turing � Algumas variações sobre a Máquina de Turing � Diferentes símbolos. � Alguns autores utilizam osímbolo ⎕ para representar o espaço em branco (β) � O movimento de direita (D) e esquerda (E) podem ser representador pela letra (R) Right = Direita e (L) Left = Esquerda � Inexistência de marcador de início. Algumas máquinas não possuem o símbolo de marcador de início de fita (⊛). Neste caso, o símbolo branco (⎕ ou β ) pode ser utilizado para entrada vazia ou nenhum símbolo, onde a célula mais esquerda contém o primeiro símbolo da palavra de entrada. 38 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 20 Máquina de Turing � Algumas variações sobre a Máquina de Turing � Cabeça de Fita não se move em uma Leitura/Gravação. A movimentação da cabeça da fita tem como objetivo facilitar a especificação da função programa, bem como reduzir o número de transições necessárias. � Estado Final de Rejeição. Pode der definido para explicitar a condição de parada com rejeição de entrada. Facilita a compreensão da lógica da função programa. 39 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Máquina de Turing � Exercício 1: Máquina de Turing - Duplo Balanceamento � Apresente a sequência do processamento da Máquina de Turing para a entrada w = aaab 40 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 21 Máquina de Turing � Exercício 3: Dada a Máquina de Turing que aceita a linguagem denotada pela Expressão Regular ER = 0*, definida como: � M = ({ q0, q1 }, {0}, { 0, ⎕}, δ, q0, { q1 }, onde δ é: � δ(q0,0) = (q0,0,R) e � δ(q0,⎕) = (q1,⎕,R) � Apresente a sequência do processamento da Máquina de Turing para uma entrada válida. � Apresente a sequência do processamento da Máquina de Turing para uma entrada inválida. � Utilize a ferramenta JFLAP para construir o autômato e reconhecer cadeias 41 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Modelos Equivalentes a Máquina de Turing � Uma das razões para considerar a Máquina de Turing como o mais geral dispositivo de computação é o fato de que todos os demais modelos e máquinas propostos, bem como diversas modificações da Máquina de Turing, possuem, no máximo, o mesmo poder computacional da Máquina de Turing 42 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 27/09/2012 22 Modelos Equivalentes a Máquina de Turing � As modificações apresentadas a seguir são freqüentemente usadas. �Autômato com Múltiplas Pilhas �Máquina de Turing Não-Derminística �Máquina de Turing com Fita Infinita à Esquerda e à Direita. �Máquina de Turing com Múltiplas Fitas �Máquina de Turing Multidimensional �Máquina de Turing com Múltiplas Cabeças �Combinações de Modificações sobre a Máquina de Turing 43 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Pesquisa � Quais foram as contribuições de Alan Turing para a Ciência da Computação? � Elaborar texto com, no máximo, 30 linhas � Fonte arial 10, sem espaçamento e tamanho de margem normal � Entregar dia 15/05 � Vale 0,5 ponto para a nota da 1a VA � Indicar as fontes de pesquisa 44 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Textos (ou parte de textos) copiados não serão avaliados!
Compartilhar