Dumme Fragen - es gibt sie DOCH!

Original von Pan
Nein, dass ist falsch!

ICH SAG DOCH, ICH WEISS NIX. xD (Man sollte nicht mitten in der Nacht ueber Informatik nachdenken.) (Du bist ja doch draufgekommen?)

Hast natuerlich Recht, ich hatte schon {a, b}* und {a, b, c}* gemeint.
Die eckigen Klammern hab ich von Ark so uebernommen, ohne drueber nachzudenken.

Hm, ja. Ich bin ja dafuer, dass du dich den eigentlichen Fragen mal annimmst. :3

(Au weia, gleich gibt es hier Tote zu beklagen. Was habe ich nur angerichtet! xD~)

Entschuldigt bitte, wenn ich mich wohl für euch missverständlich ausgedrückt habe. Meine Schreibweise kommt direkt aus der Unix-Welt (oder ist sogar allgemeine Konvention) und hat den Vorteil, dass man sich nicht mit Hochstellungen oder Sonderzeichen (Epsilon) herumschlagen muss. Zudem ist sie kompakter. Fälschlicherweise ging ich davon aus, dass sie bekannt wäre. Hier kann man mehr dazu nachlesen.

Ark

Argh, ja, RegEx ist uns durchaus bekannt. Zumindest in der Theorie. xD
Man merkt, dass ich zu wenig mit sowas zutun habe und es erst recht nicht brauche, sonst haette ich die "Regeln" eher noch im Kopf. x__x
Also hats doch so gestimmt, wie es oben stand ... Gnaaaaah. Da hat man ein Semester lang kein Info mehr und schon ist man total in der Unfaehigkeit versackt.

Ach, reguläre Ausdrücke... und ich dachte mir heute morgen noch "Oder sind vielleicht reguläre Ausdrücke gemeint?"
Reguläre Ausdrücke sind in der theoretischen Informatik leicht anders definiert, als die Unix-RegEx. Insbesondere gibts dort keine Quantoren die sagen "Zeichen X muss so und so oft vorkommen". Die Definition für Reguläre Ausdrücke bei uns an der Uni gelehrt wird, ist insbesondere so, dass man nur reguläre Sprachen darstellen kann. Also nur Sprachen vom Typ Chomsky-3.
Die Unix-RegEx können scheinbar auch Sprachen vom Typ Chomsky-2 darstellen. Naja, auf jedenfall: Reguläre Ausdrücke sind zu schwach um alle Chomsky-Typen abzudecken.
Aber darum gings ja gar nicht

Mal zu deiner Ausgangsfrage zurück: Der Begriff "Ausdrucksstärke" ist mir bisher noch nie über den Weg gelaufen. Ich hab extra nochmal die beiden Info-Skripte, die ich zu dem Thema auf dem Rechner hab, durchsucht und konnt dazu nichts finden.
Lunas Einfall klingt auf mich aber durchaus plausibel, ob das aber wirklich die gültige Definition ist, kann ich nicht sagen. Per Google hab ich dazu auch nichts gefunden.

Mal zur Unendlichkeit. So doof es klingt, Unendlich ist nicht gleich Unendlich. Unendlich darf man sich nicht als Zahl vorstellen, sonst gibt es da diese Gedankenprobleme, die du gerade hast.

Recht einfaches Beispiel: Es gibt unendlich viele positive gerade Zahlen. Genauso gibt es unendlich viele ungerade Zahlen. Die Menge der natürlichen Zahlen ist ebenfalls unendlich groß, aber "größer" als diese beiden Mengen enthält.

Oder dein Beispiel: [ab]* und [abc]*
Beide sind unendlich groß, aber [abc]* enthält ALLE Wörter, die [ab]* enthält. Deshalb ist [abc]* durchaus größer oder anders gesagt mächtiger. Mächtiger ist eigentlich das bessere Wort. Natürlich ist in [abc]* mehr drin als in [ab]*. In [ab]* gibts keine Worte, die ein c enthalten, in [abc]* aber durchaus und [abc]* enthält alle Wörter aus [ab]*.

Original von Ark

Seien G1 und G2 Grammatiken, wobei G2 in wie auch immer gearteter Weise hinsichtlich der möglichen Produktionsregeln eingeschränkter ist als G1 (siehe z.B. CH). Ferner sei vorausgesetzt, dass L(G1) eine (evtl. unechte) Teilmenge von L(G2) ist. Anders ausgedrückt: Die eingeschränktere Grammatik "frisst" mindestens das, was die uneingeschränktere hergibt.

