Chomsky-Hierarchie Sprache und Einordnung

Question

Hallo, eine Sprache L enthält alle Binärzahlen (auch mit führenden Nullen), welche durch 2, aber nicht durch 4 teilbar sind.

Wir sollen zunächst die Sprache als Menge von Wörtern angeben (allerdings ohne reguläre Ausdrücke) und die Sprache möglichst genau in die Chomsky-Hierarchie einordnen.

Normalerweise hätte ich für die erste Teilaufgabe sowas wie L={w∈{0,1}*I w ist durch 2, aber nicht durch 4 teilbar}, geschieben.

Allerdings sollen wir ja keine regulären Ausrücke verwenden. Über Hilfe wäre ich sehr dankbar. : )

Comments

Wir sollen zunächst die Sprache als Menge von Wörtern angeben (allerdings ohne reguläre Ausdrücke)

L={w∈{0,1}*I w ist durch 2, aber nicht durch 4 teilbar}

Wo ist das ein regulärer Ausdruck? Das ist bislang jedoch noch sehr unsauber formuliert, da Du nirgends erwähnst, dass \(\{0,1\}*\) als Binärzahl zu interpretieren ist. Außerdem gibt es nicht umsonst \(\mod, \mid\) und Junktoren.

möglichst genau in die Chomsky-Hierarchie einordnen.

Weißt Du, was das heißt? Mit der Einschränkung hat euer Prof die Einordnung fast schon verraten (müsste ich mir aber noch näher anschauen).

---

Hallo,

bei uns im Skript ist * ein regulärer Ausdruck, deshalb war ich etwas irritiert, wie man das darstellen soll. Würde das so gehen?

L = { w∈{0,1}* I w mod 2 = 0 ∧ w mod 4 ≠ 0}

Bei der Einordnung würde ich sagen es ist kontextfrei, also Typ 2.

Answer 1

Binärzahlen die durch 2, aber nicht durch 4 teilbar sind, enden ja zwangsläufig mit  „10”. Als Menge von Wörtern, ohne reguläre Ausdrücke, würde diese Sprache so aussehen:

\({L}_{1}\) = { w | w∈{0,1}*, 10\({ \sqsubseteq  }_{ e }\)w }.

Das man keine regulären Ausdrücke verwenden soll, klingt tatsächlich wie ein Hinweis ;). Sie ist in der Tat regulär. Dass kann man leicht nachweisen, bzw. sich leicht vorstellen, in dem man ein PDA macht. Egal was man eingibt, um ins Endzustand zu gelangen, muss eine 1 und danach eine 0 eingegeben werden. Sei  \({z}_{e}\) der Endzustand:

	\({z}_{0}\)	\({z}_{1}\)	\({z}_{e}\)
0	\({z}_{0}\)	\({z}_{e}\)	\({z}_{0}\)
1	\({z}_{1}\)	\({z}_{1}\)	\({z}_{1}\)

Answer 2

Eine durch \(2\) aber nicht durch \(4\) teilbare Zahl kann durch \(4\cdot k-2\) mit \(k\in\mathbb{N}\) dargestellt werden.

Beispiele wären: \(2, 6, 10, 14, 18, 22, 26,30, 34...\)

Diese Zahlen kannst Du dir im Binärsystem ansehen:

\(2_{(10)}=10_{(2)}\)

\(6_{(10)}=110_{(2)}\)

\(10_{(10)}=1010_{(2)}\)

\(14_{(10)}=1110_{(2)}\)

\(18_{(10)}=10010_{(2)}\)

\(22_{(10)}=10110_{(2)}\)

\(26_{(10)}=11010_{(2)}\)

\(30_{(10)}=11110_{(2)}\)

\(34_{(10)}=100010_{(2)}\)

Spätestens hier müsstest Du bereits ein Bildungsgesetz für die Binärwörter erkennen können (Tipp: Schau Dir an, was mit jeder weiteren neu hinzukommenden \(1\) mit den anderen Stellen passiert und worauf die Wörter allesamt enden). Dann müsstest Du schnell beantworten können, ob Du dieses Bildungsgesetz überhaupt durch einen regulären Ausdruck einfangen kannst.

L = { w∈{0,1}* I w mod 2 = 0 ∧ w mod 4 ≠ 0}

Das klingt schon besser, aber nicht optimal. Es fehlt nach wie vor die Information, dass \(w\) als Binärzahl zu interpretieren ist (für meinen Geschmack reicht das aber so aus).

Allerdings sollen wir ja keine regulären Ausrücke verwenden.

Wie bereits geschrieben: Prüfe, ob das überhaupt geht (Tipp: Ja, das geht).

Wir sollen zunächst die Sprache als Menge von Wörtern angeben

Alle wirst Du wohl nicht aufzählen müssen, oder (wie auch, bei abzählbar unendlich vielen Wörter)?

Bei der Einordnung würde ich sagen es ist kontextfrei, also Typ 2.

Findest Du mit dem jetzigen Wissen eine kontextfreie Grammatik zum Erzeugen der Binärstrings? Oder vielleicht sogar eine reguläre? Male Dir mal einen DFA oder NFA auf (damit ist die Katze wohl aus dem Sack ;)). Wenn Du diesen angibst, hast Du den Beweis für Deine (hoffentlich revidierte) Behauptung quasi erbracht. Du hast mit der Aussage "Diese Sprache ist kontextfrei" natürlich nicht unrecht, doch "möglichst genau" ist das nicht :)

Warum Du keinen regulären Ausdruck verwenden sollst, ist mir ehrlich gesagt schleierhaft ...