PRACA DOMOWA 6 - AUG

Równoważność wzorców, wyrażeń regularnych i automatów

skończonych

Zadanie 1: (3p.) Dopasuj do siebie automaty i wyrażenia regularne:

Zadanie 2: (4p.) Podaj automat skończony (dowolnego rodzaju) akceptujący język opisany wzorcem:

b(aba)+b* | (aa)*(ab)+

Zadanie 3: (3p.) Podaj wyrażenie regularne opisujące język akceptowany przez następujący automat
niedeterministyczny:

  = (  |

ε

(a|aa*b)(ε)*(b|aa|ba))*

     = ((a | aa*b) ( b | aa | ba))*

ε

a

b

a

ε

b

ε

ε

a

a

b

a

ε

b

ε

1

2

3

4

a

b

b

a

a

a

a

a,b

1

4

2

3