Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Slides/LFA.2015.2.Aula01.Introdu��o.pdf Aula 01 - Introdução Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 1 - Seções 1.1 e 1.5 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 0 - Seção 0.1 Introdução Autômatos Computabilidade Complexidade Quais são as capacidades e limitações fundamentais dos computadores? Introdução ● Década de 1930 ● Matemáticos ● Antes da existência dos computadores Teoria da complexidade ● Alguns problemas são simples ○ Ordenação ● Outros são complexos ○ Escalonamento de aulas em uma universidade ○ 1000 aulas: o tempo para achar o melhor escalonamento pode levar séculos ○ Número com 500 dígitos: fatorar leva todo o tempo de vida do universo O que torna alguns problemas computacionalmente difíceis e outros fáceis? Teoria da complexidade ● Não sabemos a resposta! ● Mas temos um esquema para classificar problemas conforme sua dificuldade ● Várias opções... ○ Alterar o problema (ou aquele aspecto) ○ Contentar-se com uma solução menos do que perfeita ○ Alguns problemas só são difíceis no pior caso ● Ex: criptografia Teoria da computabilidade ● Alguns problemas não podem ser resolvidos por computadores ○ Ex: um enunciado matemático é verdadeiro ou falso? ● Problemas solúveis vs insolúveis Teoria dos autômatos ● Definições e propriedades de modelos matemáticos de computação ● Autômatos são abstrações matemáticas que ajudam a entender este modelo ○ Tem implicações e aplicações práticas Autômatos e Linguagens Autômatos e Linguagens ● Conceitos centrais ● Alfabeto: conjunto finito, não vazio, de símbolos ○ Símbolos = membros de um alfabeto ● Ʃ (sigma) ou Γ (gamma) ○ Ex: Ʃ = {0,1} ○ Ʃ = {a,b,c,...,z} ○ Ʃ = conjunto de caracteres ASCII Autômatos e Linguagens ● Cadeia/string sobre um alfabeto ○ Sequência finita de símbolos daquele alfabeto ○ Geralmente escritos um seguido do outro e não separados por vírgulas ● Ex: 01001, if, then, while ● Se w é uma cadeia sobre Ʃ, o comprimento de uma cadeia |w| é o número de símbolos que ela contém ○ Estritamente, é o número de posições que conta ● Cadeia de comprimento zero ○ ε (epsilon minúsculo) Autômatos e Linguagens ● Se w tem comprimento n ○ w = w1w2...wn, onde cada wi ∈ Ʃ ● Reverso de w = wR ○ Cadeia obtida escrevendo-se w na ordem inversa ○ wnwn-1...w1 ● z é uma subcadeia/substring de w se z aparece consecutivamente dentro de w ○ cad é uma subcadeia de abracadabra Autômatos e Linguagens ● Cadeia x de comprimento m ● Cadeia y de comprimento n ● Concatenação de x e y, escrito xy é: ○ x1x2...xmy1y2...yn ○ |xy|=m+n ○ xx...x = xk ○ wε=εw=w Autômatos e Linguagens ● Potências de um alfabeto ● Ʃk ○ Conjunto de cadeias de comprimento k, e o símbolo de cada um deles está em Ʃ ● Ʃ0={ε} (independente do alfabeto) ● Se Ʃ={0,1} ○ Ʃ1={0,1} ○ Ʃ2={00,01,10,11} ○ Ʃ3={000,001,010,011,100,101,110,111} ○ Ʃ*=conjunto de todas as cadeias sobre um alfabeto ○ Ʃ*= Ʃ0 ∪ Ʃ1 ∪ Ʃ2 ∪ ... ○ Ʃ+= Ʃ1 ∪ Ʃ2 ∪ ... ○ Ʃ* = Ʃ+ ∪ {ε} Linguagens ● Um conjunto de cadeias escolhidas de um alfabeto ○ Se Ʃ é um alfabeto ○ L ⊆ Ʃ* ○ L é uma linguagem sobre Ʃ ■ E sobre qualquer alfabeto que contenha Ʃ ● Outras conclusões ○ Ʃ* é uma linguagem para qualquer alfabeto Ʃ ○ ∅ (linguagem vazia) é uma linguagem sobre qualquer alfabeto ○ {ε} é uma linguagem sobre qualquer alfabeto Linguagens e Problemas ● O termo “linguagem” pode parecer estranho ○ Mas linguagens comuns podem ser vistas como um conjunto de cadeias ○ Ex: português/alfabeto latino, grego/alfabeto grego ○ Ex: C/ASCII ● Exemplos mais abstratos ○ Ex: Linguagens de todas as cadeias que consistem de n 0’s seguidos por n 1’s ○ Ex: Conjunto de cadeias com número igual de 0’s e 1’s Linguagens ● Linguagens podem possuir infinitas palavras, mas alfabetos são finitos ● Problemas: na teoria dos autômatos, um problema é a decisão sobre se uma dada cadeia/palavra é parte de uma linguagem particular ○ Se Ʃ é um alfabeto, e L é uma linguagem sobre Ʃ, então um problema (formal) é: ■ Dada uma string w em Ʃ*, decidir se w pertence ou não a L ● Também enquadra a noção coloquial de problema Linguagens e Problemas ● Linguagens podem descrever situações reais ○ Ex: uma linguagem que descreve os caminhos entre minha casa e o trabalho: ■ DDEEFFDED (a cada esquina) ■ Há vários caminhos (cadeias) ○ Problema: encontrar o caminho mais curto ■ Ou: dado um caminho, é o mais curto? ■ Ou: encontre todos os caminhos até a minha casa ● Em termos da teoria da computação, são a mesma coisa ○ A dificuldade – em essência – é a mesma Linguagens e Problemas ● Porém em alguns casos problemas são mais do que linguagens ● Ex: Dada uma string ASCII ○ Decidir se é ou não um elemento de Lc (conjunto de programas válidos em C) ● Mas por trás: ○ Compilador precisa fazer uma tarefa complexa ○ Produz uma árvore de análise sintática ○ Entradas em uma tabela de símbolos ○ Transformar um programa C em código-objeto ○ Outras tarefas de compiladores ○ Vai além de responder “sim” ou “não” sobre a validade de um programa Linguagens e problemas ● Problemas são úteis à teoria da complexidade ○ Técnicas podem provar que alguns problemas não podem ser resolvidos facilmente ● O termo preferido depende do ponto de vista ○ Se estamos interessados nas palavras em si: linguagem ○ Se estamos mais interessados nas coisas que representam – semântica: problema ● Para a teoria computacional, estamos interessados em saber os limites de complexidade ○ Encontrar uma solução para a versão linguagem (sim/não) é tão difícil quanto a versão “resolva isso” ● É muito útil pensar em linguagens ○ Ao estudar teoria da computação Linguagens e problemas ● Definindo linguagens ● Formador de conjuntos ○ {w | algo sobre w} ● Exs: ○ {w | w consiste em um número igual de 0’s e 1’s} ○ {w | w é um número inteiro binário primo} ○ {w | w é um programa em C sintaticamente correto} ○ {0i1j | 0 ≤ i ≤ j} Fim Aula 01 - Introdução Slides/LFA.2015.2.Aula02.Aut�matos Finitos.pdf Aula 02 - Autômatos finitos Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 2 - Seções 2.1 e 2.2 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.1 Autômatos finitos ● Definição informal ○ Conjunto de estados: cada um “lembra” o que já foi feito na história de um sistema ○ Conjunto de transições: movimentos possíveis de um estado para outro ○ Controle: dispositivo hipotético que lê uma entrada externa e move de um estado para outro ○ Existem transições que não mudam o estado ○ Exemplo: geladeira Autômatos finitos Fechada Aberta Alarme AbrirFechar 10 seg 20 seg 10 seg 20 seg Autômatos finitos ● Exercício: Locadora de vídeo Disponível Empréstimo Reservado Alugado Atrasado Devolução Data passou Devolução com multa Reserva Desistência Empréstimo reservado Reserva Autômatos finitos ● Aplicações ○ Avaliar um determinado processo/protocolo em busca de erros/falhas ○ Ex: e se eu fechar a porta com o alarme tocando? ○ Ex: e se eu reservar um filme atrasado? ○ Dependendo da implementação, pode resultar em erros Autômatos finitos determinísticos ● Definição Formal: DFA ● A=(Q,Ʃ,δ,q0,F) ○ Q=Conjunto finito de estados ○ Ʃ=Conjunto finito de símbolos de entrada ○ δ=Função de transição ○ q0=Um estado inicial (q0 ∈ Q) ○ F=Um conjunto de estados finais ou de aceitação (F ⊆ Q) Autômatos finitos determinísticos ● Função de transição ○ δ:Q × Ʃ → Q ● Define o funcionamento do autômato ● Ex. da geladeira: ○ Precisa ter estado inicial e de aceitação ○ Q = {Fechada, Aberta, Alarme} ○ Ʃ = {abrir, fechar, 10seg, 20seg} ○ q0 = Fechada ○ F = {Fechada} Autômatos finitos determinísticos ● δ(Fechada, abrir) = Aberta ● δ(Aberta, fechar) = Fechada ● δ(Aberta, 10seg) = Alarme ● δ(Alarme, 20seg) = Aberta Autômatos finitos determinísticos ● Em um DFA ○ As transições estão completas ○ Para todo estado e todo símbolo de entrada ○ Sempre sabe o que fazer ■ Definição de determinismo Autômatos finitos determinísticos ● Notações ○ Diagramas (Exemplo mais comum) ○ Tabelas de transição (Versão tabular do diagrama) ○ Representam completamente a 5-upla do autômato ● Diagrama de estado ○ Cada estado tem um nó correspondente ○ Estado inicial (seta apontando para o estado a partir do nada) ○ Estado de aceitação (círculo duplo) ○ Setas saindo de um estado para outro são transições ■ Representação visual da função δ Autômatos finitos determinísticos ● Ex:{x01y | x e y são quaisquer strings de 0’s e 1’s} q0 q1 q2 Início 1 0 0 1 0,1 Autômatos finitos determinísticos ● Versão tabular ○ Linhas correspondem aos estados ○ Colunas correspondem às entradas ○ Estado inicial é marcado com uma seta ○ Estados de aceitação são marcados com asterisco 0 1 → q0 q1 q0 q1 q1 q2 * q2 q2 q2 Autômatos finitos determinísticos ● Um DFA denota uma linguagem ○ Conjunto de todas as cadeias que aceita ○ L(M) = A ○ M reconhece A ○ M aceita A ○ Mesmo que um M não aceite nenhuma cadeia ■ Ele aceita a linguagem vazia ∅ Autômatos finitos determinísticos ● Quando o autômato recebe uma cadeia de entrada ○ Processa a cadeia e produz uma saída: aceita ou rejeita ○ Começa no estado inicial ○ Lê símbolos da esquerda para a direita ○ Após ler um símbolo, move-se de um estado para outro, de acordo com a função de transição ○ Quando lê o último símbolo, produz a saída ○ Se o autômato estiver em estado de aceitação, a saída será aceita ○ Caso contrário, será rejeitada ● Ex: abrir-fechar-abrir-fechar ● Ex: 0010111 Autômatos finitos determinísticos ● Definição formal de linguagem (indutiva) ○ δ(q,a)=p ○ δˆ(q,ε)=q ○ δˆ(q,w)= δ(δˆ(q,x),a) onde w=xa ○ L(A)={w| δˆ(qo,w) está em F} ● Definição: ○ Se L é L(A) para algum DFA ○ L é regular Autômatos finitos determinísticos ● Configuração instantânea ● w1w2w3...wkqwk+1wk+2...wn-2wn-1wn ● Ex: ○ Entrada: 001010011 ○ Configuração: 001[q3]010011 ○ Já leu 001, falta ler 010011 ○ Encontra-se no estado q3 ○ Próxima entrada é 0 Interpretando autômatos finitos ● Dado o seguinte autômato finito: q1 q2 q3 0 1 1 0 0,1 Interpretando autômatos finitos ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: 00000 0100 01000 010000 010101 11111 ● Quais dessas cadeias fazem parte da linguagem do autômato? ● Descreva informalmente a linguagem do autômato ● Descreva formalmente a linguagem do autômato Respostas ● Linguagens com um 1 pelo menos e um número par de zeros depois do último 1 (zero é par) ○ A = {w | w contém pelo menos um 1 e um número par de 0s segue o último 1} Interpretando autômatos finitos ● Dado o seguinte autômato finito: q1q0 q2 q3 1 1 00 1 1 00 Interpretando autômatos finitos ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: 0101 0110 1001 1111 1 11100 ● Quais dessas cadeias fazem parte da linguagem do autômato? ● Descreva informalmente a linguagem do autômato ● Descreva formalmente a linguagem do autômato Respostas ● Cadeias com um número par de 0s e 1s ● L = {w | w tem ao mesmo tempo um número par de 0s e um número par de 1s} Interpretando Autômatos Finitos ● Dado o seguinte autômato finito: 0 1 → q1 q1 q2 * q2 q1 q2 Interpretando autômatos finitos ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ 010 0111110 0000001 1101 001 11100 ● Quais dessas cadeias fazem parte da linguagem do autômato? ● Descreva informalmente a linguagem do autômato ● Descreva formalmente a linguagem do autômato Respostas ● Todas as cadeias que terminam com 1 ● L = {w | w termina com um 1} Interpretando autômatos finitos s q1 a q2 a b a b r1 b r2 a b a b Interpretando autômatos finitos ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: a b aa bb bab ab ba bbba ● Quais dessas cadeias fazem parte da linguagem do autômato? ● Descreva informalmente a linguagem do autômato ● Descreva formalmente a linguagem do autômato Respostas ● Cadeias que começam e terminam com o mesmo símbolo ● L = {w | w começa e termina com a ou w começa e termina com b} Projetando autômatos finitos ● Projetar é um processo criativo ● Não pode ser reduzido a uma receita ou fórmula simples ● Dica: ponha-se a si próprio no lugar da máquina que está tentando projetar ○ Veja como você se conduziria para realizar a tarefa da máquina ○ Você recebe uma cadeia de entrada ○ Vai vendo os símbolos um por um ○ Você não sabe quando o final da cadeia está vindo ○ Tem que estar sempre pronto com a resposta Projetando autômatos finitos ● Você precisa lembrar coisas sobre a cadeia ○ Impossível lembrar tudo ○ Autômatos finitos não sabem contar! ○ Nem você consegue lembrar tudo ■ Imagine uma entrada com 1000 dígitos ○ Precisa ter uma lógica ○ Um raciocínio ■ Essa informação é crucial ■ Depende do feeling, talento, dom, etc... Projetando autômatos finitos ● Ex: ○ Ʃ = {0,1} ○ Linguagem = cadeias com número ímpar de 1s qÍmparqPar 1 1 0 0 Projetando autômatos finitos ● Ex: ○ Ʃ = {0,1} ○ Linguagem = cadeias que contém a cadeia 001 como uma subcadeia q q0 q00 q001 1 0 1 0 1 0 0,1 Projetando autômatos finitos ● Ex: ○ Ʃ = {0,1} ○ Linguagem = cadeias que terminam em 00 q q0 q00 1 0 1 0 0 1 Mais um exercício ● Linguagem A consistindo de todas as cadeias sobre {0,1} contendo um 1 na terceira posição a partir do final ○ Ex: 000100, 010110 estão em A, mas 0011 não Mais um exercício Fim Aula 02 - Autômatos finitos Slides/LFA.2015.2.Aula03.Minimiza��o de DFAs.pdf Linguagens Formais e Autômatos Aula 03 - Minimização de DFAs Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 4 - Seção 4.4 Minimização de DFAs ● Existe um procedimento que minimiza um DFA ○ Ou seja, dado um DFA, ele permite encontrar um DFA equivalente que tenha o número mínimo de estados. ● De fato, esse DFA é mínimo: ○ Teorema: Se A é um DFA e M é o DFA construído a partir de A pelo algoritmo descrito a seguir, então M tem tão poucos estados quanto qualquer DFA equivalente a A ○ Em outras palavras, podemos testar a equivalência entre DFAs ■ Minimizando os dois e verificando se são iguais (com exceção, possivelmente, dos nomes dos estados) Minimização de DFAs ● Conceito de estados equivalentes ○ Objetivo: entender quando dois estados distintos p e q podem ser substituídos por um único estado que se comporte como p e q ● Formalmente: ○ Dois estados p e q são equivalentes se: ■ Para todas as cadeias de entrada w, δ^(p, w) é um estado de aceitação se e somente se δ^(q, w) é um estado de aceitação Minimização de DFAs ● Menos formalmente: ○ Existe uma cadeia w que leva p à aceitação e w à não-aceitação (ou vice-versa)? ○ Se existir pelo menos uma cadeia assim, os estados são distinguíveis ■ Caso contrário, são equivalentes! Minimização de DFAs ● Ilustrando: ○ 0,1, 010, 111 não distingue p e q ○ 11 distingue p e q ○ r e s são distinguíveis (ε os distingue) p q r s 0,1 0,1 1 0,1 1 1 1 0 0 0 0 0,1 Minimização de DFAs ● Difícil encontrar estados equivalentes apenas “olhando” para o DFA ○ Muitas combinações, fácil se perder ● Estratégia sistemática: encontrar todos os pares de estados que sejam distinguíveis ○ Se fizermos o melhor possível ■ Qualquer par de estados que não considerarmos distinguíveis serão equivalentes ● Algoritmo de preenchimento de tabela ○ Descoberta recursiva de pares distinguíveis ○ Cada célula da tabela marca um par distinguível ○ Células em branco marcam pares equivalentes A B C D E F G B C D E F G H x x x x x x x A B C D E F G B C D E F G H Começamos pelos estados de aceitação/não- aceitação. São obviamente pares distinguíveis pela cadeia vazia x x x x x x x A B C D E F G B C D E F G H Agora tentamos encontrar outros estados que “chegam” em um par conhecido, dada uma mesma entrada. A técnica é seguir, para cada par distinguível, as setas pelo lado inverso, com um mesmo rótulo Fica mais fácil se marcar as células já analisadas x x x x x x x A B C D E F G B C D E F G H Exs: (a) Seguindo as setas que “chegam” em A e C (um par distinguível), mediante entrada 0, temos: ● SetasA_0:{C}, SetasC_0:{D,F} ● Novos pares = SetasA_0 x SetasC_0 = {(C,D), (C,F)} ● Estes pares já estão marcados na tabela, com um x ● Analisando para entrada 1, temos: ● SetasA_1: {}, SetasC_1: {B,C,H} ● Novos pares = SetasA_1 X SetasC_1 = {} (nenhum novo par) ● Uma vez que já analisamos as entradas 0 e 1, a célula (A,C) foi analisada e é marcada x x x x x x x x x A B C D E F G B C D E F G H Exs: (b) Continuando para par (B,C): ● SetasB_0:{A}, SetasC_0:{D,F} ● Novos pares = SetasB_0 x SetasC_0 = {(A,D), (A,F)} ● Esses pares ainda não foram marcados, e portanto a tabela precisa ser atualizada ● SetasB_1: {}, SetasC_1: {B,C,H} ● Novos pares = SetasB_1 X SetasC_1 = {} (nenhum novo par) ● Uma vez que já analisamos as entradas 0 e 1, a célula (B,C) foi analisada e é marcada x x x x x x x x x A B C D E F G B C D E F G H Exs: (c) Continuando para par (C,D): ● SetasC_0:{D,F}, SetasD_0:{} ● Novos pares = {} ● SetasC_1:{B,C,H}, SetasD_1: {} ● Novos pares = {} ● Nenhum novo par x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (d) Continuando para par (C,E): ● SetasC_0:{D,F}, SetasE_0:{} ● Novos pares = {} ● SetasC_1:{B,C,H}, SetasE_1: {G} ● Novos pares = {(B,G),(C,G),(H,G)} ● Novos pares e a célula (C,E) são marcados x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (e) Continuando para par (C,F): ● SetasC_0:{D,F}, SetasF_0:{} ● Novos pares = {} ● SetasC_1:{B,C,H}, SetasF_1: {A,E} ● Novos pares = {(B,A),(B,E),(C,A),(C,E),(H,A),(H,E)} ● Novos pares e a célula (C,F) são marcados x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (f) Continuando para par (C,G): ● SetasC_0:{D,F}, SetasG_0:{B,G,H} ● Novos pares = {(D,B),(D,G),(D,H),(F,B),(F,G),(F,H)} ● SetasC_1:{B,C,H}, SetasG_1: {D,F} ● Novos pares = {(B,D),(B,F),(C,D),(C,F),(H,D),(H,F)} ● Novos pares e a célula (C,G) são marcados x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (g) Continuando para par (C,H): ● SetasC_0:{D,F}, SetasH_0:{E} ● Novos pares = {(D,E),(F,E)} ● SetasC_1:{B,C,H}, SetasH_1: {} ● Novos pares = {} ● Novos pares e a célula (C,H) são marcados x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (h) Continuando para par (A,B): ● SetasA_0:{C}, SetasB_0:{A} ● Novos pares = {(A,C)} ● SetasA_1:{}, SetasB_1: {} ● Novos pares = {} ● Novos pares e a célula (A,B) são marcados x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (h) Continuando para par (A,D): ● SetasA_0:{C}, SetasD_0:{} ● Novos pares = {(A,C)} ● SetasA_1:{}, SetasD_1: {} ● Novos pares = {} ● Célula (A,D) é marcada x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (h) Continuando para par (A,F): ● SetasA_0:{C}, SetasF_0:{} ● Novos pares = {(A,C)} ● SetasA_1:{}, SetasF_1: {A,E} ● Novos pares = {} ● Célula (A,F) é marcada x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (h) Continuando para par (A,H): ● SetasA_0:{C}, SetasH_0:{E} ● Novos pares = {(C,E)} ● SetasA_1:{}, SetasH_1: {} ● Novos pares = {} ● Célula (A,H) é marcada x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (i) Continuando para par (B,D): ● SetasB_0:{A}, SetasD_0:{} ● Novos pares = {} ● SetasB_1:{}, SetasD_1: {} ● Novos pares = {} ● Célula (B,D) é marcada x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (i) Continuando para par (B,E): ● SetasB_0:{A}, SetasE_0:{} ● Novos pares = {} ● SetasB_1:{}, SetasE_1: {G} ● Novos pares = {} ● Célula (B,E) é marcada x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (j) Continuando para par (B,F): ● SetasB_0:{A}, SetasF_0:{} ● Novos pares = {} ● SetasB_1:{}, SetasF_1: {A,E} ● Novos pares = {} ● Célula (B,F) é marcada x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (k) Continuando para par (B,G): ● SetasB_0:{A}, SetasG_0:{B,G,H} ● Novos pares = {(A,B),(A,G),(A,H)} ● SetasB_1:{}, SetasG_1: {D,F} ● Novos pares = {} ● Novo par e célula (B,G) são marcados x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (l) Continuando para par (A,G): ● SetasA_0:{C}, SetasG_0:{B,G,H} ● Novos pares = {(C,B),(C,G),(C,H)} ● SetasA_1:{}, SetasG_1: {D,F} ● Novos pares = {} ● Célula (A,G) é marcada x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (m) Continuando para par (D,E): ● SetasD_0:{}, SetasE_0:{} ● Novos pares = {} ● SetasD_1:{}, SetasE_1: {G} ● Novos pares = {} ● Células (D,E), (D,G) e (D,H) são marcadas (pois SetasD_0 e SetasD_1 são vazios) x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (n) Continuando para par (E,F): ● SetasE_0:{}, SetasF_0:{} ● Novos pares = {} ● SetasE_1:{G}, SetasF_1: {A,G} ● Novos pares = {(A,G)} ● Célula (E,F) é marcada x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (o) Continuando para par (E,H): ● SetasE_0:{}, SetasH_0:{E} ● Novos pares = {} ● SetasE_1:{G}, SetasH_1: {} ● Novos pares = {} ● Célula (E,H) é marcada x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (p) Continuando para par (F,G): ● SetasF_0:{}, SetasG_0:{B,G,H} ● Novos pares = {} ● SetasF_1:{A,E}, SetasG_1: {D,F} ● Novos pares = {(A,D),(A,F),(E,D),(E,F)} ● Célula (F,G) é marcada x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (q) Continuando para par (F,H): ● SetasF_0:{}, SetasH_0:{E} ● Novos pares = {} ● SetasF_1:{A,E}, SetasH_1: {} ● Novos pares = {} ● Célula (F,H) é marcada x x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (q) Continuando para par (G,H): ● SetasG_0:{B,G,H}, SetasH_0:{E} ● Novos pares = {(B,E),(G,E),(H,E)} ● SetasG_1:{D,F}, SetasH_1: {} ● Novos pares = {} ● Novo par e célula (G,H) são marcados x x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Exs: (r) Continuando para par (G,E): ● SetasG_0:{B,G,H}, SetasE_0:{} ● Novos pares = {} ● SetasG_1:{D,F}, SetasE_1: {G} ● Novos pares = {(D,G),(F,G)} ● Célula (G,E) é marcada x x x x x x x x x x x x x x x x x x x x x x x x x A B C D E F G B C D E F G H Resultado: - São pares equivalentes: (A,E), (B, H) e (D,F) Minimização de DFAs ● Algoritmo em duas etapas: ○ a. Eliminar estados inalcançáveis ■ Reduz o trabalho do algoritmo de preenchimento de tabela ○ b. Particionar os estados restantes em blocos de estados equivalentes ■ Primeiro deve-se identificar os pares equivalentes ■ Depois formar os grupos de estados equivalentes Estados inalcançáveis Estados alcançáveis devem ter um caminho a partir do estado inicial Neste exemplo, o estado D é inalcançável Particionamento em grupos de estados equivalentes Neste exemplo, são pares equivalentes: (A,E), (B,H) e (D,F) - Partição: {A,E},{B,H},{D,F},{C},{G} Importante: deve-se considerar o caráter transitivo da equivalência. Por exemplo, se os pares equivalentes fossem: (A,E), (E,H), (D,F) - A partição seria: {A,E,H},{D,F},{B},{C},{G} (Ou seja, A é equivalente a E, E é equivalente a H, portanto A é equivalente a H, e os três formam um único grupo) Particionamento em grupos de estados equivalentes 0 1 {A,E} {B,H} {F} {B,H} {G} {C} {D,F} {C} {G} {C} {A} {C} {G} {G} {E} Para concluir a minimização, basta definir a nova função de transição Para isso, monta-se uma tabela vazia, onde cada estado é um grupo da partição As transições são definidas como a união das transições no autômato original Particionamento em grupos de estados equivalentes 0 1 {A,E} {B,H} {D,F} {B,H} {G} {C} {D,F} {C} {G} {C} {A,E} {C} {G} {G} {A,E} Agora, basta substituir os valores das células por grupos que representam estados válidos (a primeira coluna da tabela) De {F} para {D, F} De {A} para {A, E} 0 1 {A,E} {B,H} {F} {B,H} {G} {C} {D,F} {C} {G} {C} {A} {C} {G} {G} {E} De {E} para {A, E} Nunca haverá conflito, devido ao algoritmo de preenchimento da tabela Particionamento em grupos de estados equivalentes 0 1 → {A,E} {B,H} {D,F} {B,H} {G} {C} {D,F} {C} {G} * {C} {A,E} {C} {G} {G} {A,E} Para concluir, renomeie os estados para ficar mais legível 0 1 → Q1 Q2 Q3 Q2 Q5 Q4 Q3 Q4 Q5 * Q4 Q1 Q4 Q5 Q5 Q1 Estados iniciais e de aceitação são os grupos que contém os estados iniciais e de aceitação do DFA original Fim Aula 03 - Minimização de DFAs Slides/LFA.2015.2.Aula04.N�o Determinismo.pdf Aula 04 - Não determinismo Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 2 - Seção 2.3 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.2 Mais um exercício ● Linguagem A consistindo de todas as cadeias sobre {0,1} contendo um 1 na terceira posição a partir do final ○ Ex: 000100, 010110 estão em A, mas 0011 não Mais um exercício Não-Determinismo ● Determinismo é como achar um caminho com um GPS ○ Ele avisa a cada esquina ○ Não há dúvida ● Não-determinismo exige “adivinhação” ○ Não é possível saber todos os passos Não-Determinismo ● Um autômato pode estar em muitos estados ao mesmo tempo ○ No diagrama: ■ DFA tem exatamente 1 seta com 1 símbolo para todo símbolo e estado ■ NFA pode ter zero ou mais setas para um símbolo/estado ○ Na tabela ■ DFA é completamente preenchida, com exatamente um estado em cada célula ■ NFA pode ter células com zero ou mais estados Não-Determinismo ● O que isto significa na prática? ○ Uma visão: um NFA pode “adivinhar” algumas coisas sobre a entrada (poder paranormal) ○ Outra visão: em transições para mais de um estado, é o mesmo que dividir o autômato em dois e seguir cada execução em paralelo ○ Outra: uma árvore de possibilidades – tentativa e erro Não-Determinismo ● Mais fáceis de projetar e entender ○ Ex: Ʃ = {0,1} ○ A é uma linguagem consistindo de todas as cadeias contendo um 1 na terceira posição a partir do final (exemplo: 000100) Não-Determinismo ● Ex: Ʃ = {0,1} ● A é uma linguagem que aceita cadeias da forma 0k, onde k é um múltiplo de 2 ou 3 Autômatos finitos não- determinísticos ● Definição formal: NFA ● A=(Q,Ʃ,δ,q0,F) ○ Q=Conjunto finito de estados ○ Ʃ=Conjunto finito de símbolos de entrada ○ δ=Função de transição ○ q0=Um estado inicial (q0 ∈ Q) ○ F=Um conjunto de estados finais ou de aceitação (F ⊆ Q) ● Diferença está na função de transição ○ δ:Q × Ʃ → Q* Autômatos finitos determinísticos ● RELEMBRANDO os AFD: ● Definição formal de linguagem (indutiva) ○ δ(q,a)=p ○ δ^(q,ε)=q ○ δ^(q,w)= δ(δ^(q,x),a) onde w=xa ○ L(A)={w| δ^(qo,w) está em F} ● Definição: ○ Se L é L(A) para algum DFA ○ L é regular Autômatos finitos não- determinísticos ● Definição formal de linguagem ○ δ^(q,ε)={q} ○ δ^(q,x)= {p1,p2,...,pk} ○ δ^(q,w)=união de todos δ(pi,a), onde w=xa ○ L(A)={w| δ^(qo,w) ∩ F ≠ ∅} ● Definição: ○ Se L é L(A) para algum NFA ○ L é regular Interpretando NFAs Interpretando NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ 111 ○ 010 ○ 0100 ○ (Use notação de árvore ou conjuntos) ● Descreva a linguagem reconhecida por este autômato Interpretando NFAs Ʃ = {1,2,3,4} Interpretando NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ 1234 ○ 123 ○ 1231 ○ 433 ○ 412 ○ (Use notação de árvore ou conjuntos) ● Descreva a linguagem reconhecida por este autômato Interpretando NFAs ● Resposta ○ Aceita cadeias cujo símbolo final já apareceu antes Interpretando NFAs Interpretando NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ ave ○ avião ○ aves ○ chave ○ (Use notação de árvore ou conjuntos) ● Descreva a linguagem reconhecida por este autômato Interpretando NFAs ● Dado o seguinte autômato finito: 0 1 → q0 {q0,q1} {q0} q1 ∅ {q2} * q2 ∅ ∅ Interpretando NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ 0101010 ○ 11111 ○ 001 ○ 1101 ○ (Use notação de árvore ou conjuntos) ● Descreva a linguagem aceita por este autômato ○ Resp: cadeias que terminam em 01 Projetando NFAs ● Ex: ○ Ʃ = {a,b,c,...,z} ○ Linguagem = cadeias que contém a cadeia “pre” como uma subcadeia Projetando NFAs ● Ex: ○ Ʃ = {0,1} ○ Linguagem = cadeias que não possuem símbolos repetidos em sequência Fim Aula 04 - Não-determinismo Slides/LFA.2015.2.Aula05.Equival�ncia DFA x NFA.pdf Aula 05 - Equivalência DFA x NFA Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 2 - Seção 2.3 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.2 Equivalência DFA e NFA ● Intuitivamente, NFA é mais poderoso ○ Mas as linguagens aceitas por um NFA são regulares ○ Ou seja, qualquer NFA pode ser convertido em um DFA que reconhece a mesma linguagem ● Teorema: ○ Uma Linguagem L é aceita por algum DFA se e somente se L é aceita por algum NFA ○ Prova por construção dos dois lados: ■ “Se”: um processo que constrói um DFA a partir de um NFA ■ “Somente se”: um processo que constrói um NFA a partir de um DFA Conversão NFA → DFA ● Na maioria dos casos, um DFA equivalente tem o mesmo número de estados que o NFA, só que mais transições ● No pior caso, tem 2n estados ○ NFA N = (QN, Ʃ, δN, q0, FN) ○ DFA D = (QD, Ʃ, δD, {q0}, FD) ○ L(D) = L(N) ● QD é o conjunto de subconjuntos de QN ● FD é o conjunto S de subconjuntos de QN, tal que S ∩ FN ≠ ∅ ● Para cada conjunto S ⊆ QN ○ e para cada a ∈ Ʃ ○ δD(S,a) = ∪ todos os δN(p,a) para p ∈ S Conversão NFA → DFA ● Consiste em pegar todas as combinações de estados e agregar as transições do NFA ○ Cada combinação de estados do NFA é um estado no DFA ● Consiste basicamente na implementação “em paralelo” ○ Mas pré-calculando as combinações de estados Conversão NFA → DFA ● Passo a passo com exemplo ● Dado o NFA (cadeias que terminam com 01): 0 1 → q0 {q0,q1} {q0} q1 ∅ {q2} * q2 ∅ ∅ Conversão NFA → DFA ● Passo 1: ○ Faça uma tabela “vazia”, com as mesmas entradas como colunas (a tabela vai crescer para baixo) 0 1 Conversão NFA → DFA ● Passo 2: ○ Crie um novo estado inicial no DFA, um conjunto que contém somente o estado inicial do NFA 0 1 → {q0} Conversão NFA → DFA ● Passo 3: ○ Para cada entrada, insira no DFA um conjunto que contém a união de todos os resultados da transição NFA daquela entrada para todos os estados do conjunto à esquerda 0 1 → {q0} {q0,q1} {q0} Conversão NFA → DFA ● Passo 4: ○ Para cada novo conjunto de estados que aparecer, insira uma nova linha na tabela do DFA e volte para o passo 3 0 1 → {q0} {q0,q1} {q0} {q0,q1} {q0,q1} {q0,q2} Conversão NFA → DFA ● Passo 4 (novamente): 0 1 → {q0} {q0,q1} {q0} {q0,q1} {q0,q1} {q0,q2} {q0,q2} {q0,q1} {q0} Conversão NFA → DFA ● Passo 5: Quando não houver mais novos estados, marque como estado de aceitação os conjuntos que contém ao menos um estado de aceitação do NFA 0 1 → {q0} {q0,q1} {q0} {q0,q1} {q0,q1} {q0,q2} * {q0,q2} {q0,q1} {q0} Conversão NFA → DFA ● Passo 6: “Renomeie” os conjuntos para estados, de forma a facilitar a leitura do DFA 0 1 → A B A B B C * C B A Conversão NFA → DFA ● Dado o seguinte NFA: ○ Construa um DFA que aceite a mesma linguagem 0 1 → p {p,q} {p} q {r} {r} r {s} ∅ * s {s} {s} Conversão NFA → DFA 0 1 → {p} A {p,q} B {p} A {p,q} B {p,q,r} D {p,r} C {p,r} C {p,q,s} E {p} A {p,q,r} D {p,q,r,s} F {p,r} C * {p,q,s} E {p,q,r,s} F {p,r,s} G * {p,q,r,s} F {p,q,r,s} F {p,r,s} G * {p,r,s} G {p,q,s} E {p,s} H * {p,s} H {p,q,s} E {p,s} H Conversão NFA → DFA ● Dado o seguinte NFA: ○ Construa um DFA que aceite a mesma linguagem 0 1 → * q0 {q1} {q2} * q1 ∅ {q0} * q2 {q0} ∅ Conversão NFA → DFA 0 1 → * {q0} A {q1} B {q2} C * {q1} B {} D {q0} A * {q2} C {q0} A {} D {} D (morto) {} D {} D Conversão DFA → NFA ● “Resto” da prova ● Parte fácil ○ Construir um NFA a partir de um DFA ○ Basta “copiar” o diagrama (ou tabela), trocando estados por conjuntos de estados ○ Um DFA é um caso específico de NFA ■ NFA permite 0 ou mais transições em cada situação ■ DFA permite sempre 1 transição em cada situação ■ 1 está entre 0 ou mais Conversão DFA → NFA 0 1 → q1 q1 q2 * q2 q1 q2 0 1 → q1 {q1} {q2} * q2 {q1} {q2} Conversão DFA → NFA ● Formalmente: ○ Seja D = (Q,Ʃ,δD,q0,F) um DFA ○ Defina N = (Q,Ʃ,δN,q0,F) ■ Onde δN é definido pela regra: ● Se δD(q,a)=p, então δN(q,a)={p} ● Como consequência ○ Se δ^D(q0,w)=p, então δ^N(q0,w)={p} ● Portanto, w é aceito por D se e somente se é aceito por N ○ Isto é: L(D) = L(N) Fim Aula 05 - Equivalência DFA x NFA Slides/LFA.2015.2.Aula06.NFA com transi��es vazias.pdf Aula 06 - NFA com transições vazias Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 2 - Seção 2.5 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.2 NFA com transições vazias ● Transições espontâneas ○ Isto é, sem nenhuma entrada ● É uma forma de não-determinismo ○ Facilita a “programação” ● Ex: números decimais NFA com transições vazias ● Ex: busca por palavras-chave NFA com transições vazias ● Definição formal ○ A mesma que NFA ○ Muda somente a função de transição ■ δ:Q × Ʃ ∪ {ε} → Q* ○ Uma coluna extra na tabela, ou transições vazias no diagrama ε +,- . 0,1,...,9 → q0 {q1} {q1} ∅ ∅ q1 ∅ ∅ {q2} {q1,q4} q2 ∅ ∅ ∅ {q3} q3 {q5} ∅ ∅ {q3} q4 ∅ ∅ {q3} ∅ * q5 ∅ ∅ ∅ ∅ NFA com transições vazias ● Essa nova característica não aumenta o poder do NFA ○ Ainda reconhece linguagens regulares ● Conceito de épsilon-fechamento ○ ECLOSE(q) ○ Conjunto de todos os estados alcançáveis espontaneamente a partir de q ■ Incluindo os vizinhos diretos e indiretos ■ Analisando-se os arcos rotulados com ε ● Função de transição estendida ○ Deve considerar sempre o ECLOSE Interpretando ε-NFAs ● Dado o seguinte autômato (que reconhece números decimais) Interpretando ε-NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para a seguinte cadeia: ○ 5.6 ○ 67.1.2 ○ (Use notação de árvore ou conjuntos) ● Passo 1: calcule ECLOSE(q0) ● Passos seguintes: mesmo que NFA ○ Porém, para cada estado alcançado, inclua o seu ECLOSE também Interpretando ε-NFAs ● Resposta: ○ {q0,q1}5.6 ○ 5{q1,q4}.6 ○ 5.{q2,q3,q5}6 ○ 5.6{q3,q5} ● Conjunto de estados finais contém q5, portanto o autômato aceita a cadeia Interpretando ε-NFAs ● Dado o seguinte autômato Interpretando ε-NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ ε ○ a ○ baba ○ baa ○ b ○ bb ○ babba ○ (Use notação de árvore ou conjuntos) Interpretando ε-NFAs ● Dado o seguinte autômato Interpretando ε-NFAs ● Calcule a função estendida e mostre, passo a passo, as configurações instantâneas para as seguintes cadeias: ○ 1111 ○ 11 ○ 101 ○ 00010 ○ (Use notação de árvore ou conjuntos) Projetando ε-NFAs ● Ex: ○ Ʃ = {0,1} ○ Linguagem = cadeias que contém a sequência 010 ou 101 como subcadeia Projetando ε-NFAs ● Ex: ○ Ʃ = {a,b,c} ○ Linguagem = cadeias onde b e c sempre aparecem depois de uma ocorrência de a Equivalência ε-NFAs e DFAs ● Transições vazias não adicionam poder ao autômato ○ Ainda reconhece as mesmas linguagens ○ Linguagens regulares ● Teorema: ○ Uma Linguagem L é aceita por algum DFA se e somente se L é aceita por algum ε-NFA ○ Prova por construção dos dois lados: ■ “Se”: um processo que constrói um DFA a partir de um ε- NFA ■ “Somente se”: um processo que constrói um ε-NFA a partir de um DFA Conversão ε-NFA → DFA ● É o mesmo procedimento da construção de subconjuntos dado anteriormente ○ Porém incorporando o cálculo de ε-fechamento após cada passo ○ Similar à implementação do ε-NFA Conversão ε-NFA → DFA ● Passo a passo com exemplo ● Dado o NFA: ε a b c → p ∅ {p} {q} {r} q {p} {q} {r} ∅ * r {q} {r} ∅ {p} Conversão ε-NFA → DFA ● Passo 1 (auxiliar): calcule o ECLOSE de todos os estados ● ECLOSE(p) = {p} ● ECLOSE(q) = {p,q} ● ECLOSE(r) = {p,q,r} ε a b c → p ∅ {p} {q} {r} q {p} {q} {r} ∅ * r {q} {r} ∅ {p} Conversão ε-NFA → DFA ● Passo 2: faça uma tabela “vazia” com as entradas (sem a coluna ε) a b c Conversão ε-NFA → DFA ● Passo 3: Crie um novo estado inicial no DFA, um conjunto que contém o ECLOSE do estado inicial do NFA a b c → {p} Conversão ε-NFA → DFA ● Passo 4: ○ Para cada entrada, insira no DFA um conjunto que contém o ECLOSE da união de todos os resultados da transição NFA daquela entrada para todos os estados do conjunto à esquerda a b c → {p} {p} {p,q} {p,q,r} Conversão ε-NFA → DFA ● Passo 5: ○ Para cada novo conjunto de estados que aparecer, insira uma nova linha na tabela do DFA e volte para o passo 4 a b c → {p} {p} {p,q} {p,q,r} {p,q} {p,q} {p,q,r} {p,q,r} {p,q,r} {p,q,r} {p,q,r} {p,q,r} Conversão ε-NFA → DFA ● Passo 6: Quando não houver mais novos estados, marque como estado de aceitação os conjuntos que contém ao menos um estado de aceitação do NFA a b c → {p} {p} {p,q} {p,q,r} {p,q} {p,q} {p,q,r} {p,q,r} * {p,q,r} {p,q,r} {p,q,r} {p,q,r} Conversão ε-NFA → DFA ● Passo 7: “Renomeie” os conjuntos para estados, de forma a facilitar a leitura do DFA a b c → A A B C B B C C * C C C C Conversão ε-NFA → DFA ● Dado o seguinte ε-NFA ○ Converta para um DFA que aceita a mesma linguagem ε a b c → p {q,r} ∅ {q} {r} q ∅ {p} {r} {p,q} * r ∅ ∅ ∅ ∅ Conversão ε-NFA → DFA ● Resposta a b c → * {p,q,r} {p,q,r} {q,r} {p,q,r} * {q,r} {p,q,r} {r} {p,q,r} * {r} {} {} {} {} {} {} {} Conversão ε-NFA → DFA ● Dado o seguinte ε-NFA ○ Converta para um DFA que aceita a mesma linguagem ε a b → * 1 {3} ∅ {2} 2 ∅ {2,3} {3} 3 ∅ {1} ∅ Conversão ε-NFA → DFA ● Resposta a b → * {1,3} {1,3} {2} {2} {2,3} {3} {2,3} {1,2,3} {3} {3} {1,3} {} * {1,2,3} {1,2,3} {2,3} {} {} {} Conversão DFA → ε-NFA ● “Resto” da prova ● Parte fácil ○ Mesmo caso da conversão de DFA para NFA ○ Mas fazendo com que δ(q, ε) = ∅ para todo estado q do DFA ○ Ou seja, não existem transições espontâneas (mas poderia ter) Resumo ● Definições X Linguagens X Problemas ● Autômatos Finitos ○ DFA ○ NFA ○ ε-NFA ● Aceitam as mesmas linguagens (regulares) ε-NFA NFA DFA Resumo “fácil” Construção de subconjuntos Construção de subconjuntos + ECLOSE É possível simular Mas cada um tem um custo (tamanho da engrenagem) Resumo ● Simular direto vs converter para DFA ○ Depende da aplicação ○ Padrões de busca voláteis (ex: grep) ■ Melhor simular NFA ○ Padrões fixos (ex: análise léxica) ■ Melhor converter para DFA Fim Aula 06 - NFA com transições vazias Slides/LFA.2015.2.Aula07.Implementa��o de Aut�matos Finitos.pdf Linguagens Formais e Autômatos Aula 07 - Implementação de Autômatos Finitos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Implementando DFAs ● Implementação é simples ● Teste que implementa a função de transição e testa o estado final ○ Ou uma implementação com uma tabela genérica ● Demonstração Implementando DFAs ● www.simuladordeautomatos.com ● IC e TCC ○ UNIUBE – Universidade de Uberaba Implementando NFAs ● A implementação é mais complexa do que o DFA ○ Mas em essência é o mesmo mecanismo ● Envolve duas estratégias ○ Processamento paralelo ○ “Backtracking” ● Demonstração Implementando ε-NFAs ● Envolve a implementação do épsilon-fechamento ○ E também precisa de uma coluna para transições vazias ● Demonstração Fim Aula 07 - Implementação de Autômatos Finitos Slides/LFA.2015.2.Aula08.Express�es Regulares.pdf Aula 08 - Expressões regulares Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 3 - Seções 3.1 e 3.4 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.3 Expressões regulares ● Autômatos denotam linguagens ● Autômatos possuem duas notações ○ Diagrama de estados ○ Tabela de transições ● Vimos apenas uma notação para linguagens ○ Notações de conjuntos / formadores de conjuntos ○ Ex: {w | regra sobre w} ● Existe outra notação ○ Expressões regulares Expressões regulares ● Notação algébrica ● Definição de álgebra (by wikipedia) ○ Um conjunto A e uma coleção de operações sobre A ○ Operações k-árias ■ 0-árias: ex: constantes, 2, x, y ■ 1-árias: ex: -10 ■ 2-árias: ex: 2+2, 3*y Expressões regulares ● Na teoria da computação ● Álgebra envolve ○ Conjunto A = alfabeto ○ Operações = operações regulares ● Operações regulares ○ Operações sobre membros de um alfabeto ○ Linguagens regulares são fechadas sob as operações regulares Conjuntos fechados sob uma operação ● Exemplo: ○ N = {1,2,3,...} (conjunto de números naturais) ○ N é fechado sob multiplicação ○ Ou seja: para quaisquer x e y em N ■ x * y também está em N ○ N não é fechado sob divisão ■ Contra-exemplo: 1 e 2 estão em N, mas ½ não está! ● Definição: ○ Uma coleção de objetos é fechada sob alguma operação se, aplicando-se essa operação a membros da coleção, recebe-se um objeto ainda na coleção Operações regulares ● Operações que: ○ Aplicadas sobre elementos de linguagens regulares ○ Resultam em linguagens regulares ● Em outras palavras: ○ Sejam L1 e L2 duas linguagens regulares ○ L1 opreg L2 é regular Operações regulares ● São 3 as operações regulares: ○ União: A ∪ B = {x | x ∈ A ou x ∈ B} ○ Concatenação: A.B = {xy | x ∈ A e y ∈ B} ○ Estrela (ou fechamento, ou fechamento de Kleene): A* = {x1x2...xk | k ≥ 0 e cada xi ∈ A} ● União e concatenação são operações binárias ● Estrela é uma operação unária Operações regulares ● União ○ L = {001, 10, 111} e M = {ε, 001} ○ L ∪ M = {ε, 10, 001, 111} ● Concatenação ○ L = {001, 10, 111} e M = {ε, 001} ○ L.M (ou LM) = {001,10,111,001001,10001,111001} ● Estrela ○ L = {0, 11} ○ L* = {ε, 0, 00, 000, 000, 11, 011, 1111, 00011011, ... (não há uma ordem lógica aqui)} Operações regulares ● Teorema: A classe de linguagens regulares é fechada sob a operação de união ○ Em outras palavras: se A1 e A2 são linguagens regulares, A1 ∪ A2 é regular ● Prova: ○ Construção ○ A1 é regular, existe um autômato M1 ○ A2 é regular, existe um autômato M2 ○ Construímos um autômato M que simula M1 e M2, aceitando se uma das simulações aceita Operações regulares M1 M2 ε ε ε ε L(M) = L(M1) ∪ L(M2) M Operações regulares ● Teorema: A classe de linguagens regulares é fechada sob a operação de concatenação ○ Em outras palavras, se A1 e A2 são linguagens regulares, A1.A2 é regular ● Prova: ○ Construção ○ A1 é regular, existe um autômato M1 ○ A2 é regular, existe um autômato M2 ○ Construímos um autômato M que simula M1 e em seguida M2, passando de M1 para M2 quando M1 aceita, e aceitando quando M2 aceita Operações regulares M1 M2 ε L(M) = L(M1) . L(M2) M Operações regulares ● Teorema: A classe de linguagens regulares é fechada sob a operação de estrela ○ Em outras palavras, se A é uma linguagem regular, A* é regular ● Prova: ○ Construção ○ A é regular, existe um autômato M ○ Construímos um autômato M’ que simula M, com a possibilidade de ir direto para o estado de aceitação, e a possibilidade de voltar de um estado de aceitação para o inicial Operações regulares M ε L(M’) = L(M)* M’ ε ε ε Expressões regulares ● Existe ainda uma “quarta operação regular” ○ Constantes (operações 0-árias) ○ A diferença é sutil ● As operações operam sobre conjuntos ○ Mas muitas vezes as usaremos com símbolos ○ Ou seja, em uma concatenação, ao invés de dizer {a}.{b}, queremos dizer a.b, ou simplesmente ab ● Por isso, iremos considerar que uma constante é uma operação ○ Toma como entrada um símbolo ○ E o resultado é uma linguagem (conjunto), cujo único elemento é aquele símbolo Expressões regulares ● Conceito de “variáveis” ○ Símbolos que representam linguagens regulares ○ Ex: a.b, onde a = {w | w contém número par de 0s} e b = {0,11,101} Expressões regulares ● Construindo expressões regulares ○ Assim como aritmética ○ Expressões elementares (constantes e/ou variáveis) ○ Operadores que formam expressões mais complexas ● Operadores possuem precedência ○ Ex: multiplicação sobre adição, etc ● Métodos para agrupar operadores ○ Ex: parêntesis, colchetes, chaves, etc Expressões regulares ● Constantes: ○ ε e Ø são expressões regulares ■ L(ε) = {ε} ■ L(Ø) = Ø ○ Se a é um símbolo qualquer, a é uma expressão regular ■ L(a) = {a} ● União ○ Se E e F são expressões regulares, E + F é uma expressão regular ■ L(E+F) = L(E) ∪ L(F) Expressões regulares ● Concatenação ○ Se E e F são expressões regulares, EF é uma expressão regular ■ L(EF) = L(E).L(F) ● Estrela ○ Se E é uma expressão regular, E* é uma expressão regular ■ L(E*) = (L(E))* ● Parêntesis ○ Se E é uma expressão regular, (E) é uma expressão regular ■ L((E)) = L(E) Expressões regulares ● Precedência ○ Estrela → concatenação → união ○ Ex: 01*+1 ● Parêntesis ○ Mudam a precedência ○ Ex: (01)*+1 ou 0(1*+1) Exemplos de expressões regulares ● Alfabeto = {0,1} ○ 0*10* = {w | w contém um único 1} ○ 01 + 10 = {01,10} ○ (ε + 0)1* = {w | w é uma sequência de zero ou mais 1s, começando opcionalmente com 0} ○ (0+1)* = Conjunto das partes do alfabeto ou conjunto de todas as cadeias possíveis sobre o alfabeto, incluindo a cadeia vazia (|w| ≥ 0) ○ (0+1)(0+1)* = Idem ao exemplo acima, mas sem a cadeia vazia (|w| ≥ 1) Exercícios ● Escreva expressões regulares correspondentes às seguintes linguagens: ○ {w | w começa com um 1 e termina com um 0} ■ Resp: 1(0+1)*0 ○ {w | w contém pelo menos três 1s} ■ Resp: 0*10*10*1(0+1)* ○ {w | o comprimento de w é no máximo 5} ■ Resp: (0+1+ε)(0+1+ε)(0+1+ε)(0+1+ε)(0+1+ε) ○ {w | toda posição ímpar de w é um 1} ■ Resp: (1(0+1))* + 1((0+1)1)* ou (1(0+1))*(1+ε) Leis algébricas para expressões regulares Leis algébricas para expressões regulares ● É possível (e muitas vezes necessário) simplificar expressões regulares ○ Ex: 1*0 + 1*0(ε+0+1)*(ε+0+1) = 1*0(0+1)* ● Existem algumas leis algébricas que facilitam esse processo Leis algébricas para expressões regulares ● Associatividade e comutatividade ○ L+M=M+L ■ Ex: 0+1 = 1+0 ○ (L+M)+N=L+(M+N) ■ Ex: (a* + bc) + a = a* + (bc + a) ○ (LM)N=L(MN) ■ Ex: (00(1+0))111=00((1+0)111) Leis algébricas para expressões regulares ● Identidades (elemento neutro) e aniquiladores ● Ø+L=L+Ø=L (Ø é identidade para união) ● εL=Lε=L (ε é identidade para concatenação) ● ØL=LØ=Ø (Ø é aniquilador para concatenação) ● Exs: ● εa(b+c)+aaε = a(b+c)+aa ● Ø(ε+1)*(1+0(01*10(0+1))) + 01 = Ø + 01 = 01 Leis algébricas para expressões regulares ● Leis distributivas ○ L(M+N)=LM+LN ○ (M+N)L=ML+NL ■ Exs: ● 0(0+1) = 00 + 01 ● (0+1)(0+1) = (0+1)0 + (0+1)1 ● (0+1)(0+1) = 0(0+1) + 1(0+1) Leis algébricas para expressões regulares ● Lei da idempotência ○ L+L=L ■ Exs: ● (0+1+ε) + (0+1+ε)=(0+1+ε) ● (0+1+ε)+01*0+(ε+0+1)+(ε+1+0)=(0+1+ε)+01*0 Leis algébricas para expressões regulares ● Leis envolvendo fechamentos ○ (L*)*=L* ■ Ex:((01)*)*=(01)* ○ Ø*=ε ○ ε*=ε ● Operadores de fechamento adicionais ○ L+=LL*=L*L ○ L*=L++ε ○ L?=ε+L Exemplos de simplificação 0+010 0ε+010 0(ε+10) 0(10)? ab*b(a+ε) ab*ba? ab+a? a+(b+c+ε)a(b+c)+ca+ba a+(b+c)?a(b+c)+ca+ba a+(b+c)?a(b+c)+(c+b)a εa+(b+c)?a(b+c)+(c+b)a εa+(c+b)a+(b+c)?a(b+c) (ε+c+b)a+(b+c)?a(b+c) (b+c)?a+(b+c)?a(b+c) (b+c)?aε+(b+c)?a(b+c) (b+c)?a(ε+b+c) (b+c)?a(b+c)? Fim Aula 08 - Expressões regulares Slides/LFA.2015.2.Aula09.Aut�matos finitos e express�es regulares.pdf Aula 09 - Autômatos finitos e expressões regulares Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 3 - Seção 3.2 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.3 Autômatos finitos e expressões regulares ● São diferentes na notação ○ Mas tanto autômatos finitos como expressões regulares representam exatamente o mesmo conjunto de linguagens ■ Linguagens regulares ● Ou seja: ○ Toda linguagem definida por um autômato finito também é definida por uma expressão regular ○ Toda linguagem definida por uma expressão regular é definida por um autômato finito Autômatos finitos e expressões regulares ε-NFA ER NFA DFA Já demonstrado A demonstrar Conversão DFA→ER ● Teorema: Se L = L(A) para algum DFA A, então existe uma expressão regular R tal que L = L(R) ● Conversão é surpreendentemente complicada ○ Método 1: n3 expressões, com 4n símbolos (pior caso) ○ Método 2: eliminação de estados ■ Mais simples, porém também trabalhosa ■ Envolve uma notação mista: autômatos + ERs ● Autômato finito não-determinístico generalizado ● Transições são expressões regulares Autômatos + ERs Conversão DFA→ER ● Método da eliminação de estados ● Eliminamos todos os estados, um por um ○ Ao eliminar um estado s, todos os caminhos que passam por s não mais existem no autômato ● Substituiremos símbolos por ER nas transições, para representar as transições eliminadas Conversão DFA→ER ● Para cada estado de aceitação q, elimine todos os estados, com exceção de q e q0 (estado inicial) ○ Resultado = um autômato para cada estado de aceitação Conversão DFA→ER ● Cada autômato terá uma ER equivalente 01*(1+0)*110 0+1* 11 1 1(0+ε)10 Conversão DFA→ER Basta fazer a união de todas as expressões 01*(1+0)*110 0+1* 11 1 1(0+ε)10 01*(1+0)*110 + 0 + 1* + 111 + 1(0+ε)10 Conversão DFA→ER Eliminando um estado s (caso não haja um determinado arco, considerar que existe um arco com rótulo Ø) Conversão DFA→ER ● Repetir esse procedimento para todos os estados ● No final, existem duas possibilidades: ○ q0=q ■ Resta um único estado, com uma transição R ■ R é a expressão regular equivalente ○ q0≠q ■ Restam dois estados, no seguinte formato genérico: A expressão regular final é (R+SU*T)*SU* R R U S T Conversão DFA→ER ● Exemplo: cadeias com símbolo 1 a duas ou três posições a partir do final Conversão DFA→ER ● Primeiro passo, substituir as transições rotuladas 0,1 por 0 + 1 Conversão DFA→ER ● Eliminando B (assim dá para reaproveitar em outras reduções) ○ Q1=1 ○ P1=0+1 ○ R11=Ø ○ S=Ø ● Arco de A para C = R11+Q1S*P1 = Ø+1Ø*(0+1) ○ Simplificando: 1(0+1) Conversão DFA→ER ● Eliminando C ○ Q1=1(0+1) ○ P1=0+1 ○ R11=Ø ○ S=Ø ● Arco de A para D = R11+Q1S*P1 = Ø+1(0+1)Ø* (0+1) ○ Simplificando: 1(0+1)(0+1) Conversão DFA→ER ● Restou um autômato de 2 estados ○ R=0+1 ○ S=1(0+1)(0+1) ○ U=Ø ○ T=Ø ● Fórmula: (R+SU*T)*SU* ○ Resultado: (0+1+1(0+1)(0+1)Ø*Ø)*1(0+1)(0+1)Ø* ○ Simplificando: (0+1)*1(0+1)(0+1) R U S T Conversão DFA→ER ● Eliminando D agora ○ Não há sucessor, portanto não haverá mudanças de arcos ○ Da mesma forma, restou um autômato de 2 estados ■ Expressão regular resultante: (0+1)*1(0+1) Conversão DFA→ER ● Haviam dois estados de aceitação ○ Foram obtidos dois autômatos ■ Duas expressões regulares equivalentes ● A expressão regular final é a união dessas duas: ● (0+1)*1(0+1)+(0+1)*1(0+1)(0+1) ● Simplificando ○ (0+1)*1(0+1)(0+1)? Conversão ER→ε-NFA ● Teorema: Toda linguagem definida por uma expressão regular também é definida por um autômato finito ● Prova por construção: ER→ε-NFA ○ Base + indução ● Base: ε, Ø e a (um símbolo qualquer) ε a Conversão ER→ε-NFA ● Indução: Os mesmos autômatos das provas sobre o fechamento das operações regulares R S ε ε ε ε R S ε Rε M’ ε ε ε R+S RS R* Conversão ER→ε-NFA ● Características do ε-NFA: ○ Possui exatamente um estado de aceitação ○ Nenhum arco chega no estado inicial ○ Nenhum arco sai do estado de aceitação Conversão ER→ε-NFA ● Ex: (0+1)*1(0+1) Fim Aula 09 - Autômatos finitos e expressões regulares Slides/LFA.2015.2.Aula11.Linguagens n�o regulares.pdf Aula 11 - Linguagens não regulares Linguagens Formais e Autômatos Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352-1072-5) ○ Capítulo 4 - Seção 4.1 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 1 - Seção 1.4 Linguagens não regulares ● Até agora vimos que: linguagens regulares são aquelas reconhecidas por autômatos finitos ○ Não foi feita nenhuma definição do que é uma linguagem regular ○ Um ser humano, ao olhar para uma linguagem, dificilmente consegue dizer se é ou não regular ○ Na verdade, não existe tal definição ● Mas existe uma distinção ○ Linguagens regulares vs não-regulares ○ A linha divisória é o fato de que ■ Autômatos finitos não conseguem contar Linguagens não regulares ● Linguagens que exigem um contador ○ Ex: comentários dentro de comentários, escopos aninhados em uma linguagem, parêntesis aninhados, etc ○ Ex: ■ (1+2*(3-5+(7*7))-6) ■ É preciso contar quantos parêntesis são abertos e quantos são fechados ● Tente imaginar um autômato que reconheça tais cadeias ○ Estados são a “memória” do autômato Linguagens não regulares ● Para reconhecer infinitos níveis de parêntesis aninhados, seriam necessários infinitos estados 0 1( ) Σ Σ 2( ) Σ ∞ ... Linguagens não regulares ● Outros exemplos: ○ {0n1n|n≥0} ○ {w|w tem número igual de 0s e 1s} ○ {ww| w seja uma cadeia sobre qualquer alfabeto} ● Mas veja esse exemplo: ○ {w|w tem um número igual de ocorrências de 01 e 10 como subcadeias} ○ Aparentemente, precisa contar ■ Mas essa linguagem é regular! (faça depois como exercício a prova, se duvidar) ● Formalmente: ○ Lema do bombeamento para linguagens regulares ○ Permite definir exatamente quais linguagens não são regulares Lema do bombeamento para linguagens regulares ● Formalmente: ○ Se A é uma linguagem regular, então existe um número p (o comprimento de bombeamento) tal que, se s é qualquer cadeia de A de comprimento no mínimo p, então s pode ser dividida em três partes, s=xyz, satisfazendo as seguintes condições: ■ Para cada i ≥ 0, xyiz ∈ A ■ |y| > 0 ■ |xy| ≤ p ● Informalmente: ○ Toda cadeia da linguagem contém uma parte que pode ser repetida um número qualquer de vezes (bombeada), com a cadeia resultante permanecendo na linguagem Lema do bombeamento para linguagens regulares ● Essa repetição ou bombeamento é a característica que faz com que seja sempre possível definir um número finito de estados para um autômato que reconheça a linguagem ● Uso do lema do bombeamento: ○ Provar que B não é regular ○ Contradição: suponha que B seja regular ○ 1. Encontre um p de forma que todas as cadeias de comprimento p ou maiores possam ser bombeadas ○ 2. Encontre uma cadeia s em B que tenha comprimento p ou mais, mas que não possa ser bombeada ○ 3. Demonstre que s não pode ser bombeada considerando todas as maneiras de dividir s em x,y e z, conforme o lema Lema do bombeamento para linguagens regulares ● Ex: {0n1n|n≥0} ○ 1. Seja p o comprimento de bombeamento ○ 2. Escolha s = 0p1p ■ s é maior que p (conforme o lema) ■ Portanto, o lema diz que s pode ser dividida em 3 partes, s=xyz, onde para qualquer i ≥ 0, xyiz está em B ● Ou seja, deve ser possível “bombear” y ○ 3. Mas é impossível!! ■ Primeira possibilidade: Suponha que y contém apenas 0s ● Ex: s = 000111, x=0, y=00, z=111 ● Sempre que bombearmos y, teremos como resposta uma cadeia que não pertence à linguagem ● Pois teremos como resultado mais 0s do que 1s Lema do bombeamento para linguagens regulares ● Ex: {0n1n|n≥0} ○ 3. Mas é impossível!! (continuação) ■ Segunda possibilidade: Suponha que y contém apenas 1s ● Ex: s = 000111, x=000, y=11, z=1 ● Sempre que bombearmos y, teremos como resposta uma cadeia que não pertence à linguagem ● Pois teremos como resultado mais 1s do que 0s ■ Terceira possibilidade: y contém 0s e 1s ● Ex: s = 000111, x=00, y=01, z=11 ● Sempre que bombearmos y, teremos como resposta uma cadeia que não pertence à linguagem ● Pois teremos como resultado a presença de 0s e 1s alternados Lema do bombeamento para linguagens regulares ● Ex: {0n1n|n≥0} ○ Ou seja, é impossível existir uma divisão de s de acordo com o lema do bombeamento ○ Isso é uma contradição! ● Ou seja, se não fizemos nada de errado, a suposição de que B é regular é falsa ○ Portanto, B não é regular Lema do bombeamento para linguagens regulares ● O “truque” é encontrar o s ● Requer um pouco de pensamento criativo ● Tentativa e erro ● Busca pela “essência” da não-regularidade de B ● Conhecimento das restrições do lema ○ (|y| > 0, |xy| ≤ p, etc) Linguagens não regulares ● Ok, descobri que uma linguagem não é regular ○ Como resolver o problema? ○ Como obter uma implementação? ● Bom, se o problema é que um autômato finito não consegue contar... ○ ... basta adicionar um contador! ● Essa é exatamente a solução ○ Mais poder aos autômatos ○ Classe maior de linguagens ○ Mais detalhes nas próximas aulas! Fim Aula 11 - Linguagens não regulares Slides/LFA.2015.2.Aula12.Linguagens.Livres.De.Contexto.pdf Linguagens Formais e Autômatos Aula 12 - Linguagens Livres de Contexto Prof. Dr. Daniel Lucrédio Departamento de Computação / UFSCar Última revisão: ago/2015 Referências bibliográficas ● Introdução à teoria dos autômatos, linguagens e computação / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: Introduction to automata theory, languages, and computation - ISBN 85-352- 1072-5) ○ Capítulo 5 - Seções 5.1, 5.2 e 5.3 ● Introdução à teoria da computação / Michael Sipser ; tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the theory of computation. "Tradução da segunda edição norte-americana" - ISBN 978-85-221-0499-4) ○ Capítulo 2 - Seção 2.1 Linguagens livres de contexto ● Linguagens regulares permitem descrever muitas coisas práticas ○ Ex: busca textual, mecanismos simples de comunicação, máquinas e protocolos simples ● Mas são limitadas ○ “Não conseguem contar” → autômatos finitos ● Mas e se adicionarmos um contador aos autômatos finitos? Linguagens livres de contexto Entrada q6 13 + - Linguagens livres de contexto ● Ex: anbn q0 q2q1 q3 a, ++ b, -- a C=0? b, -- Linguagens livres de contexto ● Uma classe maior de linguagens ○ Linguagens livres de contexto ● Inicialmente, foram uma maneira de entender a linguagem humana ○ Gramáticas livres de contexto ■ Formalização das regras gramaticais da linguagem humana ● Característica principal: recursão ○ Ex: linguagens naturais: frases nominais dentro de frases verbais, e vice-versa ● O Brasil foi campeão da copa do mundo de futebol ○ Sujeito, predicado, verbo, objeto direto, etc... Linguagens livres de contexto ● Entendendo um pouco mais: ○ As linguagens humanas possuem símbolos ■ Palavras ○ Possuem também regras ■ Gramática (português, inglês, etc) ○ Existem frases válidas e inválidas ● Ex: ○ O Brasil foi campeão da copa do mundo de futebol ○ Campeão da mundo do foi futebol o de copa Brasil Linguagens livres de contexto ● A partir do estudo da linguagem humana, chegou-se a um modelo matemático formal sobre uma classe de linguagens ● O conceito é o mesmo das linguagens regulares ● Linguagens = problemas ● Um problema é: ○ Dada uma cadeia, determinar se pertence ou não à linguagem ○ A diferença é que aqui, o conceito cadeia é diferente ... ○ ... e as regras de definição da linguagem são mais poderosas do que simples transições em um autômato finito Linguagens livres de contexto ● Linguagens regulares: ○ Base: símbolos de um alfabeto ○ Regras (“gramática”): expressões regulares ○ Característica: ■ estados finitos / não conseguem contar / lema do bombeamento para linguagens regulares ● Linguagens livres de contexto: ○ Base: símbolos terminais ■ Pode-se pensar que um símbolo terminal é um símbolo de um alfabeto ■ Mas cada símbolo terminal pode ser uma cadeia sobre uma linguagem regular (uma palavra) ○ Regras (“gramática”): gramáticas livres de contexto ○ Característica: ■ recursão simples / consegue contar (de forma limitada) / lema do bombeamento para linguagens livres de contexto Gramáticas livres de contexto Gramáticas livres de contexto ● Gramática: a melhor forma de “ver” uma linguagem (ex: ER melhor do que autômatos finitos) ○ No caso das linguagens livres de contexto, temos as gramáticas livres de contexto A → 0A1 A → B B → # Regras de substituição ou produções Gramáticas livres de contexto A → 0A1 A → B B → # Lado esquerdo ou cabeça: sempre um único símbolo. Esses símbolos são chamados de variáveis ou não-terminais Lado direito ou corpo: uma cadeia de símbolos. Podem ter variáveis e outros símbolos, chamados de terminais Uma das variáveis é designada como a variável ou símbolo inicial. É a variável que aparece do lado esquerdo da primeira regra. (Neste exemplo, A é o símbolo inicial) Gramáticas livres de contexto A → 0A1 A → B B → # Sempre que houver mais de uma produção para uma mesma variável, podemos agrupá-las com o símbolo “|”. A → 0A1 | B B → # Gramáticas livres de contexto ● Variáveis normalmente são representadas por letras maiúsculas (A,B, C, ....) ● Terminais normalmente são representados por letras minúsculas, números, símbolos, etc... (a,b,c,0,1,2,#,...) ○ Assim como nos alfabetos que estudamos até então ● Mas na prática usamos nomes mais significativos Exemplo OraçãoSubstantiva → SubstantivoComplexo | SubstantivoComplexo FrasePreposicional ; FraseVerbal → VerboComplexo | VerboComplexo FrasePreposicional ; FrasePreposicional → Preposição SubstantivoComplexo ; SubstantivoComplexo → Artigo Substantivo | OraçãoSubstantiva ; VerboComplexo → Verbo | Verbo OraçãoSubstantiva ; Artigo → o | a | um | uma | ε ; Substantivo → armário | funcionário | gerente | cadeira | braços | aço ; Verbo → gosta | brinca | olha ; Preposição → para | com | de | sem ; Gramáticas livres de contexto ● Terminais podem ser cadeias (sequências) simples: ○ Ex: “menino”, “if”, “while”, “int”, “char”, etc... ● Podem também ser cadeias descritas com linguagens regulares (ex: compiladores) ○ Ex: ■ [a-zA-Z][a-zA-Z0-9]* : identificadores válidos de uma linguagem de programação ● Ex: posX1, valorAluguel, rgCliente ■ “[^”]*” : literais do tipo string ● Ex: “Telefone:”, “Digite o texto abaixo”, “Ocorreu um erro” ■ [0-9]+ : números inteiros Gramáticas livres de contexto ● Definição formal G = (V,T,P,S) V = conjunto de variáveis T = conjunto de terminais P = conjunto de produções S = símbolo inicial ● Ex: Gpalíndromos = ({P},{0,1},A,P) A = { P → ε P → 0 P → 1 P → 0P0 P → 1P1 } Gramáticas livres de contexto ● Como uma gramática descreve uma linguagem? ● Duas formas: ○ Inferência recursiva ○ Derivação ● Ex: Gramática para expressões aritméticas ○ V = {E,I} ○ T = {+,*,(,),a,b,0,1} ○ P = conjunto de regras ao lado ○ S = E E → I E → E + E E → E * E E → (E) I → a I → b I → Ia I → Ib I → I0 I → I1 Gramáticas livres de contexto ● Inferência recursiva ○ Dada uma cadeia (conjunto de símbolos terminais) ○ Do corpo para a cabeça ● Ex: a*(a+b00) ○ a*(a+b00) ⇐ a*(a+I00) ⇐ a*(a+I0) ⇐ a*(a+I) ⇐ a*(a+E) ⇐ a*(I+E) ⇐ a*(E+E) ⇐ a*(E) ⇐ a*E ⇐ I*E ⇐ E*E ⇐ E Gramáticas livres de contexto ● Derivação ○ Dada uma cadeia (conjunto de símbolos terminais) ○ Da cabeça para o corpo ● Ex: a*(a+b00) ○ E ⇒ E*E ⇒ I*E ⇒ a*E ⇒ a*(E) ⇒ a*(E+E) ⇒ a*(I+E) ⇒ a*(a+E) ⇒ a* (a+I) ⇒ a*(a+I0) ⇒ a*(a+I00) ⇒ a*(a+b00) ● Símbolo de derivação: ⇒ ● Derivação em múltiplas etapas: ⇒* (obs: asterisco acima da seta) ○ E ⇒* a*(E) ○ a*(E+E) ⇒* a*(a+I00) ○ E ⇒* a*(a+b00) Gramáticas livres de contexto ● Derivações mais à esquerda ○ Sempre substituir a variável mais à esquerda ○ Notação: ⇒lm, ⇒ * lm ● Derivações mais à direita ○ Sempre substituir a variável mais à direita ○ Notação: ⇒rm, ⇒ * rm Formas sentenciais ● Derivações a partir do símbolo inicial ● Formas sentenciais à esquerda ○ Obtidas somente com derivações mais à esquerda ● Formas sentenciais à direita ○ Obtidas somente com derivações mais à direita Ex: E ⇒lm E*E ⇒lm I*E ⇒lm a*E ⇒lm a*(E) Ex: E ⇒rm E*E ⇒rm E*(E) ⇒rm a*(E+E) ⇒rm a* (E+I) Exercícios ● Dada a gramática descrita pelas produções
Compartilhar