W

ykªad

5.

Niedeterminist

y zne

automat

y

sk

o« zone

1.

(2

p.)

P

o

da

j

automat

niedeterminist

y zn

y

ak

eptuj¡ y

sªo

w

a

nad

alfab

etem

{a, b}

za

wiera

j¡ e

p

o

dsªo

w

o

ababb

.

a,b

b

a

b

b

a

a,b

2.

(5

p.)

Zdeterminizuj

nastpuj¡ y

automat

niedeterminist

y zn

y:

a

s

p

q

a

b

a

a

b

b

Oto

o

dp

o

wiedni

automat

p

otgo

wy

(ograni zon

y

do

stanó

w

osi¡

galn

y

h):

a,b

a

b

b

b

a

{s}

{q}

{s,p}

{s,p,q}

3.

(3

p.)

W

y

elimin

uj

ε

-przej± ia

w

p

oni»szym

automa ie.

Jaki

jzyk

on

ak

eptuje?

ε

b,

ε

b,

ε

b,

ε

b,

a

a

Oto

jedno

z

mo»liwy

h

rozwi¡za«.

Nie

jest

ono

na

jprostsze,

ale

jest

wynikiem

zasto-

so

w

ania

k

onstruk

ji

przedsta

wionej

na

wykªadzie.

Jzyk

ak

epto

w

an

y

przez

automat,

to

a

∗

b

?b?b?a

∗

.

a

a,b

b

b

a,b

a,b

a

b

7