Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009
Teoretyczne Podstawy Informatyki  zadania, zestaw 3
Gramatyki bezkontekstowe
1. Zdefiniować gramatykę bezkontekstową generującą wyrażenia postaci:
a) L(G)={an bm ck ; n, m, k " N}
b) L(G)={an bm cn ; n, m " N}
c) L(G)={an bn+3; n " N}
d) L(G)={an bm c dm en ; n, m " N}
e) L(G)={S i ; S = 11 0n 1m 2 2, i, n, m " N}
f) ciąg symboli a, po którym jest ciąg symboli b, po którym jest ciąg symboli c. Ilość
symboli a i c jest parzysta, a ilość symboli b nieparzysta (a2n b2m-1 c2k; n, m, k " N)
g) ciąg symboli a, b, c tworzący palindrom (wyraz czytany od początku i od końca jest
taki sam)
h) ciąg w którym na pozycjach nieparzystych jest symbol x lub y, a na pozycjach
parzystych symbol y lub z
i) ciąg symboli x, y, z, w którym na trzeciej pozycji znajduje się ten sam symbol co na
pozycjach przedostatniej i trzeciej od końca
j) ciąg symboli a po którym jest ciąg symboli b. Ilość symboli a i b nie może być taka
sama
k) L(G)={0n 2 0m 1k ; n + m e" 1, k e" 1}
l) L(G)={0n 2 0m 1k ; n + m = k  1, k e" 2}
m) L(G)={0n a 0m 1k b 1l ; n + m = k + l e" 1}
n) L(G)={an bm ck ; n = m lub m = k}
o) L(G)={an bm ck ; n `" m lub m `" k}
p) L(G)={an bm c3(n+m) ; n, m " N }
q) L(G)={0n 1m 2k ; n = 2m lub m = 2k}
r) L(G)={0n 1m ; n d" m d" 2n}
2. Zdefiniować gramatyki bezkontekstowe realizujące języki podane w 3 zadaniu z
peirwszego zestawu zadań
3. Dana jest gramatyka:
G = ({W, S, C}, {a, b, c, d, +,  , *, ( , )}, P, W)
P: W W + S | W  S | S
S S * C | C
C (W) | a | b | c | d
Które ze słów ( a+b*c)*(d+a)*c) czy (((a+b*c)*d a))*a+b jest słowem poprawnym
języka L(G)? Dla słowa poprawnego narysować drzewo rozbioru.
4. Dana jest gramatyka:
G=({W, S}, {a, b, c, +, *, ( , ), ^}, P, W)
P: W W + W | W *W | W ^ W | S
S (W) | a | b | c
Czy słowo (a+b)+c*b^a jest słowem poprawnym języka L(G)? Jeżeli tak, narysować jego
drzewo rozbioru. Czy istnieje tylko jedno takie drzewo? Jeżeli nie to narysować wszystkie
możliwe drzewa rozbioru. Czy jest to gramatyka jednoznaczna, czy wieloznaczna?
Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009
5. Dla podanych dwóch gramatyk podać która z nich jest jednoznaczna, a która
wieloznaczna. Dla gramatyki wieloznacznej podać przykładowe słowo i narysować dla
niego dwa różne drzewa wyprowadzenia.
G=({S}, {a, b}, P, S) G=({S,A,B}, {a, b}, P, S)
P: S aS | aSbS | � P: S AbB
A aA | �
B aB | bB | �
6. Jakie języki realizują poniższe gramatyki bezkontekstowe. Podać opis słowny.
a) G=({S}, {(, )}, P, S)
P: S SS | (S) | �
b) G=({A, B, C}, {a, b}, P, C)
P: C AB | CAB
A aAbb | abb
B aBbbb | abbb
7. Zdefiniować gramatykę:
a) generującą liczby całkowite. Liczba całkowita składa się z niepustego ciągu cyfr i
może zawierać znak. Podać także postać gramatyki w której liczby nie mogą posiadać
zbędnych zer na początku.
b) generującą liczby rzeczywiste o postaci określonej poniższymi przykładami
175,33 323 0,156  ,01  1004 0,0 85478,141581 +0001230,500
c) generującą liczby rzeczywiste o postaci wykładniczej określonej poniższymi
przykładami
7531,33e10 0,7601e 3 ,162e0  0073e5  1004,0e 02  0,0e106 00320,5001e55
1e3 214e4
d) generującą liczby zespolone o postaci określonej poniższymi przykładami
12+5i +0,017-i 1+7005*i 3,14+2,56j 22,007 11,450i 0,0-0012i 9,55 -6 i
8. Podać gramatyki bezkontekstowe realizujące języki opisane wyrażeniami regularnymi
a) a (a | b*c) a
b) (0 | 1 | 2)* 3* 0
c) (a* | b*)(cb | ca)*c+
9. Przekształcić podane gramatyki do postaci normalnej Chomsky ego
a) G=({A, B, C}, {a, b, c}, P, A)
P: A aAb | aBACa
B C | ac | ca
C abAB | abab
b) G=({S, A, B, C, D, E}, {a, b, c}, P, S)
P: S aAa | bBb
A C | a
B c | b
C CDEC
D A | B | ab
E �
Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009
10. Zdefiniować gramatykę:
a) realizującą język nad alfabetem T={a, b, c} składający się ze wszystkich słów nie
będących palindromami
b) generującą wszystkie łańcuchy zrównoważonych nawiasów okrągłych i
kwadratowych; T={(, ), [, ]}
c) generującą wszystkie łańcuchy nad alfabetem T={a, b}, w których symboli a jest dwa
razy więcej niż symboli b
11. Zdefiniować gramatykę generującą instrukcje podstawienia o postaci określonej
poniższymi przykładami
A=B+C[I]+15 E[3]=  K C[11] X[30,J]=1 B6+Y[K,4]  0+G001[A]
A1=+1 Z+T[B12] T[J23,34]=R2347[10,11] A10[I1,I2]=B[I,J]+C[J,K]
12. Zdefiniować gramatykę generującą instrukcje warunkowe o postaci określonej
poniższymi przykładami
if (a<5,05) then suma:=5 if (cena>=b5) then a:=d if (bc27d=  15) then nx2d4:=34,52
if (0,015<>z2nxt) then delta:=  21,41415
Jak należałoby zmienić definicję gramatyki, aby niemożliwe było porównanie dwóch
liczb
13. Zdefiniować gramatykę generującą teksty zawierające niezagnieżdżone znaczniki
pogrubienia i pochylenia tekstu ( [B], [/B], [I], [/I] ). Przykład:
To [B] jest [/B] przykładowe [I] zdanie [/I]. To [B] jest [I] drugie [/B] przykładowe [/I]
zdanie. [I] To [/I] jest [B][I] trzecie przykładowe [/B] zdanie.
Jak należałoby zmienić definicję gramatyki, aby tekst zawsze kończył się tekstem
normalnym (tzn. aby były zakończone wszystkie otwarte znaczniki)
14. Zdefiniować gramatykę generującą wielomiany algebraiczne w zapisie Hornera. Dla
współczynników wielomianu może być stosowany zapis w notacji wykładniczej
zmiennoprzecinkowej. Przykłady:
( 3,69*x+0,1)*x+2 (((2*x 22,75)*x+5,112e3)*x+3,1e-6)*x 1723
15. Podać gramatykę definiującą pętlę for o składni takiej jak w języku C, ale z następującymi
ograniczeniami. Gramatyka powinna definiować tylko pętlę for wraz z wyrażeniami
podawanymi w nawiasach (czyli bez instrukcji występującej po zamknięciu nawiasu).
Pierwsze wyrażenie w nawiasie składa się z oddzielonych przecinkami kolejnych
instrukcji podstawienia do zmiennych wartości całkowitych. Drugie wyrażenie jest
warunkiem logicznym. Trzecie wyrażenie tak jak pierwsze składa się z oddzielonych
przecinkami kolejnych instrukcji podstawienia lub instrukcji inkrementacji albo
dekrementacji (+ +,   ).
16. Podać gramatykę definiującą instrukcję switch występującą w języku C. Zmienną
instrukcji switch oznaczyć jako  zm , wartości wymieniane po instrukcjach case jako
 wart , a instrukcje wykonywane na skutek rozpoznania wartości  wart jako  instr .
17. Zdefiniować gramatykę generującą poprawne formuły sumujące liczby w arkuszu
kalkulacyjnym. Przykładowe formuły:
=K34 =A1+B5 =DG1234 $A$11+PQ1 M64 =$V1 W$3
=  AX16 $AY17 Z$22+K64+M65+N66
Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009
18. Zdefiniować gramatykę generującą łańcuchy tekstowe przedstawiające poprawne
wyrażenia regularne (WR) nad alfabetem Ł={0, 1, 2, ..., 9}
19. Które z poniżych języków są językami bezkontekstowymi, a które regularnymi?
a) L(G)={an bn; n " N}
b) L(G)={an bn; n " N, n d" 104}
c) ciąg symboli a, b tworzący palindrom nie krótszy niż 256 symboli
d) ciąg symboli a, b tworzący palindrom nie dłuższy niż 256 symboli
e) ciąg symboli a, b tworzący palindrom o dowolnej długości