Behauptung: G2 frisst "zu viel", lässt also mehr zu als G1.

Stimmt das immer (oder überhaupt xD)?

Du setzt vorraus, dass gilt: L(G1) Teilmenge von L(G2). Anders ausgedrückt: Alle Worte in L(G1) sind ebenfalls Worte von L(G2).

L(G) ist die Sprache der Wörter, die aus G abgeleitet werden.
Dann kann G2 aber nicht eingeschränkter sein als G1. Wäre G2 eingeschränkter als G1, könnte man mit G1 Wörter ableiten, die man mit G2 nicht ableiten kann.

Das ist ein Widerspruch. Sowas geht nicht. Damit eine Menge A Teilmenge einer Menge B sein kann, muss A vollkommen in B enthalten sein. Wäre G2 also eingeschränkter als G1 kann ich mit G1 Wörter ableiten, die ich mit G2 nicht ableiten kann. Widerspruch zur Teilmengenbeziehung.

Oder meinst du mit "Eingeschränkter" etwas anderes?
Was z.B. geht, ist, dass man für eine Chomsky-3 Sprache eine Grammatik vom Typ Chomsky-1 baut (gut, eigentlich sind Chomsky-3 Sprache eh von diesem Typ.... es gilt ja Chomsky-3 ⊂ Chomsky-2 ⊂ Chomsky-1 ⊂ Chomsky-0).
Dann hast du eine Chomsky-1 Grammatik und eine Chomsky-3 Grammatik, die beide das selbe beschreiben, aber eine davon ist "eingeschränkter"...

"Eingeschränkter" ist ein zu ungenaues Wort Da kann man zuviel reininterpretieren. Was du mit "frisst" meinst, versteh ich auch nicht ganz.

Original von Ark
Also, jetzt mal bildlicher, an einem Beispiel: Typ 2 kriegt es hin, Klammernpaare zu erkennen. Typ 3 hat von so was keine Ahnung. Man könnte zwar etwas Derartiges nachbauen, aber wenn man erreichen will, dass Typ 3 genau alle zulässigen Klammernpaare erkennt, die also laut Typ 2 gültig sind, bräuchte man unendlich viele Regeln.

Nein! Das ist nicht möglich. Mit Chomsky-3 kannst du keine Grammatik bauen, die Chomsky-2 Sprachen erkennen. Dafür braucht man, wie du es sagst, unendlich viele Regeln und das ist per Definition nicht erlaubt.

Original von Ark
Um das Problem mit der unendlich langen Vorschrift zu "lösen", könnte man auf die Idee kommen, einfach [(]* bzw. [)]* an den entsprechenden Stellen zu verwenden. Dann hat man allerdings das Problem, dass zu viel zugelassen würde, also auch Wörter angenommen werden, die nach Typ 2 nicht mehr gültig wären. Das meine ich mit "frisst zu viel".

Ja, eben. Mit diesen Regeln kriegst du es nicht hin zu sagen, dass Klammerpaare erkannt werden. Okay, ich glaube, ich verstehe auf was du hinaus willst.

Z.B. sei L(G1) die Sprache [(]*a[)]*, L(G1) ist Chomsky-3, sei L(G2) die Sprache (^n a )^n, L(G2) ist Chomsky-2. L(G1) enthält aber auch alle Wörter von L(G2)... G2 ist aber "eingeschränkter". ABER: L(G1) ist nicht Teilmenge von L(G2). In L(G1) gibts Wörter, die es in L(G2) nicht gibt.
Das ist doch gar kein schlechtes Beispiel, dass das, was du möchtest, so nicht geht.

Aber "Eingeschränkter" ist halt echt ein ungenaues Wort, da kann man viel reininterpretieren, z.B. die Sprache L(G3) = [(]*a[)]* | (^n a )^n
ist auch vom Typ Chomsky-2, nach deiner Meinung also vielleicht "eingeschränkter", aber enthält L(G1), aber auch L(G2). Insofern würde ich L(G3) dann doch nicht als eingeschränkter ansehen

Man könnte z.B. auch sagen Chomsky-3 als Chomsky-2 ist eingeschränkter, weil ich damit keine Klammerpaare erkennen kann.

Generell kann man sich die Chomsky-Hierarchie vielleicht besser so vorstellen, dass die logischen Sturkturen, die ich in eine Sprache bauen kann, immer höher werden, je niedriger der Chomsky-Typ. Bei Chomsky-3 kann ich nur ganz "dumme" Sprachen bauen, mit Chomsky-0 krieg in prinzipiell alles mögliche hin.

