Lr.pdf

Ciência da Computação

Teoria da Computação Linguagens Regulares Prof. Hilário Tomaz Alves de Oliveira [email protected]

1

Roteiro 2. Linguagens Regulares 2.1 Autômatos Finitos Determinísticos.

2.2 Autômatos Finitos Não Determinísticos. 2.3 Expressões Regulares.

2.4 Equivalências entre os modelos. 2.5 Lema do Bombeamento. 2

Leitura recomendada • Capítulo 1 – Linguagens Regulares.

3

Introdução • A teoria da computação começa com uma pergunta: O que é um computador? • Parece uma questão tola, já que todos nós usamos diariamente um computador. • Os computadores reais são bastante complicados para nos permitir construir uma teoria matemática manejável sobre eles diretamente. • Começaremos com o modelo mais simples, denominado Máquina de

estados finitos ou Autômato finito.

4

Autômatos Finitos • Autômatos Finitos (AF) são bons modelos para computadores com uma quantidade extremamente limitada de memória.

• O que um computador pode fazer com uma memória tão pequena? • Interagimos com tais computadores o tempo todo, pois eles residem no centro de vários dispositivos eletromecânicos.

5

Autômatos Finitos - Aplicações

6

Exemplo - Visão superior de uma porta automática

7

Exemplo – Funcionamento (Diagrama de Estados)

8

Exemplo – Funcionamento (Tabela de Transições)

9

Autômatos Finitos • Pensar em um controlador de porta automática como um Autômato finito é útil porque sugere formas padrão de representação.

• Esse controlador é um computador que tem apenas um bit de memória, capaz de registrar em qual dos dois estados o controlador está.

• Outros dispositivos comuns têm controladores com memórias bem maiores. • Controlador de elevador: • (1) Andar no qual o elevador está; e (2) Sinais recebidos dos botões. 10

Autômatos Finitos • Os autômatos finitos e suas contrapartidas probabilísticas cadeias de Markov são ferramentas úteis quando estamos tentando reconhecer padrões em dados. • Esses dispositivos são utilizados em processamento de voz e em reconhecimento de caracteres. • As cadeias de Markov têm sido usadas para modelar e fazer previsões de mudança de preços em mercados financeiros. 11

Autômatos Finitos - Exemplo 𝑀1

• A Figura acima é chamada de diagrama de estados de 𝑀1 . • M1 possui 3 estados. • q1 é o estado inicial de 𝑀1 . • q2 é o estado de aceitação (estado final) de 𝑀1 .

• As setas saindo ou entrando nos estados são as transições.

12

Autômatos Finitos - Funcionamento de 𝑀1 • 𝑀1 recebe como entrada uma cadeia de símbolos. • Como saída, 𝑀1 aceita ou rejeita a cadeia de entrada. Ao final do

processamento da cadeia de entrada: • Aceita: se 𝑀1 estiver em um estado de aceitação. • Rejeita: se 𝑀1 estiver em qualquer outro estado que não seja de aceitação. 13

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.14

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.15

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.16

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.17

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.18

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.19

Autômatos Finitos - Funcionamento de 𝑀1 • Entrada: 1101. • O processamento de 𝑀1 será executado da seguinte forma: 1. Começa no estado 𝑞1 ; 2. Lê o símbolo 1, segue a transição de 𝑞1 para 𝑞2 ; 3. Lê o símbolo 1, segue a transição de 𝑞2 para 𝑞2 ; 4. Lê o símbolo 0, segue a transição de 𝑞2 para 𝑞3 ; 5. Lê o símbolo 1, segue a transição de 𝑞3 para 𝑞2 ; 6. Aceita a cadeia porque 𝑀1 está no estado de aceitação 𝑞2 no final da entrada.

20

Autômatos Finitos • Definição. Um autômato finito é uma 5-upla (Q, , , q0, F), onde:

• Q é um conjunto finito conhecido como os estados, •  é um conjunto finito chamado de alfabeto, • : Q x  → Q é a função de transição, • q0 ∈ Q é o estado inicial, e • F ⊆ Q é o conjunto de estados de aceitação (estados finais). 21

