1

Estado Final Único para NFAs e DFAs

2

Observação

Todo Autômato Finito (NFA ou DFA)

pode ser convertido em um NFA equivalente

com um único estado final

3

a

b

ba NFA

NFA Equivalente

a

b

ba

Exemplo

4

NFAEm Geral

NFA Equivalente

Estadofinal único

5

Caso Extremo

NFA sem estado final

Adicione um estado final sem transições

6

Algumas Propriedades de Linguagens Regulares

7

Propriedades1L 2L

21LLConcatenação:

*1LStar:

21 LL União:

São LinguagensRegulares

Para linguagens regulares e vamos provar que:

8

Dizemos:Linguagens Regulares são fechadas sob

21LLConcatenação:

*1LStar:

21 LL União:

9

1LLinguagem Regular

11 LML

1M

Estado final único

NFA 2M

2L

Estado final único

22 LML

Linguagem Regular

NFA

10

Exemplo

}{1 baL na

b

1M

baL 2ab2M

11

UniãoNFA para

1M

2M

21 LL

12

Exemplo

ab

ab

}{1 baL n

}{2 baL

}{}{21 babaLL n NFA para

13

Concatenação

NFA para 21LL

1M 2M

14

Exemplo NFA for

ab ab

}{1 baL n}{2 baL

}{}}{{21 bbaababaLL nn

15

Operação StarNFA para *1L

1M

*1L

16

Exemplo

NFA para *}{*1 baL n

ab

}{1 baL n

17

Expressões Regulares

18

Expressões RegularesExpressões Regulares descrevem linguagens regulares

Exemplo:

descreve a linguagem

*)( cba

,...,,,,,*, bcaabcaabcabca

19

Definição Recursiva,,

11

21

21

*rrrrrr

São expressões regulares

Expressões regulares primitivas :

2r1rDadas expressões regulares e

precedência dos operadoresmaio

rmenor

20

Exemplos

)(* ccbaUma expressão regular:

baNão é uma expressão regular :

21

Linguagem de uma Expressão Regular

: linguagem da expressão regular

Exemplo

rL r

,...,,,,,*)( bcaabcaabcacbaL

22

Definição

Para expressões regulares primitivas:

aaL

L

L

23

Definição (continuação)

Para expressões regulares e

1r 2r

2121 rLrLrrL

2121 rLrLrrL

** 11 rLrL

11 rLrL

24

ExemploExpressão Regular *aba

*abaL *aLbaL *aLbaL *aLbLaL

*aba ,...,,,, aaaaaaba

,...,,,...,,, baababaaaaaa

25

Exemplo

Expressão Regular bbabar *

,...,,,,, bbbbaabbaabbarL

26

Exemplo

Expressão Regular bbbaar **

27

Exemplo

Expressão Regular *)10(00*)10( r

)(rL = { todos os strings com pelo menos dois 0s consecutivos }

28

Exemplo

Expressão Regular )0(*)011( r

)(rL = {todos os strings sem dois 0s consecutivos }

29

Expressões Regulares Equivalentes

Definição:

Expressões regulares e

são equivalentes se

1r 2r

)()( 21 rLrL

30

Exemplo L= { todos os strings sem

dois 0s consecutivos }

)0(*)011(1 r

)0(*1)0(**)011*1(2 r

LrLrL )()( 211r 2r e

são expr. regularesequivalentes

31

Expressões Regulares e Linguagens Regulares

32

Teorema

LinguagensGeradas porExpr. Regulares

LinguagensRegulares

33

Teorema – Parte 1

LinguagensGeradas porExpr. Regulares

LinguagensRegulares

r)(rL

1. Para cada expressão regular a linguagem é regular

34

Teorema - Parte 2

LinguagensRegulares

Lr LrL )(

2. Para cada linguagem regular existe uma expressão regular com

LinguagensGeradas porExpr. Regulares

35

Prova - Parte 1

r)(rL

1. Para cada expressão regular a linguagem é regular

Prova por indução no comprimento der

36

Base da InduçãoExpressões Regulares Primitivas: ,,

NFAs

)()( 1 LML

)(}{)( 2 LML

)(}{)( 3 aLaML

linguagensregulares

37

Hipótese de Indução

Suponha para expressões regulares eque e são linguagens

regulares

1r 2r

)( 1rL )( 2rL

38

Passo InductivoVamos provar:

1

1

21

21

*

rL

rL

rrL

rrL

São linguagensregulares

39

Pela definição de expressões regulares :

11

11

2121

2121

**

rLrL

rLrL

rLrLrrL

rLrLrrL

40

)( 1rL )( 2rLPela hipótese de indução temos: e são linguagens regulares

Linguagens regulares são fechadas sob *1

21

21

rLrLrLrLrL união

concatenação

star

Também sabemos:

41

Portanto:

** 11

2121

2121

rLrL

rLrLrrL

rLrLrrL

São linguagensregulares

42

E trivialmente:

))(( 1rL é uma linguagem regular

43

Prova – Parte 2

Lr LrL )(

2. Para cada linguagem regular existe uma expressão regular com

Prova por construção da expressão regular

44

Como é regular, considere um NFA que a aceita

LM

LML )(

Estado final único

45

De construímos o equivalenteGrafo de Transição Generalizado

GNFA rótulos de transições

são expressões regulares

M

Exemplo:

a

ba,

cM

a

ba

c

46

Outro Exemplo:

ba a

b

b0q 1q 2q

ba,a

b

b0q 1q 2q

b

b

47

Reduzindo os estados:ba

ab

b0q 1q 2q

b

0q 2q

babb*

)(* babb

48

Expressão Regular resultante :

0q 2q

babb*

)(* babb

*)(**)*( bbabbabbr

LMLrL )()(

49

Em GeralRemovendo estados:

iq q jqa b

cde

iq jq

dae* bce*dce*

bae*

50

Obtendo a expressão regular final:

0q fq

1r

2r

3r4r

*)*(* 213421 rrrrrrr

LMLrL )()(