Aula 4 - Operações e Expressões Regulares

Teoria da Computação Aula 4 Operações e Expressões Regulares Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Agenda Operações regulares Recapitular linguagens regulares Definição Exemplos Expressões regulares Definição Equivalência com autômatos finitos 2 Operações regulares Definimos que Uma linguagem é chamada regular se existir um autômato finito capaz de reconhecêla 3 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 4 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 Qual o alfabeto desta linguagem 5 Operações regulares Exemplo consideremos a linguagem definida pelo conjunto de números que começam em 1 e são múltiplos de 5 1015100105110115120125130135 Qual o alfabeto desta linguagem Esta linguagem é regular 6 Operações regulares 9 q0 q1 q2 1 1 Operações regulares 10 q0 q1 q2 1 1 0129 Operações regulares 11 q0 q1 q2 1 1 q3 0129 q4 Operações regulares 12 q0 q1 q2 1 1 q3 0129 q4 05 05 Operações regulares 13 q0 q1 q2 1 1 q3 0129 q4 05 05 Operações regulares 14 q0 q1 q2 1 1 0129 q4 05 05 q3 Operações regulares 15 q0 q1 q2 1 1 0129 q4 05 05 05 05 q3 Operações regulares 16 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 q3 Operações regulares 17 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 10 q3 Operações regulares 18 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 100 q3 Operações regulares 19 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 152 q3 Operações regulares 20 q0 q1 q2 1 1 0129 q4 05 05 05 05 05 05 1205 q3 Operações regulares Como obtivemos um autômato capaz de reconhecer a linguagem formada pelo conjunto 1015100105110115120125130135 então podemos afirmar que esta é uma linguagem regular 21 Operações regulares Uma linguagem com 1 elemento exemplo BRASIL é regular 22 Operações regulares Uma linguagem com 1 elemento exemplo BRASIL é regular Sim 23 q0 q1 q2 q3 q4 q5 q6 q7 B R A S I L B R A S I L ABCZ ABCZ Operações regulares Uma linguagem com 2 elementos exemplo BRASILCHILE é regular 24 Operações regulares Uma linguagem com 2 elementos exemplo BRASILCHILE é regular Sim 25 q0 q1 q2 q3 q4 q5 q6 q11 B R A S I L BC R A S I L ABCZ q7 q8 q9 q10 C H I L E ABCZ H I L E Operações regulares Uma linguagem com N elementos é regular 26 Operações regulares Uma linguagem com N elementos é regular Sim Podemos construir um autômato formado por caminhos tais que cada um corresponda a um elemento da linguagem 27 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto 28 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto A string com 0 elementos é representada por 𝛆 29 Operações regulares Uma string sequência de elementos de um alfabeto pode ser formada por 0 1 2 elementos do alfabeto A string com 0 elementos é representada por 𝛆 Cada string por sua vez é um elemento de uma linguagem 30 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares 31 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em aritmética temos dois tipos de elementos objetos básicos números operações x 32 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em teoria da computação temos objetos básicos linguagens operações 33 Operações regulares Agora que temos conhecimento sobre linguagens regulares podemos definir o conceito de operações regulares Em teoria da computação temos objetos básicos linguagens operações união concatenação estrela 34 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens 35 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 36 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 A B a1 a2 a3 b1 b2 b3 c1 c2 c3 37 Operações regulares Sejam A a b c e B 1 2 3 duas linguagens A B a b c 1 2 3 A B a1 a2 a3 b1 b2 b3 c1 c2 c3 A 𝛆 a b c aa ab ac ba bb bc ca cb cc aaa aab 38 Operações regulares Sejam A e B duas linguagens A B x x A ou x B 39 Operações regulares Sejam A e B duas linguagens A B x x A ou x B A B xy x A e y B 40 Operações regulares Sejam A e B duas linguagens A B x x A ou x B A B xy x A e y B A x1x2x3xk k 0 e xi A 41 Operações regulares As operações de união e concatenação são binárias isto é possuem dois operandos A B A B A operação estrela é unária isto é possui apenas um operando A 42 Operações regulares O resultado da aplicação de uma operação regular sobre uma linguagem regular é também uma linguagem regular 43 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING 44 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING Defina A B A B A 45 Operações regulares Exemplo A BRASIL CHILE CANADÁ B POR ESP ING Como poderíamos obter um linguagem tal que cada elemento correspondesse ao país com todos os idiomas porém com um símbolo de separação entre o país e o idioma BRASILPOR BRASILESPBRASILINGCHILEPOR 46 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens 47 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 48 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 49 Expressões regulares Podemos expandir o conceito das operações regulares criando sentenças com as strings das linguagens Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 50 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 51 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 52 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 As duas partes devem ser concatenadas 53 Expressões regulares Exemplo seja o alfabeto 01 Desejamos obter uma linguagem regular que contemple todas as strings tais que o primeiro elemento é seguindo por uma sequência de 0s 010010000100000010000000010000 Para o primeiro elemento podemos definir a união entre 0 e 1 Para os demais elementos podemos definir a operação estrela sobre 0 As duas partes devem ser concatenadas Resultado 0 10 54 Expressões regulares Simplificando a notação podemos representar um conjunto 0 ou 1 simplesmente pelo elemento 0 ou 1 Resultado 0 10 0 10 55 Expressões regulares Simplificando a notação podemos representar um conjunto 0 ou 1 simplesmente pelo elemento 0 ou 1 Resultado 0 10 0 10 Podemos representar a operação de concatenação pelo posicionamento de uma linguagem na sequência de outra Resultado 0 10 0 10 ou ainda 0 10 0 10 56 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares 57 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares Podemos então afirmar que se uma linguagem foi obtida a partir de uma expressão regular então esta é uma linguagem regular 58 Expressões regulares Observamos que é possível obter linguagens com base em expressões regulares Podemos então afirmar que se uma linguagem foi obtida a partir de uma expressão regular então esta é uma linguagem regular Usando a nossa definição de linguagem regular com base na existência de um autômato podemos concluir que existe ao menos 1 autômato associado a uma expressão regular 59 Expressões regulares Tomando o exemplo da expressão 0 10 podemos montar o autômato 60 Expressões regulares Tomando o exemplo da expressão 0 10 podemos montar o autômato 61 q0 q2 q1 01 0 1 01 Expressões regulares Qual autômato corresponde à expressão regular ae ea U 𝜀 62