Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Zeigen Sie, dass diese Sprache nicht regulär ist

Zeigen Sie, dass diese Sprache nicht regulär ist

Universität / Fachhochschule

Sonstiges

Tags: GTI, informatik, Pumping Lemma, reguläre Sprachen, Sonstig

UltraVio aktiv_icon

18:39 Uhr, 07.07.2019

Hallo Leute ich versuche das Pumping Lemma zu verstehen. Womit man zeigen kann, dass eine Sprache nicht regulär ist. Da mir das Pumping Lemma irgendwie trivial erscheint dazu ein Beispiel.

L = {{a^{i} b^{j} | i, j \in ℕ}}

ist eine reguläre Sprache. Ich kann aber das pumping lemma verwenden und beweisen das es nicht regulär ist.

Wir nehmen an

L

ist eine reguläre Sprache.
Wir wählen Pumping Länge

= p

.
Wir wählen

w \in L, w = a^{p - 2} b^{p + 2} \in L

.
Wir zerlegen

w

in xy^iz, sodass

| y | > 0

und |xy|

\leq p

x = a, y = a^{p - 3} b b, w = b^{p}

.
Wir pumpen

y

mit

i = 2

.
Also dann ist xy²z

= a a^{p - 3} b b a^{p - 3} b b b^{p + 2}

.
Dann haben wir ein Wort welches nicht in

L

ist. Deshalb ist die SPrache nicht regulär.

Die Sprache ist doch aber regulär(Wo ist mein Fehler).

Einfach ausgedrückt die Sprache ist regulär. Ich kann doch aber

y

so wählen, dass sowohl a als auch

b

drin ist. Wenn ich das dann pumpe bekomme ich ein Wort welches nicht mehr in

L

ist.

MfG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1475354

	Status: nicht eingeloggt	Noch nicht registriert?