Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Pumping Lemma - Reguläre Sprache (http://www.informatikerboard.de/board/thread.php?threadid=2224)
Geschrieben von Piep000r am 16.04.2015 um 12:46:
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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
L = \{w \in (0,1)^{\ast} | (|w|_0 = |w|_1)\}<br />
)
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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
L := \{0^n1^{2n}2^{3n} |n \in \mathbb{N}\}<br />
)
Wie muss ich dann in meinem Fall vorgehen um zunächst die Konstante n zu bestimmen?
Geschrieben von Karlito am 16.04.2015 um 15:16:
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
Geschrieben von Piep000r am 16.04.2015 um 16:18:
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]](http://www.matheboard.de/latex2png/latex2png.php?<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 />
)
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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH