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...}