0 Daumen
1,2k Aufrufe

Sei G = (Σ, N, S, R) eine Grammatik mit Σ = {a, b, c}, N = {S, A, B} und R = {S → ABSc | ABc, BA → AB, Bc → bc, Bb → bb, Ab → ab, Aa → aa}.

Zeigen Sie, dass diese Grammatik die Sprache L = {anbncn| n ≥ 1} erzeugt. (Zeigen Sie also L ⊆ L(G) und L(G) ⊆ L.)

 

Also ich weiß, dass es gezeigt werden muss, dass alle in G erzeugten Wörter in L liegen und umgekehrt. Beide Male genügt ein Induktionsbeweis über die Anzahl der Ableitungsschritte. Nur hänge ich eben bei diesem Beweis. 

Vielleicht kann mir jemand weiterhelfen? 

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community