W

ykªad

9.

Jzyki

b

ezk

on

teksto

w

e

1.

(6

p.)

P

o

da

j

gramat

yk



b

ezk

on

teksto

w

¡

generuj¡ ¡

jzyk

{a

n

b

n+k

c

k

: n, k ≥ 1}

.

P

o

da

j

drzew

o

wypro

w

adzenia

dla

sªo

w

a

aabbbbbccc

.

Zau

w

a»m

y

,

»e

a

n

b

n+k

c

k

= a

n

b

n

b

k

c

k

.

Mo»em

y

wi

niezale»nie

opisa¢

jzyki

zªo»one

ze

sªó

w

p

osta i

a

n

b

n

i

b

k

c

k

,

a

nastpnie

sklei¢

je:

S

→ XY

X

→ aXb | ab

Y

→ bY c | bc

Oto

drzew

o

wypro

w

adzenia

sªo

w

a

aabbbbbccc

:

S

oo

oo

oo

oo

oo

oo

oo

N

N

N

N

N

N

N

N

N

N

N

N

N

N

X









?

?

?

?

?

?

?

?

Y

>

>

>

>

>

>

>

>

a

X









?

?

?

?

?

?

?

?

b

b

Y

>

>

>

>

>

>

>

>

c

a

b

b

Y

>

>

>

>

>

>

>

>

c

b

c

2.

(4

p.)

P

o

da

j

linio

w

¡

gramat

yk



generuj¡ a

jzyk

ab

(b

∗

| a

∗

)

.

T

o

zadanie

mo»na

rozwi¡za¢

na

wiele

sp

osob

ó

w,

zwªasz za

je»eli

nie

wymagam

y

ab

y

gramat

yk

a

b

yªa

silnie

linio

w

a.

Oto

jedno

z

mo»liwy

h

rozwi¡za«:

S

→ abX | abY

X

→ aX | ε

Y

→ bY | ε

A

oto

inne,

silnie

linio

w

e:

S

→ aR

R

→ bX

X

→ aY | bZ | ε

Y

→ aY | ε

Z

→ bZ | ε

12