W

ykªad

8.

Minimaliza ja

determinist y zn

y

h

automató w

sk

o« zon

y

h

Zminimalizuj nastpuj¡ e

determinist y zne

automat y

sk

o« zone:

1.

(4

p.)

a b

→ 1

4

3

2

1

4

F 3 1 1

F 4 1 1

Stan

2

nie

jest

osi¡

galn

y

,

wi

mo»em

y

go

usun¡¢.

W

wyniku zastoso w

ania

algorytm u

minimaliza ji

otrzym ujem

y

p

ok

azan¡

p

oni»ej tabli ,

o

ozna za,

»e

mo»na

ze

sob¡

sklei¢

stan

y

3

i

4:

1

a

b

F 3

→ 1

3, 4 3, 4

T F 4

F 3, 4

1

1

2.

(6

p.)

a b

→ F 1

2

4

2

5

1

3

6

5

4

1

6

5

1

2

6

4

1

Stan

3

nie

jest

osi¡

galn

y

,

wi

mo»em

y

go

usun¡¢.

W

wyniku zastoso w

ania

algorytm u

minimaliza ji

otrzym ujem

y

p

ok

azan¡

p

oni»ej tabli ,

o

ozna za,

»e

mo»na

ze

sob¡

sklei¢

stan

y

2

i

6,

oraz

4

i

5:

1

a

b

F 2

→ F 1

2, 6 4, 5

F F 4

2, 6 4, 5

1

F F T 5

4, 5

1

2, 6

F T F F 6

11