Original von Ark
Von dieser Beobachtung ausgehend vermute ich jetzt einfach mal, dass das generell so ist: Wenn für eine Grammatik weniger Regeln zugelassen sind (also eingeschränkter, in Richtung reguläre Sprachen), dann würde sie Wörter zulassen, die in Grammatiken, wo mehr Regeln möglich sind, nicht mehr möglich wären. Anders gesagt: Wenn ich weniger regeln darf, aber Wörter bestimmter höherer Regeln durchlassen soll, dann lasse ich zwangsläufig mehr durch; schließlich fehlen mir die Möglichkeiten, um zu sagen "Nein, du darfst hier nicht rein".

Ja, damit hast du Recht, diese Beobachtung stimmt. Je weiter man in Richtung reguläre Sprachen geht, desto weniger Möglichkeiten hat man um logische Strukturen in den Wörtern zu verlangen.
Wobei ich deine Formulierungen leicht schwammig finde
"Regeln höherer Ordnung" - Was meinst du damit?

Wenn ich das richtig gesehen habe, hast du hier eigentlich erkannt, dass
Chomsky-3 ⊂ Chomsky-2 ⊂ Chomsky-1 ⊂ Chomsky-0
gilt

Ich hoffe mal, dass hilft dir ein bisschen was. Ich hab leider nicht das Gefühl, deine Fragen klar beantwortet zu haben, aber sie sind leider teilweise schon etwas unpräziese
Frag ruhig noch nach, wenn du weitere Fragen hast.

Schonmal überlegt nach deiner Ausbildung Informatik zu studieren, wenn dir sowas Spass macht?

Gibt es einem HTML-Tag für Double Strike?

Was meinst du mit Double Strike? Durchgestrichen mit zwei Linien? Unterstrichen mit zwei Linien?

Da strike durchgestrichen und underline unterstrichen ist, dachte ich, wäre klar, dass ich jenes meine. xD; Ja, doppelt durchgestrichen.

Ist es eigentlich auch, aber ich glaub, sowas hab ich noch nie gesehen und wuesste spontan auch nicht, wie das machbar waere. xD;
Vielleicht weiss jemand anders Rat, aber ich fuerchte fast, sowas laesst sich ueber HTML-Tag nicht machen. Du koenntest allerdings einfach manuell das Zeug tippen, durchstreichen und als Bild hochladen, wenn's nicht allzu viel/lang ist.

Ich habs grad mal ueber Word versucht, dort kann man ja doppelt durchstreichen und Dateien auch als .html speichern, da kommt aber beim Speichern dann auch nur die Meldung: ""Doppelt durchgestrichen" wird geändert zu "durchgestrichen"" - es scheint in HTML also tatsaechlich nur normales Durchstreichen zu funktionieren.

Die Befürchtung hatte ich auch, aber ich dachte, wir haben ja einige Informatiker hier, vielleicht wüsste jemand Rat.
So dringend ist es aber nicht, war nur eine Frage, weil google mir auf die Schnelle auch nichts ausgespuckt hat. xD

SelfHTML kennt dafür auch keine Tags, von daher geh ich auch mal davon aus, dass das nicht geht.

Original von Pan
Reguläre Ausdrücke sind in der theoretischen Informatik leicht anders definiert, als die Unix-RegEx. Insbesondere gibts dort keine Quantoren die sagen "Zeichen X muss so und so oft vorkommen". Die Definition für Reguläre Ausdrücke bei uns an der Uni gelehrt wird, ist insbesondere so, dass man nur reguläre Sprachen darstellen kann. Also nur Sprachen vom Typ Chomsky-3.
Die Unix-RegEx können scheinbar auch Sprachen vom Typ Chomsky-2 darstellen. Naja, auf jedenfall: Reguläre Ausdrücke sind zu schwach um alle Chomsky-Typen abzudecken.

So weit mir bekannt ist, kann man mit den Regex aus der Unix-Welt genau Typ 3 abdecken. Typ 2 geht schon mal gar nicht, und kontextsensitive Regeln lassen sich nur in diversen Erweiterungen festlegen (für die wiederum Typ 3 reichen muss).

Die Quantoren sind einfach nur Potenzen, die ihr an der Uni auch behandelt haben dürftet (nehme ich jetzt einfach mal an xD). Ich habe es auf einem gerade direkt vor mir liegenden Zettel mal nachvollzogen und für alle Unix-Regex (ohne kontextsensitive Erweiterungen) Darstellungen gefunden, die mit den hier genannten Regeln konform gehen. Bei Bedarf kann ich die ja mal hier hochladen.

