Fragen zu regulären Sprachen
Torsten Giebl
1. Ist a^n b^n regulär ?
2. Ist (ab)^n regulär ?
Vielen Dank.
Martin Fuchs
> Hallo !
Gestern die Einführungsstunde zu regulären Sprachen gehabt
und heute sollen wir die erste Hausaufgabe für dich lösen?
Sowas ist hier sehr gern gesehen, besonders, wenn man
sich nicht mal die Mühe macht, die Frage formal vollständig
zu formulieren.
> 1. Ist a^n b^n regulär ?
Das ist gewöhnlich die erste Sprache, die man nutzt,
um die Anwendung des "Pumping Lemma" für reguläre
Sprachen zu zeigen.
> 2. Ist (ab)^n regulär ?
Versuch' doch mal, einen DFA anzugeben, der diese Sprache
akzeptiert.
mf
Stefan Nobis
> 1. Ist a^n b^n regulär ?
> 2. Ist (ab)^n regulär ?
Eine von den beiden ist regulär, die andere nicht. Die Frage lässt
sich recht leicht beantworten, wenn man sich eine der zentralen
Eigenschaften endlicher Automaten (und damit auch regulärer Sprachen)
vor Augen führt. Tipp: Hat etwas mit Gedächtnis und der Fähigkeit zu
zählen zu tun.
--
Stefan.
Florian Noack
>
> 1. Ist a^n b^n regulär ?
> 2. Ist (ab)^n regulär ?
>
Versuch doch mal, reguläre Ausdrücke zu finden.
Gruß, Florian
Christian
> 1. Ist a^n b^n regulär ?
> 2. Ist (ab)^n regulär ?
Torsten Giebl
> Gestern die Einführungsstunde zu regulären Sprachen gehabt
> und heute sollen wir die erste Hausaufgabe für dich lösen?
>
> Sowas ist hier sehr gern gesehen, besonders, wenn man
> sich nicht mal die Mühe macht, die Frage formal vollständig
> zu formulieren.
Was für ein Käse. Nicht jeder der hier eine Frage stellt,
möchte das seine Hausaufgaben gelöst werden. Bei 1. war ich mir
sicher das sie nicht regulär ist, aber nicht bei 2.
CU
Martin Fuchs
> Was für ein Käse. Nicht jeder der hier eine Frage stellt,
> möchte das seine Hausaufgaben gelöst werden. Bei 1. war ich mir
> sicher das sie nicht regulär ist, aber nicht bei 2.
Das passt ins Bild.
Du machst dir nicht mal die Mühe, deine Frage vernünftig zu formulieren,
geschweige denn, deinen Hintergrund/Wissensstand, deine Vermutungen und
Lösungsansätze mitzuteilen.
Gerade bei der zweiten Sprache springt einen der zugehörige
endliche Automat doch geradezu an, wenn man weiß, was eine reguläre
Sprache ist und bereit ist, mal 2 Minuten nachzudenken.
mf
Torsten Giebl
> Das passt ins Bild.
> Du machst dir nicht mal die Mühe, deine Frage vernünftig zu formulieren,
> geschweige denn, deinen Hintergrund/Wissensstand, deine Vermutungen und
> Lösungsansätze mitzuteilen.
Sicher hätte ich die beiden Fragen ausführlicher stellen können,
aber anzunehmen das jeder der eine Frage stellt, gleich Hausaufgaben
erledigt haben möchte, ist absurd.
CU
Heinrich Moser
> Martin Fuchs schrieb:
Nur so aus Neugier (und um vielleicht den sich ankündigenden Streit
gleich im Keim zu ersticken): Was war denn der konkrete Hintergrund
der Frage?
LG,
Heinzi
Heinrich Moser
> Heinrich Moser <use...@heinzi.at> writes:
>> Nur so aus Neugier (und um vielleicht den sich ankündigenden Streit
>> gleich im Keim zu ersticken
>
> Raum zu schaffen.
...allerdings mit der Intention, dieses wieder auf informatische
Bahnen zu lenken, siehe unten. Den gleichen Vorwurf kann man dir nun
übrigens auch machen. ;-)
>> ): Was war denn der konkrete Hintergrund
>> der Frage?
>
> Der »Hintergrund« von Fragen gehört nicht unbedingt zum Thema
> dieser Gruppe »de.sci.informatik.misc«.
>
> An einer Frage in dieser Gruppe interessiert mich der
> fachliche Inhalt dieser Frage und dieser liegt bereits vor.
Mit "nicht unbedingt" hast du recht, allerdings liegen die meisten
Anwendungsbereiche regulärer Sprachen *innerhalb* der Informatik (mit
ein paar Ausnahmen wie z.B. dem Lösen von Hausaufgaben, aber das hat
der OP ja schon ausgeschlossen). Daher war meine Hoffnung, dass sich
daraus vielleicht eine interessantere Diskussion als "Hausaufgabe
ja/nein" entwickelt (z.B. "Ich versuche, eine Regular Expression für
diesen oder jenen Anwendungszweck zu basteln" oder "Ich versuche zu
verstehen, warum..."). Denn...
> Ob diese Frage durch eine Hausaufgabe motiviert wurde
> ist dafür nicht von Bedeutung. Ich will Autoren von Fragen
> hier auch nicht ausforschen.
...hier bin ich mit dir ganz einer Meinung.
LG,
Heinzi
Stefan Reuther
Die Erfahrung zeigt allerdings, dass quasi jeder, der eine Frage in
dieser Kürze und ohne jeglichen Ansatz eines eigenen Gedankens stellt,
eine Hausaufgabe gelöst haben will. Insbesondere, wenn es sich um
Aufgaben handelt, die im Normalfall in der ersten Vorlesung drankommen.
Stefan
Florian Noack
Hash: SHA256
Stefan Reuther schrieb:
> Insbesondere, wenn es sich um
> Aufgaben handelt, die im Normalfall in der ersten Vorlesung drankommen.
>
Andererseits hat er die Frage zum Semesterende gestellt.
Grüße, Florian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEAREIAAYFAknJR3sACgkQjACxo+SKLOXsyQCZAbcj2y7dyJ0A+RY2YmVN6YKe
2ygAni8eAUDAoaTB/MW4UnwCvz8cz226
=jnFc
-----END PGP SIGNATURE-----
Heinrich Moser
> Stefan Reuther schrieb:
>> Insbesondere, wenn es sich um
>> Aufgaben handelt, die im Normalfall in der ersten Vorlesung drankommen.
>
> Andererseits hat er die Frage zum Semesterende gestellt.
Nein, er hat sie zu Semesterbeginn gestellt.
LG,
Heinzi
Florian Noack
Hash: SHA256
Heinrich Moser schrieb:
Das sehen die Autoren von [1] anders ;)
Grüße, Florian
[1] http://www.ferienzeitweb.de/semesterferien.htm
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEAREIAAYFAknKXqAACgkQjACxo+SKLOVBvwCfSTrCl09KmEj/95s6spntmMH+
EzMAn1cHSREPzdbflH1kuyCZHwrWBQxg
=aUFg
-----END PGP SIGNATURE-----
Heinrich Moser
> Heinrich Moser schrieb:
>> Florian Noack <sen...@gmx.de> writes:
>>> Stefan Reuther schrieb:
>>>> Insbesondere, wenn es sich um
>>>> Aufgaben handelt, die im Normalfall in der ersten Vorlesung drankommen.
>>> Andererseits hat er die Frage zum Semesterende gestellt.
>>
>> Nein, er hat sie zu Semesterbeginn gestellt.
>>
>
> Das sehen die Autoren von [1] anders ;)
>
Dem stelle ich [2] entgegen. ;-)
LG,
Heinzi
Florian Noack
Hash: SHA256
Heinrich Moser schrieb:
Ich habe ca. 60 Gegenbeispiele gezeigt, du 1. Das ist eine erdrückende
Mehrheit :p Wir könnten auch einfach nachfragen, ob es Hausaufgaben
waren: Hey Torsten, sind das Hausaufgaben gewesen?
Beste Grüße,
Florian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEAREIAAYFAknKqtkACgkQjACxo+SKLOX1pACgqlvuDzLHLTJLTqaAjh9TE0CK
ZQoAmQG5bKNMyZRDwzcgYaKlxPj6e3Y7
=MfH+
-----END PGP SIGNATURE-----
Johannes Starosta
> Andererseits hat er die Frage zum Semesterende gestellt.
Also dann, wenn Klausuren geschrieben werden...
--
MFG, - nicht dass ich etwas unterstellen wollte- Johannes.
PGP Fingerprint: 719A 160A 6643 889E 851D CE3C 71CA 824A 2E44 AC29
PGP: keyID: 2E44AC29 0x71ca824a2e44ac29
Heinrich Moser
> Heinrich Moser schrieb:
>> Florian Noack <sen...@gmx.de> writes:
>>> Heinrich Moser schrieb:
>>>> Florian Noack <sen...@gmx.de> writes:
>>>>> Stefan Reuther schrieb:
>>>>>> Insbesondere, wenn es sich um
>>>>>> Aufgaben handelt, die im Normalfall in der ersten Vorlesung drankommen.
>>>>> Andererseits hat er die Frage zum Semesterende gestellt.
>>>> Nein, er hat sie zu Semesterbeginn gestellt.
>>>>
>>> Das sehen die Autoren von [1] anders ;)
>>>
>>> [1] http://www.ferienzeitweb.de/semesterferien.htm
>>
>> Dem stelle ich [2] entgegen. ;-)
>>
>
> Ich habe ca. 60 Gegenbeispiele gezeigt, du 1. Das ist eine erdrückende
> Mehrheit :p
Es ging mir auch eher darum, darauf hinzuweisen, dass "jemand postet
in de.*" => "der Poster ist aus Deutschland" ein Trugschluss ist, und
habe aus rhetorischen Gründen mit der gleichen Überzeugung angenommen,
der OP wäre Österreicher. ;-)
LG,
Heinzi
Florian Noack
Hash: SHA256
Heinrich Moser schrieb:
Ok, dann haben wir jetzt ein unwichtiges Thema maximal aufgebläht ;)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEAREIAAYFAknMyH0ACgkQjACxo+SKLOUC7QCgoKBz7Y624XdiyBB+GeGBMI2l
W5IAoJSXv9m3Ii9bOrKZ6CmmexOroCvF
=fdBz
-----END PGP SIGNATURE-----