Informatiker Board | Druckvorschau: Reguläre Sprache und Beweis

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)
--- Reguläre Sprache und Beweis (http://www.informatikerboard.de/board/thread.php?threadid=209)

Geschrieben von ICEMAN am 07.06.2007 um 20:43:

Reguläre Sprache und Beweis

Hi there!

Ich würde gern wissen, ob die Sprache L{(ab)^i (ab)^j; i<>j; i,j >0}
regulär ist oder nicht.

Wenn regulär, wie sieht dann der Automat aus? Wenn nicht regulär, wie ist der korrekte Beweis?

Meiner Meinung nach sollte sie nicht regulär sein, weil es ein kleinstes gemeinsames Vielfaches gibt und irgendwann i=j ist. Andererseits bin ich aber auch nicht sicher, ob es nicht doch einen DFA gibt.

Helft mir...

Gruß, Jens

Geschrieben von Tobias am 07.06.2007 um 22:33:

Versuchs mal mit dem Pumping Lemma.

D.h. setze eine beliebige Zahl n voraus, erzeuge ein Wort und beweise, dass jede Zerlegung dieses Wortes zu einem aufgepumpten Wort führt, das nicht in L liegt.

Tipp:

$[latex](ab)^n(ab)^{1\cdot 2 \cdot \ldots \cdot n}[/latex]$

Geschrieben von ed209 am 08.06.2007 um 18:12:

RE: Reguläre Sprache und Beweis

Zitat:

Original von ICEMAN
Hi there!

Ich würde gern wissen, ob die Sprache L{(ab)^i (ab)^j; i<>j; i,j >0}
regulär ist oder nicht.

Unterscheidet sich L{(ab)^i (ab)^j; i<>j; i,j >0} in irgendeiner Art und Weise von L{(ab)^(i+j); i<>j; i,j >0}?

Gruß,
ED209

Geschrieben von ICEMAN am 09.06.2007 um 11:49:

RE: Reguläre Sprache und Beweis

Das ist ne gute Frage. So hab ich das noch nicht betrachtet. Mathematisch bzw. Theoretisch gesehen könnte man das so zusammenfassen, ja. Aber was ändert das?

Geschrieben von Tobias am 09.06.2007 um 13:45:

Oha, das hab ich auch komplett übersehen. Dafür lässt sich ein Automat wirklich einfach konstruieren.