Wann benötige ich Lambda?

Question

Sehr geehrte Frau Pfeiffer,

vielen Dank für Ihre ausführliche Erklärung. Trotzdem wird mir auch nach längerer Zeit einfach nicht klar, WANN ich ein Lambda benötige, wann es zwingend notwendig ist und wann es verboten ist.

Vielen Dank im Vorraus!

 

Answer 1

Diese Frage ist nicht einfach zu beantworten. Es gibt einige klare Richtlinien:

•     Das Startsymbol muss auf lambda führen, wenn lambda Element der zu erzeugenden Sprache ist.
•     Lambda darf nicht in einer kontextsensitiven oder monotonen Grammatik auftauchen, außer unter folgenden Umständen:
  •  Die Linke Seite der Regel, in der lambda auftaucht, besteht ausschließlich aus dem Startsymbol und
  •  Das Startsymbol taucht auf keiner rechten Seite einer Regel auf.
•     Lambda darf nicht in Grammatiken in Chomsky-Normalform oder Greibach-Normalform auftauchen, außer unter denselben Umständen wie oben.

Ansonsten gibt es jedoch keine Regeln für die Anwendung von lambda. Sie dürfen das leere Wort einfach benutzen, wenn Sie es für notwendig halten. Eine Frage wie "wann benutzt man das leere Wort in einer Grammatik?" ist ein bisschen als würde man fragen: "Wann benutze ich ein if-Statement in Java?" (Da Grammatiken äquivalent sind zu Turingmaschinen, die (nach der Churchschen These) äquivalent sind zu Programmiersprachen.) Man kann das nicht allgemein beantworten, sondern muss ein Gefühl dafür entwickeln. Sie werden aber sehen, dass sich die Schemata in unseren Aufgaben immer wiederholen, sodass es irgendwann schnell einleuchtet, wann man lambda braucht.

Oft sind es Situationen, wo man eine gerade Anzahl von Zeichen erzeugen möchte, in denen man lambda benötigt, bspw. für die Sprache ${anbn | n∈N}$:

$S→aSb|λ$

Während man bei einer ungeraden Zeichenanzahl statt lambda ein Terminalzeichen nehmen würde; vgl. bspw. für die Sprache ${w∈{a,b} | w=w′}$, wo beides vorkommt:

$S→aSa|bSb|a|b|λ$

Das gilt aber nur für kontextfreie Grammatiken (wo man übrigens theoretisch durch Nutzung der Normalformen auch komplett auf lambda verzichten könnte, genauso wie bei den kontextsensitiven Grammatiken).

Viele Grüße

Lukas König