Politechnika Rzeszowska
Wydział Elektrotechniki i Informatyki
Katedra Informatyki i Automatyki
Języki, automaty i obliczenia
PROJEKT cz. I
Gramatyki i języki bezkontekstowe
Wykonała: Urbańska Anna
II EF-DI
Rzeszów 2012
Temat projektu:
Dla danej gramatyki bezkontekstowej wyprowadzić język przez nią generowany.
Dane:
Gramatyka G=<{S, A, B, a,b}, {a, b}, P, S > o następujących regułach produkcji:
1 2 3
S → aA | SA | bB
4 5 6
A → aB | a | b
7 8
B → Λ | bB
Wyprowadzenie języka generowanego przez powyższą gramatykę
2 *2 1 4,5,6 *8 7
S → SA → SAn → aAn+1 → a(aB+a+b)n+1 → a(abkB+a+b)n+1 → a(abk+a+b)n+1 = a(abk+b)n+1
n=0,1,… k=0,1,… n,k=0,1,…
3
4,5,6 *8 7
bBAn → bB(aB+a+b)n → bbmB(abkB+a+b)n → bbm(abk+a+b)n = bm+1(abk+b)n
m,k=0,1,... n,m,k=0,1,...
Odpowiedź
Język generowany przez podaną gramatykę:
L(G)= {a(abk+b)n+1 + bm+1(abk+b)n, n,m,k = 0, 1, 2, ...}
2