Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-2-2

Beantwortet: Nicht alle Wörter der Sprache L5 werden erzeugt

Thu, 03 Jan 2019 11:04:25 +0000

Hallo ugmwm,

du meinst die Aufgabe 3c auf dem 2. Tutoriumsblatt, wenn ich es richtig sehe.
Du hast recht, das Wort "0001" gehört zu der Sprache, dies kann aber von dem reguläre Ausdruck ((0+1)(0+1))* erzeugt werden. Allgemein: Bei (0+1) kannst du frei wählen, ob 1 oder 0 genommen werden soll (ein ausschließendes oder, als beide gehen nicht). Du kannst also in der ersten Klammer wählen und in der zweite genauso und musst nichts vertauschen. Diesen Vorgang kannst du durch den Stern beliebig oft wiederholen. Aber jedes mal kommen genau zwei weitere Zeichen zu deinem Wort, also eine gerade Anzahl. Dies ist genau die Sprache L5.
(Konkret: Beim ersten mal durchlaufen wählst du in beiden Klammern die 0, dann wiederholst du den Vorgang aufgrund des * und wählst dann 0 und 1 >> 0001)

Aber du hast Recht, generell darf die Zeichen wegen des Sternes nicht vertauschen, da nur ein Vorgehen wiederholt wird und das restliche Wort davor unverändert bleibt.

Ich hoffe es ist nun klar, liebe Grüße

Anne (Tutor)

Beantwortet: Frage zu Skript:

Wed, 10 Jan 2018 16:13:26 +0000

Hallo,

deine Lösung ist leider nicht richtig. Wir betrachten w=00011. Dann sehen wir, dass wir dieses Wort aus deiner Sprache erzeugen können, indem wir aus der ersten Klammer 00 wählen und aus dem zweiten Block 01*. Die eins können wir aufgrund des Sternes verdoppeln. Somit erhalten wir w aus deiner Sprache. Allerdings liegt dieses Wort nicht in der XWizard- Sprache. Dort können wir immer nur eine eins einfügen und dann muss erst wieder eine Null kommen, bevor die nächste kommen kann. Deshalb können diese beiden Ausdrücke bereits nicht äquivalent sein.

Bei regulären Ausdrücken kann man leider nicht einfach den Stern "in die Klammer reinziehen". Was du allerdings machen kannst ist innerhalb der großen Klammer ausmultiplizieren, folgender Ausdruck wäre somit richtig:

(00+1)x(0(0+00+1))* = (00+1)x(00+000+01)*

Viele Grüße,

Julia (Tutorin)

Beantwortet: Benötigt man die 0* vor den 3 Klammern oder könnte man diese auch einfach weglassen?

Thu, 28 Dec 2017 16:35:16 +0000

Hallo,
du brauchst eine 0 am Anfang, um z.B. das Wort 010101 darzustellen. Ohne diese 0 kann man keine Wörter mit 3 1en und einer führenden 0 darstellen, die ja ebenfalls Teil der Sprache sind.
Liebe Grüße (Tutor)

Beantwortet: und wie schaut es mit

Sun, 15 Jan 2017 08:43:00 +0000

Ja, dein regulärer Ausdruck ist auch richtig.

Viele Grüße,

Julia (Tutorin)

Beantwortet: Verständnisfrage zu Teilaufgabe c)

Sun, 07 Feb 2016 06:31:42 +0000

Hallo,

ausführlich ab hier oder kurz im letzten Absatz:

Der reguläre Ausdruck ist ja ((0+1)(0+1))*.

Das Ganze hat drei entscheidende Bestandteile:

1) Die Iteration (*) außen, die die beliebige Wiederholung des Klammerinhalts erlaubt. Dadurch ist zunächst mal eine beliebige Wortlänge möglich.

2) Die zwei inneren Klammern mit jeweils 0 ODER 1 zur Auswahl. Sie erlauben also immer die Wahl irgendeines Zeichens und legen keine bestimmte Zeichenfolge fest.

3) Die Verbindung dieser zwei inneren Klammern mit UND, wodurch bei einem Durchlauf der äußeren Klammer automatisch 2 neue Zeichen geschaffen werden. Damit wird die gerade Anzahl an Zeichen im Wort eingehalten.

Also ließe sich beispielsweise dein Wort 0001 bilden, indem man die äußere Klammer zunächst einmal durchläuft und dabei in beiden inneren Klammer die 0 aus dem ODER-Ausdruck wählt. Bei einem weiteren Durchlauf der äußeren Klammer würde man dann in der ersten die 0 wählen, in der zweiten die 1.

Viele Grüße

Max (Tutor)

Beantwortet: Alternativer regulärer Ausdruck

Fri, 05 Feb 2016 15:08:19 +0000

Hallo,

leider ist die Lösung nicht richtig da du kein Wort darstellen kannst was mit einer 0 anfängt ;)

Viele Grüße,

Marc (Tutor)

Beantwortet: Ginge auch (0+1)(0+1)(0*+1) ?

Thu, 04 Feb 2016 13:32:30 +0000

Hallo uwduw,

