Question

Betrachten Sie die Grammatik G = (Σ,N,S,P) mit Σ = {a,b},N = {S,A,B} und
                                                 P = {S → aS ∣ bS ∣ b ∣ bA,

                                                        A → aB ∣ bB,
                                                        B → aB ∣ bB}.

Geben Sie zu der Grammatik G formal (nicht als Zustandsgraph) den NFA M an und

geben Sie die Sprache L(G) formal als Menge von Wörtern an, ohne weiteren Bezug auf G zu nehmen.

Answer 1

Ein NFA wird formal als 5-Tupel angegeben.
Also M = (Q, Σ, δ, q0, F)

Dabei steht Q für die Menge der Zustände, Σ für das Eingabealphabet, δ für die Zustandsübergangsfunktion, q0 für den Startzustand (wird auch als S bezeichnet) und F für die akzeptierenden oder auch finiten Zustände.

Aus der Grammatik G, kannst du nun den entsprechenden Automaten herleiten. Zur Hilfe kannst du dir den NFA auch erstmal aufzeichnen, um aus diesem dann den 5-Tupel herzuleiten.

Dann musst du noch die Sprache L(G) angeben und darfst dich dabei nur auf M, also deinen zuvor erstellten Automaten, beziehen. Eine Sprache zu definieren, ist dabei ein bisschen knifflig, aber nicht unmöglich.

L(G) = { [...] | y ∈ {a; b} }

So müsste das aufgebaut werden, wobei ich dir erstmal nicht die Lösung gebe.

Ich hoffe, dass ich dir einigermaßen helfen konnte, wenn das überhaupt deine Fragen waren, die ich dir beantwortet habe. 
Wenn du einen Lösungsansatz hast, dann kannst du ihn hier gerne reinschicken und ich guck mal drüber!
(Wollte dir nur nicht die komplette Aufgabe lösen, weil der Lerneffekt sonst fehlen würde. Aber ich glaube, dass du das trotzdem hinbekommst!)

LG
Nero