 Reguläre Sprache und Beweis |
ICEMAN 
Grünschnabel
Dabei seit: 07.06.2007
Beiträge: 2
Herkunft: Boppard, Mannheim
 |
|
| 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
|
|
07.06.2007 20:43 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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:
^n(ab)^{1\cdot 2 \cdot \ldots \cdot n}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?(ab)^n(ab)^{1\cdot 2 \cdot \ldots \cdot n})
|
|
|
07.06.2007 22:33 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
| 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
|
|
|
08.06.2007 18:12 |
|
|
ICEMAN
Grünschnabel
Dabei seit: 07.06.2007
Beiträge: 2
Herkunft: Boppard, Mannheim
|
|
| 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?
|
|
|
09.06.2007 11:49 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Oha, das hab ich auch komplett übersehen. Dafür lässt sich ein Automat wirklich einfach konstruieren.
|
|
|
09.06.2007 13:45 |
|
|
|
