Automat

y

i

gramat

yki



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

KOLOKWIUM

(przykªad)

Imi¦

i

nazwisk

o:

Nr

indeksu:

Nr

grup

y:

Zadanie

1



4

pkt.

P

o

da

j

wyra»enie

regularne

opisuj¡ce

p

oni»szy

j¦zyk

L

:

1.

L

=

w ∈ {a, b}

∗

: w

nie

za

wiera

p

o

dsªo

w

a

bb

,

2.

L

=

w ∈ {a, b}

∗

: w

za

wiera

p

o

dsªo

w

o

baa

lub

aab

.

Zadanie

2



4

pkt.

P

o

da

j

automat

determinist

yczn

y

lub

niedeterminist

yczn

y

ak

ceptuj¡cy

p

oni»szy

j¦zyk

L

:

L

=

w ∈ {a, b}

∗

: w

nie

za

wiera

p

o

dsªo

w

a

baab

i

abba

 .

1

P

a

w

eª

Remb

elski

Automat

y

i

gramat

yki



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

Zadanie

3



4

pkt.

Zdeterminizuj

p

oni»szy

automat

niedeterminist

yczn

y

.

2

P

a

w

eª

Remb

elski

Automat

y

i

gramat

yki



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

Zadanie

4



6

pkt.

Zredukuj

p

oni»szy

automat

sk

o«czon

y

do

automatu

dwustano

w

ego,

którego

kra

w

¦dzie

s¡

et

ykieto

w

ane

wyra»eniami

regularn

ymi.

K

orzysta

j¡c

z

rezultatu

reduk

cji,

p

o

da

j

wyra»enie

regularne

ró

wno

w

a»ne

roz-

w

a»anem

u

automato

wi

sk

o«czonem

u.

3

P

a

w

eª

Remb

elski

Automat

y

i

gramat

yki



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

Zadanie

5



6

pkt.

P

o

da

j

gramat

yk

¦

b

ezk

on

teksto

w

¡

opisuj¡c¡

p

oni»szy

j¦zyk

L

:

L

=

w ∈ {a, b, c}

∗

: #

c

(w) > #

b

(w)

 .

Narysuj

drzew

o

wypro

w

adzenia

sªo

w

a

w

= acbccba

w

otrzymanej

gramat

yce.

Czy

otrzymana

gramat

yk

a

jest

jednoznaczna

-

o

dp

o

wied¹

uzasadnij?

4

P

a

w

eª

Remb

elski

Automat

y

i

gramat

yki



materiaªy

¢wiczenio

w

e

Studia

dzienne

PJWSTK

Zadanie

6



8

pkt.

P

o

da

j

automat

stoso

wy

ak

ceptuj¡cy

p

oni»szy

j¦zyk

L

:

L

=

w ∈ {a, b}

∗

: w = b

i

a

j

b

k

dla

i

+ k = j

 .

5

P

a

w

eª

Remb

elski