Original von Pan
Mal zu deiner Ausgangsfrage zurück: Der Begriff "Ausdrucksstärke" ist mir bisher noch nie über den Weg gelaufen. Ich hab extra nochmal die beiden Info-Skripte, die ich zu dem Thema auf dem Rechner hab, durchsucht und konnt dazu nichts finden.
Lunas Einfall klingt auf mich aber durchaus plausibel, ob das aber wirklich die gültige Definition ist, kann ich nicht sagen. Per Google hab ich dazu auch nichts gefunden.

Schade. Ich habe gerade noch einmal gesucht, aber außer dass hier ein gesuchtes Wort auf Seite 7 auftaucht, steht auch nicht vielmehr dazu drin.

Original von Pan
Mal zur Unendlichkeit. [...]

Warum erinniert mich das an Hilberts Hotel?!

Original von Pan
Aber "Eingeschränkter" ist halt echt ein ungenaues Wort, da kann man viel reininterpretieren, z.B. die Sprache L(G3) = [(]*a[)]* | (^n a )^n
ist auch vom Typ Chomsky-2, nach deiner Meinung also vielleicht "eingeschränkter", aber enthält L(G1), aber auch L(G2). Insofern würde ich L(G3) dann doch nicht als eingeschränkter ansehen

Hm, ich glaube, ich wurde missverstanden. ^^' Um das Beispiel zu kürzen: Nehmen wir an, dass a in diesem Fall einfach Epsilon ist. Der Teil " (^n a )^n" ist überflüssig, da er von der ersten Alternative sowieso schon abgedeckt ist. Und für die erste Alternative reicht Typ 3. Genau daher kommt ja auch meine Vermutung.

Also noch mal, etwas konkreter:

Ich habe eine Grammatik G1, die (nach allen möglichen Vereinfachungen etc.) solche Regeln enthält, dass sie nicht mehr unter Typ 3, sondern unter Typ 2 fällt. Typ 3 reicht also garantiert nicht. Altbekanntes Beispiel auch hier: Sie soll genau auf a^n b^n passen.

Darunter fielen jetzt Epsilon, ab, aabb, aaabbb, aaaabbbb usw.

Jetzt nehme ich an, ich finde eine Grammatik G2 mit eingeschränkteren Regeln, also zum Beispiel vom Typ 3. Anforderung: Diese Grammatik soll mindestens das zulassen, was schon in G1 zugelassen ist, also Epsilon, ab, aabb usw. Eine solche Grammatik wäre (als Regex geschrieben) a*b*.

Nun ist es aber so, dass sie auch aaaab zulässt, was bei G1 nicht möglich war. Ich behaupte, dass dieses Phänomen damit zusammenhängt, dass G2 eingeschränkter ist. G2 soll das abdecken, was G1 abgedeckt hat, aber weil G2 eingeschränktere Regeln hat, passiert es, dass sie mehr erlaubt als G1.

Original von Pan
Ja, damit hast du Recht, diese Beobachtung stimmt. Je weiter man in Richtung reguläre Sprachen geht, desto weniger Möglichkeiten hat man um logische Strukturen in den Wörtern zu verlangen.
Wobei ich deine Formulierungen leicht schwammig finde
"Regeln höherer Ordnung" - Was meinst du damit?

Mit "höheren Regeln" meine ich Regeln, die weniger Einschränkungen unterliegen. Entschuldige bitte meine eigenartige Ausdrucksweise.

Original von Pan
Ich hoffe mal, dass hilft dir ein bisschen was. Ich hab leider nicht das Gefühl, deine Fragen klar beantwortet zu haben, aber sie sind leider teilweise schon etwas unpräziese
Frag ruhig noch nach, wenn du weitere Fragen hast.

Noch eine offene Frage hier. *g*

Original von Pan
Schonmal überlegt nach deiner Ausbildung Informatik zu studieren, wenn dir sowas Spass macht?

Wenn ich das Geld hätte, würde ich schon lange studieren.

Ark

Also zur Ausdrucksstaerke bzw "ausdrucksstaerker" hatte ich ueber Google auch noch das hier gefunden (ich hoffe, der Link funktioniert brav - ich glaub, das Buch hatte ich letztes Semester auch ausgeliehen und fands ganz okay), aber so wirklich viel steht da auch nicht.

... welch vergeudete Ressourcen. D: Schenk irgendwer mal bitte Ark ein Stipendium?

Bin ich die einzige, die mit eurer "Ausdrucksstärke" überfordert ist?


@topic
Kann mir jemand einen Tipp geben, wie man es schafft, morgens ausnahmsweise mal nicht zu verschlafen, indem man dummerweise auf den Wecker eindrischt? (Abgesehen von früh schlafen gehen, denn das hilft bei mir nicht)
Oh, und die snooze-Fuktion hab' ich auch, aber wenn dann 'ne halbe Stunde alle fünf Minuten was geklingelt hat, kommt auch nix mehr nach - also wie werd' ich schnell wach? ^^'

Original von Ark
So weit mir bekannt ist, kann man mit den Regex aus der Unix-Welt genau Typ 3 abdecken. Typ 2 geht schon mal gar nicht, und kontextsensitive Regeln lassen sich nur in diversen Erweiterungen festlegen (für die wiederum Typ 3 reichen muss).

Die Quantoren sind einfach nur Potenzen, die ihr an der Uni auch behandelt haben dürftet (nehme ich jetzt einfach mal an xD). Ich habe es auf einem gerade direkt vor mir liegenden Zettel mal nachvollzogen und für alle Unix-Regex (ohne kontextsensitive Erweiterungen) Darstellungen gefunden, die mit den hier genannten Regeln konform gehen. Bei Bedarf kann ich die ja mal hier hochladen.

Schau mal beim Wiki-Artikel zu den regulären Ausdrücken (such einfach nach Chomsky, dann findest du es gleich) - da steht, dass die Unix-RegEx meist so implementiert sind, dass Rückwärtsreferenzen möglich sind, wodurch dann auch Chomsky-2 Sprachen darstellbar sind. Ich kenn mich nicht so gut mit den Unix-RegEx aus und weis auch nicht, was die Rückwärtsreferenzen sind, aber scheinbar erlauben sie Chomsky-2

Stimmt, du hast recht. Ich hatte den Artikel nur kurz überflogen, die Quantoren sind wirklich blos die (festen) Potenzen.

Original von Ark
Schade. Ich habe gerade noch einmal gesucht, aber außer dass hier ein gesuchtes Wort auf Seite 7 auftaucht, steht auch nicht vielmehr dazu drin.

Hm, der Link geht bei mir leider nicht

Original von Ark
Warum erinniert mich das an Hilberts Hotel?!

Also wenn du Hilberts Hotel kennst und verstehst, sollte das doch eigentlich ein Klacks sein

Original von Ark
Hm, ich glaube, ich wurde missverstanden. ^^' Um das Beispiel zu kürzen: Nehmen wir an, dass a in diesem Fall einfach Epsilon ist. Der Teil " (^n a )^n" ist überflüssig, da er von der ersten Alternative sowieso schon abgedeckt ist. Und für die erste Alternative reicht Typ 3. Genau daher kommt ja auch meine Vermutung.

Hast Recht, dummes Beispiel, hab ich nicht gut nachgedacht

Original von Ark
Jetzt nehme ich an, ich finde eine Grammatik G2 mit eingeschränkteren Regeln, also zum Beispiel vom Typ 3. Anforderung: Diese Grammatik soll mindestens das zulassen, was schon in G1 zugelassen ist, also Epsilon, ab, aabb usw. Eine solche Grammatik wäre (als Regex geschrieben) a*b*.

Nun ist es aber so, dass sie auch aaaab zulässt, was bei G1 nicht möglich war. Ich behaupte, dass dieses Phänomen damit zusammenhängt, dass G2 eingeschränkter ist. G2 soll das abdecken, was G1 abgedeckt hat, aber weil G2 eingeschränktere Regeln hat, passiert es, dass sie mehr erlaubt als G1.

Ah, okay, jetzt versteh ichs glaub ich. Damit hast du recht, ja. Das liegt wie gesagt daran, dass man bei den verschiedenen Chomsky-Typen immer weniger Anforderungen an die Sprachen stellen kann und da Chomsky-3 ⊂ Chomsky-2 ⊂ Chomsky-1 ⊂ Chomsky-0 gilt, findet man auch immer eine Sprache von niedrigerem Typ (also, für mich ist Chomsky-3 die niedrgiste Stufe, damit wir da nicht aneinander vorbeireden), die die Wörter einer Sprache von höherem Typ enthält + weitere Wörter.

Original von Ark
Noch eine offene Frage hier. *g*

Ah, dass ist einfach

Die Grammatik
S → A
S → b
S → ε
A → B
A → a
B → A
B → b
B → ε
ist vom Typ Chomsky-0. Die Regel B → ε ist nicht erweiternd, somit kann die Grammatik nicht vom Typ Chomsky-1 sein und dann schonmal gar nicht Chomsky-2/-3.

(Oder war das eh schon geklärt?)

Die Regel S → ε ist immer erlaubt, sonst kann man das leere Wort nicht ableiten. Das ist ein Spezialfall.

Ja, Grammatiken vom Typ Chomsky-2 können immer in die sogenannte Chomsky-Normalform überführt werden. Dadurch werden alle Regeln der Form → ε eliminert, außer evtl. S → ε.

Es gibt für Chomsky-2 (oder war es Chomsky-1? Ich weis es nicht mehr... ist dir das wichtig? Dann schau ich mal in meinen Unterlagen) 2 verschiedene Definitionen, eine davon lässt auch ε auf der rechten Seite zu. Aber beide Definitionen sind äquivalent, also ja, dass kommt eigentlich nur aus der Bequemlichkeit.

Original von Ark
Wenn ich das Geld hätte, würde ich schon lange studieren.

Keine Chance auf BAFÖG und dann evtl. noch nebenher ein bisschen Arbeiten? So mach ichs, ich arbeite nebenher am Forschungszentrum für Informatik als HiWi und verdien mir noch ein bisschen was zum BAFöG dazu. Zusammen mit ein bisschen Geld von meinen Eltern komm ich damit gut über die Runden.

Original von bereth15
@topic
Kann mir jemand einen Tipp geben, wie man es schafft, morgens ausnahmsweise mal nicht zu verschlafen, indem man dummerweise auf den Wecker eindrischt? (Abgesehen von früh schlafen gehen, denn das hilft bei mir nicht)
Oh, und die snooze-Fuktion hab' ich auch, aber wenn dann 'ne halbe Stunde alle fünf Minuten was geklingelt hat, kommt auch nix mehr nach - also wie werd' ich schnell wach? ^^'

Wecker, Handy, wasauchimmer weit genug weg platzieren, dass man aufstehen MUSS, um den Wecker abzustellen. Und dann eben aufstehen, wenn man sowieso schon das Bett verlassen musste.

Original von bereth15
Kann mir jemand einen Tipp geben, wie man es schafft, morgens ausnahmsweise mal nicht zu verschlafen, indem man dummerweise auf den Wecker eindrischt? (Abgesehen von früh schlafen gehen, denn das hilft bei mir nicht)
Oh, und die snooze-Fuktion hab' ich auch, aber wenn dann 'ne halbe Stunde alle fünf Minuten was geklingelt hat, kommt auch nix mehr nach - also wie werd' ich schnell wach? ^^'

Kauf' dir einen von diesen coolen Weckern die beim Klingeln irgendwie anfangen durch's Zimmer zu rollen, die man dann erst einfangen muss.

@Luna
Hab' ich schon probiert, aber nur, weil ich mal eben ganz kurz aufstehe, um dann doch draufzuhauen und mich dann kurz einmümmel, weil mir kalt ist, hilft mir das leider auch nicht - schlafe dann doch wieder ein.

@The Wall
Wecker, die durchs Zimmer rollen? Ok, auf der Jagd wird man bestimmt warm und hellwach, danach werd' ich mal suchen!
(Sachen gibt's ^^)

Original von Pan
Hm, der Link geht bei mir leider nicht

So, ich hoffe, der hier funktioniert.

Frage zwischendurch: Kann man sich den Punkt (.) in Regex vorstellen als Σ, also dass eben z.B. .* so viel bedeutet wie Σ*? Und [^abc] ist dann Σ \ {a, b, c}, oder? (Hintergrund: Ich werde demnächst darüber referieren, deshalb mache ich mich gerade ungeheuer schlau auf diesem Gebiet. bereth15 möge es mir bitte verzeihen. xD)

Original von Pan
[...] findet man auch immer eine Sprache von niedrigerem Typ (also, für mich ist Chomsky-3 die niedrgiste Stufe, damit wir da nicht aneinander vorbeireden), die die Wörter einer Sprache von höherem Typ enthält + weitere Wörter.

Und gerade dieses "+ weitere Wörter", so vermute ich, ist zwingend. Lässt sich das irgendwie beweisen?

BTW: Für mich ist ebenfalls Typ 3 die niedrigste Stufe. Wer kam eigentlich auf die Idee, die Nummerierung "verkehrt herum" zu vergeben?

Original von Pan
Die Grammatik {...] ist vom Typ Chomsky-0. Die Regel B → ε ist nicht erweiternd, somit kann die Grammatik nicht vom Typ Chomsky-1 sein und dann schonmal gar nicht Chomsky-2/-3.

(Oder war das eh schon geklärt?)

Ja, das war schon geklärt, und zwar mit dem Ergebnis, dass wir es hierbei mit einer Typ-3-Grammatik(!) zu tun haben.

Original von Pan
Ja, Grammatiken vom Typ Chomsky-2 können immer in die sogenannte Chomsky-Normalform überführt werden. Dadurch werden alle Regeln der Form → ε eliminert, außer evtl. S → ε.

Warum bin ich nicht früher darauf gekommen, da mal nachzulesen? xD

Original von Pan
Es gibt für Chomsky-2 (oder war es Chomsky-1? Ich weis es nicht mehr... ist dir das wichtig? Dann schau ich mal in meinen Unterlagen) 2 verschiedene Definitionen, eine davon lässt auch ε auf der rechten Seite zu. Aber beide Definitionen sind äquivalent, also ja, dass kommt eigentlich nur aus der Bequemlichkeit.

Gut, dann habe ich das also richtig verstanden. Danke. (Du brauchst also nicht nachzuschlagen. *g*)

Wobei ich beim Lesen wieder auf meine ursprüngliche Frage mit der Ausdrucksstärke zurückkomme, denn das hier macht sie wieder für mich interessanter: Alle reden davon, aber keiner sagt, was es letztendlich ist.

Original von Pan
Keine Chance auf BAFÖG und dann evtl. noch nebenher ein bisschen Arbeiten?

Tja, gute Frage eigentlich! In meiner aktuellen Situation gibt es zwei grundlegend verschiedene Möglichkeiten:

1. Direkt nach der Ausbildung studieren. Vorteil: Die Oberstufe ist noch nicht so lange her. Nachteil: Relativ wenig Geld zur Verfügung.
2. Noch ein Jahr arbeiten und dann studieren (Einstieg im Sommersemster ist nicht möglich). Vor- und Nachteile selbsterklärend.

Was also sollte ich tun?

@bereth15: Mit Weckerklingeln am besten sofort aufstehen und irgendetwas machen, aber auf gar keinen Fall hinlegen, besser auch nicht hinsetzen.

Ark

Ach, Mist, ich sollte doch eigentlich für die Technische Informatik Klausur lernen... aber das hier ist viel interessanter

Original von Ark

So, ich hoffe, der hier funktioniert.

Ja, der Link geht!
Also ausgehend von der Verwendung des Begriffs hier und in dem Buch, was Luna verlinkt hat, würde ich sagen, die Ausdrucksstärke beschreibt, wieviel Anforderungen ich an eine Sprache stellen kann.

In Chomsky-3 kann ich keine korrekten Klammerpaare verlangen, in Chomsky-2 schon => Chomsky-2 ist ausdrucksstärker.

Hm, wie würde man das formal definieren?
Die Kuroda-Normalform kenne ich noch nicht und wie meine momentane Auffassung vom Begriff Ausdrucksstärke da reinpassen würde, seh ich auch grade nicht... Mist.

Komische Sache, dass das nirgendswo genauer definiert ist... ich hab nächstes Semester wieder eine Vorlesung zum Thema Theoretische Informatik, sollten wir bis dahin zu keiner Lösung gekommen sein, geh ich in die Sprechstunde vom Prof.

Zu deiner RegEx-Frage: Hm, da kann ich dir leider grade nicht helfen Wie gesagt, ich kenne die Unix-Definition nicht und in unserer Definition kam auch kein . vor. Grade fehlt mir die Zeit, aber wenn ich später/morgen Zeit hab, schau ich mal über die Unix-Definition!

Original von Ark
Und gerade dieses "+ weitere Wörter", so vermute ich, ist zwingend. Lässt sich das irgendwie beweisen?

Ja, genau, dass "+ weitere Wörter" (komisch von mir formuliert ) ist zwingend. Wie kann man das beweisen... hm... gute Frage. Es ist doch an sich klar, dass man mit den Regeln für Produktionen von Chomsky-3 keine Chomsky-2 Sprachen darstellen kann, weil die nötigen Mittel fehlen. Aber mann könnte alle erzwungenen Potenzen durch * usw. ersetzen. Verstehst du, auf was ich raus möchte? Ich glaube, ich drück mich grade konfus aus

Also z.B.

a^n b^n c^n ist vom Typ Chomsky-1.
a^n b* c^n ist vom Typ Chomsky-2, enthält aber das vorherige.
a* b* c* ist vom Typ Chomsky-3, enthält aber das vorherige.

Also das man einfach alle "festen" Einschränkungen durch sukzessiv durch "belieibig viele" ersetzt. Hm... so als Beweisskizze... richtig ausformulieren kann ich das grade nicht und obs überhaupt der richtige Ansatz ist... ?

Evtl. wäre es geschickter hier über Turing-Maschinen, Kellerautomaten und endliche Automaten zu argumentieren. Schwierig.
Vielleicht auch irgendwie über die Pumping Lemmata.

Original von Ark
BTW: Für mich ist ebenfalls Typ 3 die niedrigste Stufe. Wer kam eigentlich auf die Idee, die Nummerierung "verkehrt herum" zu vergeben?

Ich nehm mal an, dass war Noam Chomsky selbst

Original von Ark
Ja, das war schon geklärt, und zwar mit dem Ergebnis, dass wir es hierbei mit einer Typ-3-Grammatik(!) zu tun haben.

Oh, nein! Ganz böser Fehler!
Die Grammatik ist vom Typ Chomsky-0. Aber die erzeugte Sprache lässt sich auch durch eine Grammatik vom Typ Chomsky-3 darstellen. Deshalb ist die Sprache vom Typ Chomsky-3. Aber deine angegebene Grammatik ist trotzdem vom Typ Chomsky-0.

Typ der erzeugten Sprache und Typ der Grammatik sind 2 verschiedene Dinge!

Original von Ark
Was also sollte ich tun?

Ich würde definitiv mal beim BAFöG-Berater vorbeischauen und mit ihm besprechen, inwiefern du Chancen auf BAFöG hast. Auch in Anbetracht der Tatsache, dass du grade eine Ausbildung machst, musst du da mal klären, ob du nach der Ausbildung überhaupt noch Anspruch darauf hast, weil das BAFöG glaube ich nur für die erste Ausbildung gilt
Ich meine, es gibt da auch eine Sonderregelung, wenn das Studium als Weiterbildung der Ausbildung angesehen wird (also die Themen zusammenhängen), aber da bin ich mir nicht sicher.
Das wäre erstmal recht wichtig, würde ich sagen.

Ich kenn deine familiären Zustände nichts und es geht mich eigentlich auch nichts an, aber deine Eltern können oder wollen dir nicht beim Finanzieren helfen? Ganz neutraler Rat: Deine Eltern MÜSSEN dich finanzieren, wenn es deine erste Ausbildung ist, ob sie es wollen, oder nicht (das war ungelogen das erste, was mir mein BAFöG-Berater erzählt hat ^^).

Zur Not würde ich da dann evtl. mal schauen, ob es Sinn macht, die Ausbildung abzubrechen und dann direkt mit dem Studium anzufangen, so dumm es klingt

Du zeigst soviel Interesse an dem Thema... da wäre es fast Verschwendung, wenn du nicht studieren gehen würdest. Ich würd ja sagen, evtl. kommt ein Berufsakademiestudium in Frage (also Dual Studieren + Ausbildung, du verdienst die ganze Zeit Geld)... aber da dürfte das Niveau zu niedrig sein und dich nicht viel weiterbringen, als deine Ausbildung jetzt

Original von Pan
Komische Sache, dass das nirgendswo genauer definiert ist... ich hab nächstes Semester wieder eine Vorlesung zum Thema Theoretische Informatik, sollten wir bis dahin zu keiner Lösung gekommen sein, geh ich in die Sprechstunde vom Prof.

Schreib doch Conny 'ne Mail ... xD (scnr)

Was die Sache mit BAFoeG angeht - also soweit ich das bei einem Kommilitonen mitbekommen habe, funktioniert das wie folgt:
Eltern eigentlich zu gutverdienend, als dass man BAFoeG bekommen wuerde, Ausbildung gemacht, BAFoeG beantragt und zugesagt bekommen.
Weiss nicht, wie da die genauen Hintergruende aussehen, aber ich finde auch, dass es Verschwendung waere, so jemanden wie dich nicht studieren zu lassen, also erkundige dich doch mal und schildere jemandem, der dafuer zustaendig ist und sich auskennt, deine Situation.