Teil 1

Man erhält für die drei Wörter nach dem CYK-Algorithmus die folgenden Tabellen:

´{A,C}´	´{S,C}´	´O/ ´	´O/ ´	´O/ ´
´a´	´{B}´	´O/ ´	´O/ ´	´{A}´
	´b´	´{B}´	´O/ ´	´{A}´
		´b´	´{B}´	´{S, A}´
			´b´	´{A,C}´
				´a´

´{B}´	´{S, A}´	´O/ ´	´O/ ´	´{S, A, C}´
´b´	´{A,C}´	´{B}´	´{B}´	´{S, A, C}´
	´a´	´{A,C}´	´{S,C}´	´{B}´
		´a´	´{B}´	´{S, A}´
			´b´	´{A,C}´
				´a´

´{B}´	´O/ ´	´O/ ´	´{A}´	´O/ ´	´{S, A, C}´
´b´	´{B}´	´O/ ´	´{A}´	´O/ ´	´{S, A, C}´
	´b´	´{B}´	´{S, A}´	´O/ ´	´{S, A, C}´
		´b´	´{A,C}´	´{B}´	´{S, A, C}´
			´a´	´{A,C}´	´{B}´
				´a´	´{A,C}´
					´a´

Damit ist ´w_1 !in L(G)´, aber ´w_2, w_3 in L(G)´.

Teil 2

Da die gegebene Grammatik in Chomsky-Normalform ist und es zu jedem Nichtterminal ´X´ aus ´{A,B,C}´ ein ableitbares Wort gibt, in dem ´X´ vorkommt, und zu jedem ´X´ eine terminierende Ableitung existiert, haben wir nur zu sehen, ob es in dem Graphen

S -> A S -> B S -> C A -> A A -> B C -> A C -> B B -> C

einen Kreis gibt. Dies ist sofort zu sehen und folglich ist L(G) unendlich.

Lösung ohne diesen Algorithmus: Es gibt für jedes ´n >= 1´ die Ableitung

´S => AB => BAB => BBAB => … => B^nAB =>^(**) b^nab´.

Damit enthält ´L(G)´ die unendliche Menge ´{b^nab | n >= 1}´, womit ´L(G)´ unendlich ist.