Pumping Lemma - Reguläre Sprache

16.04.2015, 12:46	Auf diesen Beitrag antworten »
Piep000r	Pumping Lemma - Reguläre Sprache Meine Frage: Hallo. Ich befasse mich damit herauszufinden, ob die folgende Sprache regulär ist, oder nicht: $[latex]<br /> L = \{w \in (0,1)^{\ast} \| (\|w\|_0 = \|w\|_1)\}<br /> [/latex]$ Allerdings habe ich schon Probleme, hier anzusetzen. Meine Ideen: Zunächst würde ich gerne die minimale Länge des Wortes bestimmen um es in drei Teile zu zerlegen. In den Beispielen, die ich zu diesem Thema gefunden habe, war so zumindest meine Interpretation ein konkretes Wort schon gegeben. Bsp.: $[latex]<br /> L := \{0^n1^{2n}2^{3n} \|n \in \mathbb{N}\}<br /> [/latex]$ Wie muss ich dann in meinem Fall vorgehen um zunächst die Konstante n zu bestimmen?


16.04.2015, 15:16	Auf diesen Beitrag antworten »
Karlito	Hallo Piep000r, leider ist das Pumping-Lemma und der Nachweis der Nichterkennbarkeit nicht gerade meine Stärke, aber ein paar Argumente: Man kann in regulären Sprachen nicht zählen. Daher ist ein Vergleich auf gleiche Anzahl von 0 und 1 eher schlecht (reicht natürlich nicht als Beweis aus). Eventuell ist das Pumping-Lemma hier auch nicht das Mittel der Wahl. Ein anderer Ansatz wäre die Nerode-Rechtskongruenz. Damit sollte sich feststellen lassen, dass man bei jeder Verlängerung des Wortes mehr Kongruenzklassen benötigt und somit mehr Zustände im Automaten. Das hätte zur Folge, dass man nicht mit einer endlichen Menge von Zuständen auskäme und somit die Sprache nicht regulär wäre... Gruß, Karlito
16.04.2015, 16:18	Auf diesen Beitrag antworten »
Piep000r	Hallo Karlito, das Pumping-Lemma ist auf jeden Fall in unserer Veranstaltung vorgeschrieben für diese Aufgabe. Ich würde dann vermutlich den folgenden Ansatz wählen: $[latex]<br /> L = \{ 0^{n_0}1^{n_0} \| n \in \mathrm{N} \}<br /> <br /> <br /> \|w\| = \| 0^{n_0}1^{n_0} \| = 2 *{n_0}<br /> <br /> \Rightarrow \|w\| \geq {n_0}<br /> [/latex]$ Also sollte man dann w doch in 3 Teile zerlegen können, oder? Bin mir aber zum einen nicht sicher, ob ich es formal korrekt beschrieben habe und zum anderen ob der Ansatz so überhaupt zulässig ist. Gruß Piep000r

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »