Formale Sprachen: Konstruieren Sie ein Rezeptbuch mit genau drei verschiedenen Rezepten

Question

Angenommen, Sie wollen sich nach einem anstrengenden Tag in der Universität ein leckeres Abendessen zubereiten. In Ihrem Kühlschrank befinden sich die Zutaten Fleisch, Halloumi, Gemüse und Salat. Fleisch und Halloumi müssen jeweils zunächst entweder gegrillt oder gebraten werden. Gemüse und Salat müssen jeweils erst geschnitten werden, wobei Gemüse anschließend entweder noch gegrillt oder gebraten werden kann, aber keines von beidem muss. Zu einem Salat müssen Sie stets sofort nach dem Schneiden ein Dressing zubereiten. Zuletzt muss das gesamte Abendessen noch einmalig angerichtet werden. Daraus ergibt sich folgendes Alphabet:

Σ ={Fleisch,Halloumi,Gemüse,Salat,Grillen, Braten,Schneiden,DressingZubereiten,Anrichten}

Jedes Wort über dem Alphabet Σ entspricht einem Rezept.

Konstruieren Sie ein Rezeptbuch mit genau drei verschiedenen Rezepten, die jeweils aus genau zwei verschiedenen Zutaten bestehen und die oben beschriebenen Regeln einhalten, indem Sie eine Sprache über Σ mit genau drei Wörtern erstellen, welche diesen Rezepten entsprechen.

Comments

Vom Duplikat:

Titel: Konstruieren Sie ein Rezeptbuch mit genau drei verschiedenen Rezepten

Stichworte: wörter,länge

Σ ={Fleisch,Halloumi,Gemüse,Salat,Grillen,Braten,Schneiden,DressingZubereiten,Anrichten}

Jedes Wort über dem Alphabet Σ entspricht einem Rezept.

Konstruieren Sie ein Rezeptbuch mit genau drei verschiedenen Rezepten, die jeweils aus genau zwei verschiedenen Zutaten bestehen und die oben beschriebenen Regeln einhalten, indem Sie eine Sprache über Σ mit genau drei Wörtern erstellen, welche diesen Rezepten entsprechen.

Geben Sie für jedes Wort Ihrer erstellten Sprache die Länge an.

Wählen Sie eines Ihrer Rezepte aus und geben Sie für das Wort, welches diesem Rezept entspricht, das (eindeutig bestimmte) Anfangswort der Länge drei an.

Geben Sie für jedes Wort Ihrer erstellten Sprache genau die Teilwörter an, welche der fertigen Vorbereitung einer Zutat entsprechen.

Answer 1

Konstruieren Sie ein Rezeptbuch mit genau drei verschiedenen Rezepten

Das ist aber ein kleines Rezeptbuch. Viel spannender wäre es, eine Grammatik zu konstruieren, die ein Rezeptbuch mit allen möglichen Rezepten gemäß den obigen Bildungsregeln erzeugt. Drei mögliche Wörter in der Sprache sind:

FleischGrillenSalatSchneidenDressingZubereitenAnrichten

HalloumiBratenSalatSchneidenDressingZubereitenAnrichten

FleischBratenGemüseSchneidenGrillenAnrichten

Es ist also

\(L\subseteq\Sigma^*:= \) FleischGrillenSalatSchneidenDressingZubereitenAnrichten}, HalloumiBratenSalatSchneidenDressingZubereitenAnrichten, FleischBratenGemüseSchneidenGrillenAnrichten}