PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Frage(n) zur theoretischen Informatik


Senior Sanchez
2009-02-19, 13:08:08
Hi,

Ich lerne gerade für die theoretische Informatik Klausur am Montag und bin gerade auf eine Situation gestoßen, die ich nicht ganz verstehe.

Es geht um reguläre Sprachen, also solche Sprachen die mit regulären Ausdrücken oder endlichen Automaten beschreiben lassen.

Nun lese ich hier im Buch, dass die folgende Sprache regulär ist...

L = {w element {0,1}* | |w|1 <= 2}

Es handelt sich also um die Sprache, die alle Wörter enthält, deren Wörter höchstens zwei Einsen enthalten.
Ich kann dafür ja ohne Probleme einen endlichen Automaten oder regulären Ausdruck konstruieren, der das nachweist und hätte somit gezeigt, dass sie regulär ist.
Allerdings müsste dafür ja auch das Pumping Lemma gelten, dass bekanntlich besagt, dass es für eine reguläre Sprache ein n>=1 gibt, sodass für alle Wörter der Länge >= n eine Zerlegung in w=xyz existiert ( |xy| <= n, y nicht leer). Ferner muss dann für jedes i>=0 das Wort xy^iz wieder in der Sprache liegen, was beim Verfielfältigen von Einsen ja nicht sein würde.

... ach verdammt, jetzt ist mir mein Denkfehler gerade beim Schreiben aufgefallen. *g* Es muss ja nur eine Zerlegung gelten und sobald das Wort mindestens die Länge 3 hat, kann ich das y als die 0 auffassen, was sich ja beliebig aufpumpen lässt.

Ich lass den Thread trotzdem mal hier, falls ich noch mal Fragen habe oder es noch einmal nachlesen will.

pest
2009-02-19, 16:43:31
wie habe ich es gehasst :wink:
viel Erfolg

Senior Sanchez
2009-02-19, 17:20:34
Hehe, danke.

Aber ich sage dir eins: Wenn du mal Regelungstechnik gehört hast und da genauso gekotzt hast wie ich, dann wirst du die theoretische Informatik lieben, weil das dagegen irgendwie relativ einfach ist.

Coda
2009-02-19, 19:14:11
Ich glaube jeder hat seine Stärken und Schwächen in unterschiedlichen Bereichen. Rein aus Interessensgründen würde ich Regelungstechnik wohl trotzdem um einiges vorziehen.

Theoretische Info ist bis auf ein paar Sachen verdammt unnötig. Zumindest so wie es gelehrt wird.

Oid
2009-02-19, 20:17:26
Ich mag Regelungstechnik :).

Aber von theoretischer Info hab ich keine Ahnung, sry :D

PatkIllA
2009-02-19, 20:25:07
Reguläre Ausdrücke kann man ja wirklich in der Praxis benutzen. Wobei der Einsatz bei uns auch nicht mal erwähnt wurde.

Senior Sanchez
2009-02-19, 20:46:52
Ich mag Regelungstechnik :).

Aber von theoretischer Info hab ich keine Ahnung, sry :D

Nach der Klausur vom Montag, wo alle gekotzt haben, würdest du das vielleicht auch anders sehen. :D

Naja, am Montag ist "Theoretische Informatik"-Klausur, dann ist erstmal nen bissl Pause.

Monger
2009-02-19, 21:00:22
Reguläre Ausdrücke kann man ja wirklich in der Praxis benutzen. Wobei der Einsatz bei uns auch nicht mal erwähnt wurde.
Wobei es äußerst, äußerst selten passiert dass man seinen eigenen Parser dafür schreibt.

Ich hatte auch ne Vorlesung in Compilerbau, wo der Prof natürlich auch voller Inbrunst vertreten hat, dass es unglaublich praktisch ist wenn man sich mal fix seine eigene Grammatik für eine neue Sprache zusammenzimmern kann. Ich will das nicht ausschließen, es gibt ja nunmal wirklich unzählige Sprachen und Dialekte für jeden Anwendungszweck, aber ich konnte damit absolut nix anfangen. Ich weiß von der Vorlesung heute praktisch gar nichts mehr.

Trap
2009-02-19, 22:30:42
Theoretische Informatik ist nicht nur das was in der Grundstudiumsveranstaltung dazu vorkommt.

Semantik, Verifikation und Transformation von Programmen sind durchaus interessante und auch nützliche Themen der theoretischen Informatik, im Grundstudium kommen sie aber nicht dran.