Informatiker Board | Theoretische Informatik | Pumping Lemma

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma - Reguläre Sprache

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Pumping Lemma - Reguläre Sprache

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Piep000r
Grünschnabel

Dabei seit: 16.04.2015
Beiträge: 4

Pumping Lemma - Reguläre Sprache

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo. Ich befasse mich damit herauszufinden, ob die folgende Sprache regulär ist, oder nicht:

$[latex] L = \{w \in (0,1)^{\ast} | (|w|_0 = |w|_1)\} [/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] L := \{0^n1^{2n}2^{3n} |n \in \mathbb{N}\} [/latex]$

Wie muss ich dann in meinem Fall vorgehen um zunächst die Konstante n zu bestimmen?

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Piep000r: 16.04.2015 13:28.

16.04.2015 12:46

Nehmen Sie Piep000r in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 15:16

Nehmen Sie Karlito in Ihre Freundesliste auf

Piep000r
Grünschnabel

Dabei seit: 16.04.2015
Beiträge: 4

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] L = \{ 0^{n_0}1^{n_0} | n \in \mathrm{N} \} |w| = | 0^{n_0}1^{n_0} | = 2 *{n_0} \Rightarrow |w| \geq {n_0} [/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

16.04.2015 16:18

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Pumping Lemma - Reguläre Sprache