Autômatos Finitos - Exemplo 𝑀1 • Podemos descrever M1 formalmente escrevendo M1 = {Q, , , q1, F}, onde: • Q = {q1, q2, q3},

•  = {0, 1}, •  é descrita como

0

1

q1

q1

q2

q2

q3

q2

q3

q2

q2

• q1 é o estado inicial, e • F = {q2}

22

Autômatos Finitos • Se A é o conjunto de todas as cadeias que a máquina M aceita, dizemos que A é a linguagem da máquina M e escrever L(M) = A. • Dizemos que M reconhece A ou que M aceita A.

• L(M1) = {w | w termina com o símbolo 1 ou um número par de 0s após o último 1.}.

23

Qual a definição formal de 𝑀2 ? • Podemos descrever M2 formalmente escrevendo M2 = {Q, , , q1, F}, onde:

24

Qual a definição formal de 𝑀2 ? • Podemos descrever M1 formalmente escrevendo M1 = {Q, , , q1, F}, onde: • Q = {q1, q2},

•  = {0, 1}, •  é descrita como

0

1

q1

q1

q2

q2

q1

q2

• q1 é o estado inicial, e • F = {q2}

25

Autômatos Finitos - 𝑀2 • Uma boa maneira para começar a entender uma Máquina é testá-la com algumas amostras de cadeias de entrada.

• Possíveis entradas (w): • 0101010 • 1100011 • 1010101

• Qual a linguagem reconhecida por 𝑀2 ? 26

Autômatos Finitos - 𝑀2 • Uma boa maneira para começar a entender uma Máquina é testá-la com algumas amostras de cadeias de entrada.

• Possíveis entradas (w): • 0101010 • 1100011 • 1010101

• Qual a linguagem reconhecida por 𝑀2 ? • L(𝑀2 ) = {w | w termina com 1.} 27

Autômatos Finitos - Exemplo 𝑀3 • 𝑀3 é muito similar à 𝑀2 , exceto pela posição do estado de aceitação.

• Como o estado inicial também é um estado de aceitação, então 𝑀3 aceita a cadeia vazia ().

• L(𝑀3 ) = {w | w é a cadeia vazia  ou termina com 0.} 28

Autômatos Finitos - Exemplo 𝑀4 • Descreva L(𝑀4 ).

29

Autômatos Finitos - Exemplo 𝑀5 • M5 mantém “contador da soma”

dos símbolos numéricos de entrada. •  = {0, 1, 2, }

• Toda vez que recebe o símbolo ela reinicia o contador de soma para 0. • M5 aceita w se o valor do contador da soma for 0 ou múltiplo de 3.

30

Definição Formal de Computação • Seja M= (Q, , , q0, F) um autômato finito e suponha que w = w1w2...wn seja uma cadeia onde cada wi é um membro do alfabeto.

• M aceita w se uma sequência de estados r0, r1...rn em Q existe com três condições: a) r0 = q0, b) (ri,wi+1) = ri+1, para i = 0,...,n-1; e c) rn  F.

Dizemos que M reconhece a linguagem A se L(A) = {w | M aceita w}. 31

Linguagem Regular

• Uma linguagem é chamada de uma LINGUAGEM REGULAR se algum autômato finito a reconhece.

32

Máquina 𝑀5 - Computação • Seja a máquina 𝑀5 e a cadeia w: 1022012 • Então𝑀5 aceita conforme a definição formal de computação, porque a sequência de estados na qual ela entra quando está computando sobre w é: • 𝑞0 , 𝑞1 , 𝑞1 , 𝑞0 , 𝑞2 , 𝑞1 , 𝑞0 , 𝑞0 , 𝑞1 , 𝑞0 • O que satisfaz as três condições.

33

Máquina 𝑀5 - Computação • L(𝑀5 ) = {w | • a soma dos símbolos em w é múltiplo 3,

• exceto que RESET retorna o contador para 0.}

• Como 𝑀5 reconhece essa linguagem, ela é

uma Linguagem Regular. 34

Operações Regulares

35

Operações Regulares • Na teoria da computação os objetos são linguagens e as ferramentas incluem operações especificamente projetadas para manipulá-las.

• Definimos três operações sobre linguagens, chamadas operações regulares, e as usamos para estudar propriedades de linguagens regulares.

36

Operações Regulares

37

Operações Regulares – Exemplo usando Conjuntos

38

Operação de União • 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, o mesmo acontece com A1  A2.

• Ideia da Prova: Se A1 e A2 são linguagens regulares, então existem AFs M1 e M2 que as reconhecem, respectivamente. • Vamos fazer uma prova construtiva, ou seja, vamos construir um AF M, que

reconheça A1  A2, a partir de M1 e M2. 39

Operação de União - Prova

40

Operação de União - Prova

41

Operação de União - Prova

42

Operação de União – Prova Exemplo • M1 é um AF que reconhece as cadeias w com um número par de 1s. 0 1

0 qq11

q2 1

• M2 é um AF que reconhece as cadeias w com um ímpar de 0s. 1 0

1 qq13

q4 0 43

Operação de União – Prova Exemplo • Construir um M = M1  M2 • L(M) = { w | w possui um número par de 1s ou um número ímpar de 0s}.

• M1=(Q1,1,1,q1,F1) e M2=(Q2,2,2,q3,F2)

0

q1,q3

• M =(Q1Q2,,,(q1,q3),F)

0 1

1

• ((r1,r2),a) = (1(r1,a),2(r2,a)) • F= (F1Q2)  (Q1F2 )

q1,q4 1

1 0

q2,q4

q2,q3 0

44

Operação de Concatenação • 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, o mesmo acontece com A1  A2.

• De modo análogo à prova do teorema anterior, vamos construir um autômato M para reconhecer A1A2 a partir de M1 e M2. • M aceita sua entrada se ela puder ser quebrada em duas partes, onde M1

aceita a primeira parte e M2 aceita a segunda parte. 45

Operação de Concatenação • O problema é que M não sabe onde quebrar sua entrada.

• Para resolver esse problema introduzimos uma nova técnica chamada NÃO-DETERMINISMO.

46

Não-determinismo

47

Não-determinismo • Até agora em nossa discussão, todo passo de uma computação segue de uma maneira única do passo precedente. • Quando a máquina está em um dado estado e lê o próximo símbolo de entrada, sabemos qual será o próximo estado. • Chamamos isso de computação determinística.

• Em uma máquina não-determinística, várias escolhas podem existir para o próximo estado em qualquer ponto. • Não-determinismo é uma generalização de determinismo.

48

Exemplo 𝑁1

• L(𝑁1 ) = {w | w contém 101 ou 11 como uma subcadeia} 49

Computação Não-determinística

50

Computação de Exemplo 𝑁1 • Entrada: 010110

51

Exemplo - AFN q2

q3

q4

q6

q7

q1 q5

52

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

53

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

54

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

55

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

56

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

57

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

58

Exemplo - AFN q2

q3

q4

q5

q6

q7

q1

59

Exemplo - AFN • Como um dos caminhos terminou em um estado final, então a palavra é ACEITA pelo

q2

q3

q4

q5

q6

q7

q1

AFND.

60

Exemplo 𝑁2

61

AFD equivalente ao AFN 𝑁2 • Todo AFN pode ser convertido num AFD equivalente, mas às vezes esse AFD pode ter muito mais estados.

• O menor AFD para a linguagem L(A) contém oito estados. • Entender o funcionamento do

AFN é muito mais fácil.

62

Exemplo 𝑁3 • L(𝑁3 ) = {0𝑘 | k é múltiplo de 2 ou 3}

63

Definição Formal AFN

64

Definição Formal 𝑁1

65

Definição Computação AFN

66

Equivalência entre AFD e AFN

67

Equivalência AFD e AFN • Teorema: Todo autômato finito não-determinístico tem um autômato finito determinístico equivalente.

• IDÉIA DA PROVA: Se uma linguagem é reconhecida por um AFN, então temos de mostrar a existência de um AFD que também a reconhece. • A ideia é converter o AFN num AFD equivalente que simule o AFN.

68

