Wydział Elektrotechniki i Informatyki

Politechnika Rzeszowska

Katedra Informatyki i Automatyki

Języki, automaty, obliczenia

Projekt cz.1 (141)

Gramatyka i języki bezkontekstowe

Wykonał: Kacper Rapacz 2FD/L08

Rzeszów 2009

Temat projektu:

Dla danej gramatyki bezkontekstowej wyprowadzid język przez nią generowany.

Dane:

Gramatyka G=<{S,Y,X,Z,x,y},{x,y}, P, S> o następujących regułach produkcji P:

1 2 3
S->Yx|yZx|yxy
4 5
Y->yx|XZ
6 7
X->yy|xyX
8
Z->yXx

Wyprowadzenie języka generowanego przez powyższą gramatykę:

5

XZx

8

XyXxx

7

*

(xy)

n

Xy(xy)

m

Xxx

6

(xy)

n

yyy(xy)

m

Xxx

6

(xy)

n

yyy(xy)

m

yyxx

n,m= 0,1,2,3...

1

Yx

4

yxx

S

2

yZx

8

yyXxx

7

*

yy(xy)

k

Xxx

6

yy(xy)

k

yyxx

k= 0,1,2,3...

3

yxy

Odpowiedź:

Język generowany przez gramatykę:

L(G)={ (xy)

n

yyy(xy)

m

yyxx + yy(xy)

k

yyxx + yxy , n,m,k = 0,1,2,3...}