die Bedingung ist, dass max. 3 Einsen im Wort vorkommen. Das bedeutet aber, dass die 0en egal wie verteilt sein dürfen. Bei dem oben angegeben regulären Ausdruck ist es z.b. nicht möglich nach der letzten 1 ein/mehrere Nullen zu haben. Genauso kann bei obigem regulären Ausdruck zwischen 3 Einsen keine Null sein. Damit ist der reguläre Ausdruck nicht korrekt.
Halte dich am besten an die vorgestellten Vorgehensweisen.
Viel Erfolg,
Marvin (Tutor)

Wie sieht es mit 0101010 aus ?

Tue, 02 Feb 2016 15:21:42 +0000

Wenn ich den * richtig interpretiere, also dass das entsprechende Zeichen entweder keinmal oder beliebig oft verwendet wird, dann müsste doch auch diese Variante funktionieren?

Beantwortet: Alternativlösung

Tue, 02 Feb 2016 11:44:48 +0000

Hallo,

auf welche Teilaufgabe bezieht sich deine Frage denn?

Zu deiner 2. Frage betreffend interpretation von * stimmt das genau. Wenn bspw. ein 1* da steht kann die 1 auch kein mal vorkommen.

Viele Grüße,

Marc (Tutor)

Beantwortet: Ginge auch: $0^\star(0^\star+1)(0^\star+1)(0^\star+1)$?

Tue, 08 Dec 2015 07:25:56 +0000

Deine Lösung funktioniert leider nicht. Die einzige Restriktion der Sprache ist, dass maximal 3 1er in den Wörtern enthalten sein dürfen; vor und hinter den 1en können beliebig viele 0er stehen.

Bei deinem Ausdruck kann man zwischen den 1ern keine 0 erzeugen, da entweder beliebig viele 0er oder eine 1 erzeugt wird. Damit dies funktioniert braucht man die 0* hinter der 1. Damit kannst du in jedem Klammerausdruck entscheiden, ob du nur 0er oder eine 1 und beliebig viele 0er erzeugst.

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Mon, 21 Sep 2015 07:50:22 +0000

Hallo,

könnte man den in der Musterlösung zur Teilaufgabe b) angegebenen regulären Ausdruck 0*(0*+10*)(0*+10*)(0*+10*) eigentlich auch vereinfacht in folgender Form schreiben?

0*(0*+10*)^3

Gruß

Beantwortet: Allgemein: immer erst Automaten zeichnen, dann Grammatik ableiten?

Mon, 21 Sep 2015 07:49:33 +0000

Hallo,

das kann man machen (und übt dabei auch schön die endlichen Automaten), aber mit ein bisschen Übung kann man den regulären Ausdruck auch direkt angeben.

Z.B. beim b)-Teil muss man überlegen, wie ein Wort aussieht, dass maximal drei Einsen enthält: Da kommt zuerst eine beliebige Anzahl von Nullen, dann (eventuell) eine Eins, dann wieder Nullen, dann wieder (eventuell) eine Eins, dann nochmal Nullen, noch eine (eventuelle) Eins und am Ende nochmal beliebig viele Nullen. Wie könnte man das als regulärer Ausdruck formulieren? Die Schwierigkeit ist hier vor allem, die "optionalen Einsen" darzustellen; "genau drei Einsen" wäre einfach, bei "höchstens drei" muss man ein bisschen tricksen. Wenn Sie nicht darauf kommen, schauen Sie sich die Lösung an.

Um Ihre Frage zu beantworten: in der Klausur sollten Sie bei einer solchen Aufgabe den Ausdruck direkt aufstellen, da der Umweg über einen endlichen Automaten zuviel Zeit kosten würde.

Viele Grüße

Lukas König

PS. Ich habe mal den zugehörigen endlichen Automaten aufgestellt (siehe Anhang). Daraus einen regulären Ausdruck abzuleiten scheint mir gar nicht so leicht... Diese Prozedur ist nämlich nicht immer einfach. Es gibt dafür zwar einen Algorithmus, aber der ist nichttrivial, und wir behandeln ihn in der Vorlesung nicht.

Beantwortet: Funktionsweise von * hinter den Klammern?

Mon, 21 Sep 2015 07:40:01 +0000

Hallo,

nein, wenn hinter einer Klammer kein * kommt, dann wird sie genau einmal durchlaufen, nicht mehr und nicht weniger.

Viele Grüße

Philippe (Tutor)

Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-2-2

Beantwortet: Nicht alle Wörter der Sprache L5 werden erzeugt

Beantwortet: Frage zu Skript:

Beantwortet: Benötigt man die 0* vor den 3 Klammern oder könnte man diese auch einfach weglassen?

Beantwortet: und wie schaut es mit

Beantwortet: Verständnisfrage zu Teilaufgabe c)

Beantwortet: Alternativer regulärer Ausdruck

Beantwortet: Ginge auch (0*+1)(0*+1)(0*+1) ?

Wie sieht es mit 0*10*10*10* aus ?

Beantwortet: Alternativlösung

Beantwortet: Ginge auch: $0^\star(0^\star+1)(0^\star+1)(0^\star+1)$?

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Beantwortet: Allgemein: immer erst Automaten zeichnen, dann Grammatik ableiten?

Beantwortet: Funktionsweise von * hinter den Klammern?

Beantwortet: Ginge auch (0+1)(0+1)(0*+1) ?

Wie sieht es mit 0101010 aus ?