Equivalência AFD e AFN • Vamos converter um AFN em um AFD equivalente que o simule. • Se k é o número de estados do AFN, ele tem 2k subconjuntos de estados. • Cada subconjunto corresponde a uma das possibilidades de que o AFD tem que se lembrar, portanto o AFD que simula o AFN terá 2k estados.

69

Equivalência AFD e AFN • Considere o AFN 𝑁4 seguinte:

70

Equivalência AFD e AFN • O conjunto de estados Q’ do AFD equivalente terá 23 = 8 estados. • Q’ = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

• O estado inicial é E({1}) ➔ o conjunto de estados que são atingíveis a partir

do estado 1 viajando ao longo de setas 𝜀, mais o próprio símbolo 1. • E({1}) = {1, 3}

71

Equivalência AFD e AFN • Os novos estados de aceitação são aqueles contendo o estado de aceitação de 𝑁4 . • F’ = {{1}, {1,2}, {1,3}, {1,2,3}}

• Finalmente, determinamos a função de transição do novo AFD. • Cada um dos estados do AFD vai para um lugar dada a entrada do símbolo a e um lugar quando a entrada é o símbolo b. 72

Equivalência AFD e AFN • O estado {1} vai para estado ∅ na entrada a, porque não existe nenhuma transição para a entrada a no estado {1}. • No AFD, o estado {2} vai para {2,3} com a entrada a, porque no 𝑁4 , o estado 2 vai para ambos 2 e 3 com a entrada a e não consegui ir mais longe. • O estado {3} vai para {1,3} na entrada a, pois em 𝑁4 o estado 3 vai para o estado 1 na entrada a e 1, por sua vez, vai para 3 com uma seta 𝜀. 73

AFD equivalente ao AFN 𝑁4

74

AFD (simplificado) equivalente ao AFN 𝑁4 • Podemos simplificar o AFD observando que nenhuma seta aponta para os estados {1} e {1,2}, portanto eles podem ser removidos sem afetar o AFD.

75

Linguagem Regular

• Uma linguagem é REGULAR se e somente se algum autômato finito não-determinístico a reconhece.

76

Fecho sob as Operações Regulares

77

Operação de União • Teorema: A classe de linguagens regulares é fechada sob a operação de união.

• IDÉIA DA PROVA: Temos as linguagens regulares A1 e A2 e desejamos provar que A1  A2 também é regular.

78

Construção de um AFN para reconhecer A1  A2

79

Operação de Concatenação • Teorema: A classe de linguagens regulares é fechada sob a operação de concatenação.

• IDÉIA DA PROVA: Temos as linguagens regulares A1 e A2 e desejamos provar que A1 ∘ A2 também é regular.

80

Construção de um AFN para reconhecer A1 ∘ A2

81

Operação Estrela • Teorema: A classe de linguagens regulares é fechada sob a operação estrela.

• IDÉIA DA PROVA: Dada a linguagem A1 desejamos provar que A1* também é regular.

82

Construção de um AFN para reconhecer A1*

83

Expressões Regulares

84

Expressões Regulares • Na aritmética, podemos usar as operações + e  para montar expressões tais como (5 + 3)  4. • Similarmente, podemos usar as operações regulares para montar expressões descrevendo linguagens, que são chamadas Expressões Regulares (ER).

• Exemplo: • (0  1)0*

85

Expressões Regulares • O valor de uma expressão aritmética é um número. • No exemplo passado (5 + 3)  4 é 32.

• O valor de uma expressão regular é uma linguagem. • No exemplo (0  1)0* ➔ (0  1) ∘ 0* • A linguagem das cadeias binárias que começam com 1 ou 0 seguido por um número qualquer de 0s. 86

Expressões Regulares • Exemplo: (0  1)* • Essa ER começa com a linguagem (0  1) e aplica a operação *. • L(ER) = todas as cadeias constituídas de 0s e 1s.

• Se  = {0,1}, pode escrever  como uma abreviação para (0  1) • * = (0  1)*

• Qual a linguagem descrita pela ER (0*)  (*1)? 87

