Baixe o app para aproveitar ainda mais
Prévia do material em texto
LINGUAGENS FORMAIS E AUTÔMATOS Marcelo Guerra PROFESSOR Marcelo Roberto Bastos Guerra Vale marceloguerra@ufersa.edu.br DCEN sala 31. Horário de atendimento: a combinar Mestre em Engenharia Elétrica na UFRN Doutorando no PPGEEc – UFRN Todo o material do curso foi cedido pela professora Mara Bonates. Adaptações feitas pelo professor Marcelo Guerra ESTRUTURA DO CURSO Aulas teóricas Aulas expositivas. Resolução de exercícios. Avaliações Provas escritas. Trabalhos de implementação. Nota dos trabalhos não ultrapassam 30% da nota da unidade. Resolução de exercícios em aula. Créditos extras. OBJETIVOS Estudar classes de linguagens e seus respectivos formalismos reconhecedores, os autômatos. Estudar linguagens em ordem crescente de complexidade e suas aplicações. Entender os modelos fundamentais de computação e suas propriedades. Provocar curiosidade e interesse em aspectos mais abstratos (e gerais) da Ciência da Computação EMENTA Linguagens Regulares Autômatos Finitos Linguagens Livres de Contexto Autômatos com Pilha Máquinas de Turing O Problema da Parada da Máquina de Turing Hierarquia das Classes de Linguagem BIBLIOGRAFIA Hopcroft, J.E.; Ullman, J.D, Introdução à Teoria de Autômatos, Linguagens e Computação. Segunda Edição, Ed. Campus/Elsevier. 2003. BIBLIOGRAFIA Blauth, P. M. Linguagens Formais e Autômatos. Série Livros Didáticos 3, Edição 2, UFRGS, 1998. BIBLIOGRAFIA Harry Lewys & Christos Papadimitriou, Elementos de Teoria da Computação, Editora Bookman, Porto Alegre, 2a. ed., 2000. BIBLIOGRAFIA Michael Sipser, Introdução à Teoria da Computação, Editora Thompson, Tradução 2a. ed., 2007. Rosa, J. L. G. Linguagens Formais e Autômatos. Editora LTC, 2010. Acióly B. M.; Bedregal B. R., Introdução à Teoria das linguagens formais, dos autômatos e da computabilidade, Editora UnP, 1a. ed., 2002. MOTIVAÇÃO O que podemos fazer com os computadores? O que jamais poderemos fazer com eles? Como encontrar respostas a essas perguntas? INTRODUÇÃO Alan Turing foi um grande matemático, lógico e criptoanalista. pioneiro na inteligência artificial e na ciência da computação. A homossexualidade de Turing resultou em um processo criminal em 1952 Morreu em 1954, algumas semanas antes de seu aniversário de 42 anos Em 10 de setembro de 2009, após uma campanha de internet, o primeiro-ministro britânico Gordon Brown fez um pedido oficial de desculpas público, em nome do governo britânico INTRODUÇÃO Alan Turing estudou uma máquina abstrata que tinha todas as características dos computadores atuais. O objetivo era descrever o limite entre o que uma máquina de computação podia fazer e aquilo que ela não podia fazer. As conclusões de Turing se aplicam não apenas às suas máquinas de Turing abstratas, mas também às máquinas reais de hoje. INTRODUÇÃO A Teoria dos Autômatos é o estudo dos dispositivos de computação abstratos, ou “máquinas”. INTRODUÇÃO Teoria da computação A importância da teoria para a prática, em qualquer ciência é imensa. Se entendermos por computação tudo o que um computador pode realizar, devemos primeiro entender o que um computador é. A resposta poderia ser dada em termos de hardware e tecnologia, mas não podemos nos limitar à tecnologia do momento. Isto nos levará, irremediavelmente, a definir uma noção abstrata de computador. A construção de modelos é essencial em qualquer disciplina científica. INTRODUÇÃO Teoria da Computação: Fundamenta diversas aplicações computacionais, tais como: Software de verificação de circuitos digitais Analisadores léxicos Motores de busca na Web Software para verificar sistemas com número de estados finito, como protocolos para comunicações Sub-áreas: Teoria das linguagens formais Teoria da computabilidade e os limites da computação INTRODUÇÃO Teoria da Computação e os limites da computação: A Teoria da Computação nos permite deduzir se temos a chance de, ao nos depararmos com um problema, sermos capazes de resolve-lo, ou se teremos de descobrir algum modo de contornar o problema intratável. Encontrar uma aproximação, uma heurística ou limitar o período de tempo de execução do programa. LINGUAGENS FORMAIS TEORIA DAS LINGUAGENS FORMAIS Linguagens formais são mecanismos formais para representação e especificação de linguagens, baseados na chamada Teoria da Computação. As representações podem ser feitas por: Reconhecedores: dispositivos formais que servem para verificar se uma sentença pertence ou não à determinada linguagem. Autômatos. Geradores: dispositivos formais que permitem a geração sistemática de todas as sentenças de uma linguagem. Gramáticas. LINGUAGENS FORMAIS Em nossa linguagem natural usamos letras, palavras e sentenças. Grupos de letras constituem uma palavra e grupos de palavras constituem uma sentença. Mas, nem toda concatenação de letras forma uma palavra, nem toda sequência de palavras uma sentença. A situação também se verifica para as linguagens de programação, na qual certos agrupamentos de palavras chave são um comando e algumas sequências de comandos são programas. LINGUAGENS FORMAIS É necessária uma teoria geral que unifique todos esses casos. Definição de uma estrutura onde a decisão de quando uma cadeia de unidades constitui uma unidade maior válida seja baseada na aplicação de regras explicitamente definidas. LINGUAGENS FORMAIS Em linguagens naturais não podemos dar regras para descrever todas as frases, pois nos permite construir frases sem sentido. Ex: <artigo><substantivo><verbo> => “o gato late” É difícil estabelecer quais frases fazem sentido, porque dependem de nossa habilidade para interpretar metáforas poéticas. LINGUAGENS FORMAIS Isto não acontece com as linguagens de programação, pois elas são formais. O compilador de uma linguagem de programação é um procedimento que analisa a corretude de uma seqüência de símbolos e determina se ela constitui um programa válido ou não. Assim, o compilador não procura saber o que o programa faz, mas se ele está corretamente escrito. LINGUAGENS FORMAIS A palavra “formal” nos diz que todas as regras para a linguagem são explicitamente declaradas em termos das cadeias de símbolos que podem ocorrer nela. Sentenças são consideradas como meros símbolos e não como expressões de idéias na mente humana. CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS Alfabeto É um conjunto não-vazio e finito de símbolos. Representação: Σ (sigma) Exemplos: Σ = {0,1}, o alfabeto binário. Σ = {a,b,...,z}, o alfabeto de todas as letras minúsculas. CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS String, cadeia ou palavra É uma seqüência finita de símbolos escolhidos de algum alfabeto. Representação: letras minúsculas do inicio do alfabeto para representar elementos do alfabeto (a,b,c...). letras minúsculas do final do alfabeto para indicar nomes de cadeias (...w,x,y,z). Exemplos: Se o alfabeto for Σ = {a,b} então w = abab e z = aaabba são cadeias sobre Σ. CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS A cadeia vazia é a cadeia com zero ocorrências de símbolos. Representação: ε (Épsilon) ou λ (Lambda). A concatenação de duas cadeias w e v, é denotado por wv. Se w=a1...an e v=b1...bm então wv=a1...anb1...bm. O comprimento de uma cadeia w, denotado por |w|, é o número de símbolos que figuram na cadeia. Exemplos: |abba|= 4 | ε |=0. CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS Potências de um alfabeto Se Σ é um alfabeto, podemos expressar o conjunto de todas as cadeias de um certo comprimento desse alfabeto, usando uma notação exponencial Σk. Σ0 = { ε }, independente de qual alfabeto seja Σ. Seja Σ= {0,1}, Σ1 = {0,1}, Σ2={00,01,10,11}, Σ3= {000,001,010,011,...,111}. CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS Fecho Estrela O fecho estrela de um alfabeto Σ, denotado por Σ*, é o conjunto de todas as cadeias (finitas) sobre Σ. Σ* = Σ0 Σ1 Σ2 Σ3 ... Exemplo: {0,1}* = { ε, 0, 1, 00, 01, 10, 11, 000,... } CONCEITOS ELEMENTARES DA TEORIA DOS AUTÔMATOS Fecho positivo O conjunto Σ* sempre contém ε. O fecho estrela de Σ sem a cadeia vazia é denominado fecho positivo do alfabeto Σ, e é denotado por Σ+. Desse modo, duas equivalências são apropriadas: Σ+ = Σ1 Σ2 Σ3 ... Σ* = Σ+ {ε} LINGUAGENS Um subconjunto qualquer de Σ* pode ser visto como uma linguagem sobre o alfabeto Σ. Uma cadeia w numa linguagem L, isto é, w L, será chamada sentença de L. Exemplo: seja Σ = {a,b}. Então Σ* = {ε, a, b, aa, ab, ba, bb, ...}. O conjunto {a, aa, aab} é uma linguagem sobre Σ. LINGUAGENS Linguagem Finita Quantidade finita de palavras. Linguagem Infinita Exemplo: dado o alfabeto = {a, b}, o conjunto L = {anbn | n ≥ 0} é uma linguagem L sobre o alfabeto Σ. OBS: As cadeias aabb e aaaabbbb são palavras de L, mas a cadeia abb não está em L. LINGUAGENS Exemplos de linguagens: Português: coleção de palavras válidas na língua. C: programas válidos são um subconjunto dos strings possíveis que podem ser formados a partir do alfabeto da linguagem. Linguagem de todos os strings que consistem em n 0’s seguidos por n valores 1, para algum n ≥ 0: {ε, 01, 0011, 000111, ...}. O conjunto de strings de 0’s e 1’s com um número igual de cada um deles: {ε, 01, 10, 0011, 0101, 1001,...}. A única restrição importante sobre o que pode ser uma linguagem é que todos os alfabetos são finitos. GRAMÁTICAS GRAMÁTICAS Para estudar linguagens matematicamente, precisamos de um mecanismo para descrevê-las. As gramáticas são uma poderosa ferramenta para definir linguagens. Uma gramática para a língua portuguesa nos diz se uma sentença, em particular, é bem formada ou não. <oração> : <sujeito> <predicado> <sujeito> : <artigo><substantivo> <predicado> : <verbo><complemento> Sentenças como: “um cão corre na praia” e “uma menina caminha lentamente” são bem formadas. GRAMÁTICA Definição: Uma gramática G é definida como uma quádrupla G = < V, T, S, P >, onde: V é um conjunto finito de objetos, chamados variáveis. T é um conjunto finito de objetos, disjunto de V, chamados símbolos terminais. S V é um símbolo especial, chamado variável de início. P é um conjunto finito de produções. GRAMÁTICA Considere a gramática G = < {S}, {a,b}, S, P > onde P é dado por: S aSb S ε O principal na gramática são as regras de produção. Elas especificam como a gramática transforma uma cadeia em outra, e através disso elas definem uma linguagem associada à gramática. GRAMÁTICA Assumiremos que todas as produções são da forma: x y onde x é um elemento de (V T)+ e y está em (V T)*. GRAMÁTICA As produções são aplicadas como segue: dada uma cadeia da forma: w uxv dizemos que a produção x y é aplicável a esta cadeia, e podemos usá-la para trocar x por y, obtendo assim, a nova cadeia z uyv Neste caso, dizemos que w deriva z, denotado por w z. GRAMÁTICA G = <{S}, {a,b}, S, P>, onde P é dado por: S aSb S ε Então S aSb aaSbb aabb. Logo, podemos escrever: S aabb. A cadeia aabb é uma sentença na linguagem gerada por G, enquanto aaSbb é uma forma sentencial.
Compartilhar