Expressões Regulares - Precedência • A ordem de precedência dos operadores é • (R) • R* • R1R2 • R1  R2

• Então ab*c|d é analisada como sendo ((a(b*))c)|d 88

Expressões Regulares - Definição

89

Expressões Regulares - Operadores • Operadores de repetição: • R∗ ➔ Zero ou mais ocorrências de R • R+ ➔ Uma ou mais ocorrências de R (abreviação de RR*) • R𝐾 ➔ k repetições de R

90

Expressões Regulares - Operadores • Se tomarmos R como uma expressão regular qualquer, temos as identidades a seguir. • R∅ =R • R∘𝜀=R

• O inverso pode não ser verdadeiro. • R  𝜀 pode não ser R • R ∘ ∅ pode não ser R 91

Expressões Regulares - Exemplo • Suponha que nosso alfabeto é formado por letras, números, ‘@’, e ‘.’ • Por simplicidade ‘a’ representa letras e números.

• A expressão regular a seguir pode ser usada para extrair endereços de email: aa*(.aa*)*@aa*.aa*(.aa*)* • [email protected] • [email protected]

• [email protected] • [email protected]

92

Expressões Regulares - Exemplo • Podemos simplificar essa ER para reconhecer e-mails. • aa*(.aa*)*@aa*.aa*(.aa*)*

• Exemplos: • [email protected] • [email protected] • [email protected]

• [email protected] 93

Expressões Regulares - Exemplo • Podemos simplificar essa ER para reconhecer e-mails. • aa*(.aa*)*@aa*.aa*(.aa*)* • a+ (. a+ )*@ a+ . a+ (. a+ )*

• Exemplos: • [email protected] • [email protected]

• [email protected] • [email protected]

94

Expressões Regulares - Exemplo • Podemos simplificar essa ER para reconhecer e-mails • aa*(.aa*)*@aa*.aa*(.aa*)* • a+ (. a+ )*@ a+ . a+ (. a+ )*

• Exemplos: • [email protected] • [email protected]

• [email protected] • [email protected]

95

Expressões Regulares - Exemplo • Podemos simplificar essa ER para reconhecer e-mails • aa*(.aa*)*@aa*.aa*(.aa*)* • a+ (. a+ )*@ a+ . a+ (. a+ )* • a+ (. a+ )*@ a+ (. 𝑎+ )+

• Exemplos: • [email protected] • [email protected] • [email protected], [email protected]

96

Equivalência entre ER e Autômatos

97

Equivalência ER e Autômatos • Expressões regulares e autômatos finitos são equivalentes em seu poder descritivo. • Teorema: Uma linguagem é regular se e somente se alguma expressão regular a descreve. • Este teorema tem duas direções. • Todo ER pode ser convertida para um AF

• Todo AF pode ser convertido para uma ER*. 98

Equivalência ER e Autômatos • LEMA: Se uma linguagem é descrita por uma expressão regular, então ela é regular.

• IDEIA DE PROVA: Vamos supor que tenhamos uma expressão regular R descrevendo alguma linguagem A. • Mostramos como converter R em um AFN que reconhece A.

99

Equivalência ER e Autômatos • PROVA: Vamos converter R em um AFN. Consideramos os seis casos na descrição formal de expressões regulares.

100

Equivalência ER e Autômatos

101

Equivalência ER e Autômatos 4. R1  R2

5. R1  R2

6. R* • Para os três últimos casos usamos as construções dadas nas provas de que a classe de linguagens regulares é fechada sob as operações regulares.

102

Equivalência ER e Autômatos - Exemplos

103

Equivalência ER e Autômatos - Exemplos

104

Equivalência ER e Autômatos • Construindo um AFN a partir da expressão regular (a  b)*

105

Linguagens não-regulares • Para entender o poder dos autômatos finitos e das expressões regulares você precisa entender também suas limitações. • Exemplo: B = { 0𝑛 1𝑛 | n ≥ 0} • Existe um método para provar que linguagens, como a anterior, não são regulares. • LEMA DO BOMBEAMENTO. 106

Dúvidas

107

Próximos Assuntos .... • Aula 4 – Linguagens Livres de Contexto.

108