Formale Sprache

[b1zarRe]

Hi,

Ist der Ausdruck (011*)+0 äquivalent zu 011*+0 ?
Sprich: Lässt sich beispielsweise das Wort 0 aus beiden ableiten? Ich würde denken, dass es
beim ersten kein Problem ist und beim zweiten (ohne Klammern) nur Wörter der Form:
0 konkateniert mit 1 konkateniert mit beliebig vielen 1 ODER mit einer 0. Aber nicht nur eine 0.

Stimmt dies? Habe 2 Programme durchlaufen lassen... und beide geben mir eine andere Antwort auf die Frage...

 

[SlaterB]

nicht äquivalent aber du liegst mit deinen Erläuterungen auch falsch, 0 geht in beiden nicht,
Tipp: die Klammern sind für das + interessant, + ist auch ein Zeichen wie *, kein ODER,
das * bezieht sich in beiden Fällen nur auf eine 1, ist von der Klammer hier komplett unabhängig

was hast du denn konkret an Programmen, zeige diese doch?

 

[Tomate_Salat]

die Klammer [c]( )[/c] im Regex sind gruppierungen. Doch bei der ersten Anweisung wäre sowas gültig:
01010101010
oder
011011101010

bei der 2ten nicht. Da es sich hier um einen Possessive Ausdruck handelt (*+). Wie sich der verhält weiß ich nicht mehr, aber die obigen Beispiele sollte er nicht akzeptieren. Bei diesem darf zwischen 01 und 0 nur eine beliebige anzahl an 1er stehen.

edit kleine Erklärung:
[c](011*)+0 [/c] => der Ausdruck muss mit 01 beginnen. Danach kann eine beliebige Anzahl von 1en folgen. Dieser erste Teil muss mind. einmal vorkommen. Das letzte Zeichen ist 0

[c]011*+0[/c] => Ähnlich wie oben: der Ausdruck muss mit 01 beginnen. Danach kann eine beliebige Anzahl von 1en folgen. Dieser Teil des Ausdrucks darf sich aber nicht wiederholen und das letzte Zeichen muss auch hier eine 0 sein.

 

[b1zarRe]

Also jetzt bringt ihr gleich meine Welt zum Einsturz....

Zunächst einmal: ( Ich gehe davon aus, dass + sowie | das gleiche bedeuten... so haben wir es zumindest gelernt)
(ab*) + b -> möglich Wörter: b, a, abb,abbb,abbbb,abbbbb....

ab*+b -> mögliche Wörter: ab,abb,abbb,abbbb,abbbbb....

Siehe Fotos vom Programm:
http://www8.pic-upload.de/08.08.11/v5j898uktrme.jpg
http://www8.pic-upload.de/08.08.11/ozgldy9xvzu.jpg

"Doch bei der ersten Anweisung wäre sowas gültig:
01010101010
oder
011011101010"

Wie kommst du dadrauf? Beide Programme, sagen auch dazu nein...

"nicht äquivalent aber du liegst mit deinen Erläuterungen auch falsch, 0 geht in beiden nicht,"
bin mir zu 99prozent sicher das es beim ersten Ausdruck geht... Erklär bitte warum nicht?!

 

[SlaterB]

> dass + sowie | das gleiche bedeuten
nein, klingt unnett aber ist wahr: wie wärs damit, erstmal zu lernen was es in Java bedeutet?
Pattern (Java 2 Platform SE 5.0)
oder ein beliebiges Lehrbuch mit seitenweisen Erklärungen und ausführlichen Beispielen

falls es dir überhaupt um Java geht, deine beiden 'Programme' sind auch eher unbekannten Ursprungs,
was die aussagen muss für Java keine Bedeutung haben

> Erklär bitte warum nicht?!

ungern erkläre ich etwas was du zunächst nachlesen und aus den natürlichen Regeln herleiten kannst,
könnte deine Hausaufgabe sein usw. bzw. ist komplett falsche Arbeitsrichtung

lerne RegEx

--------

wenn es nicht um Java geht dann definiere/ verlinke die Bedeutung jedes Zeichens, Klammerregeln usw.

 

[b1zarRe]

ich meine in etwa sowas: Blitzkurs Theoretische Informatik/ reguläre Sprachen ? Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher
(Unter "Tag2")

Halt Reguläre Ausdrücke der Theoretischen Informatik... nicht direkt Java... - sorry, dachte nicht das es da einen Unterschied gibt?! oO

Btw.: Programm in Link eins ist von irgendeiner UNI Seite, Programm2 ist aus dem Buch Socher - Theoretische Informatik

 

[SlaterB]

ein + als | ist auf der Seite übrigens nicht zusehen,
aber nungut, dann stimme ich mit dir überein dass die zweite Sprache keine 0 erzeugen sollte,
tja, jetzt nehme ich an dass das Programm 2 dir doch 'ja, 0 geht' antwortet?

schwer zu sagen warum, vielleicht zählt 011 ohne Leerzeichen dazwischen als ein Block wie mit Klammer?
ich schlage vor du testest mit dem Programm weiter bis du (und ich) es verstehst,
fange mit einfacheren Beispielen an, z.B.
0+1

aktzeptiert das 0?
1?
01?
000001?

andere Beispiele bitte selber ausdenken

 

[b1zarRe]

Ich gebe mal einen kurzen Crashkurs wie wir das gelernt haben (und da bin ich mir schon sehr sicher - Leider darf ich das Skript oder Buchunterlagen ja nicht online stellen...Vielleicht finde ich ja noch ein passendes Beispiel im Netz) :

+ oder | = ODER
.(also der Punkt mittig) = Konkatenation
* = Keinmal, einmal oder beliebig oft

Beispiele:
0 + 1 -> Akzeptiert: 0 oder 1. Keine 00 oder 01 oder 1110101 oder sonstwas
(0+1)* -> Akzeptiert: leeres Wort epsilon, 0,1,00,000,0000...,11,111,1111....,010101011,10101010101,1010,010
11*0 -> Akzeptiert: 10,110,1110,11110,1111110,..
(0+1)*+0 Akzeptiert: 0,1,10,01,101,00000,1010101 etc
0*+1 Akzeptiert: leeres Wort epsilon,0,00,000,0000....,1
(1+0*) Akzeptiert: 1,leeresWort,0,00,000,0000...

Die Frage ist nun, ob 11*+0 beispielsweise <=> zu (11*)+0 ist.
Zweiteres Akzeptiert: 0,1,11,111,1111,11111...
Ersteres Akzeptiert hingegen nun entweder das gleiche wie der zweite oder(weil keine Klammerung) nur: 1 konkateniert mit beliebig vielen 1 ODER einer 0 sprich:
1,11,111,11111,1111111,111....,10 <- Wenn dies der Fall ist, dann akzeptiert er zb. NICHT eine einzige 0 so wie es beim zweiteren möglich ist!


-> Also wie gesagt, mit dem "zweiterem" bin ich mir sehr sicher.. beim ersteren bin ich grade verwirrt.. warum das Programm das nicht so sieht wie ich.

 

[Tomate_Salat]

habe ich oben schon erklärt und slaterB hat dir schon gesagt: zwischen + und | liegt ein rießen Unterschied. Lies doch einfach mal die Api zu dem ganzen.

Ok ich versuchs nochmal zu erkären, was du verwendest:

* = vorkommen: 0..n
+ = vorkommen: 1..n
()= gruppierung
()+= die gruppierung kann 1..n mal vorkommen

ausführlicher stehts in der Api und ich denke nicht, dass wir die hier abschreiben müssen ;-)

 

[b1zarRe]

.... Ich habe doch schon gesagt, dass es nicht direkt auf Java bezogen ist...

und ich denke nicht, dass ich das zweimal schreiben muss

 

[Tomate_Salat]

Regex muss nicht direkt was mit java zu tun haben. Es gibt zwar verschiedene versionen von Regex, aber im Kern, sollten sie sich alle ähneln.

Und dazu kommt: wir sind in einem Java-Forum. Insofern sollte er etwas mit dem Regex gemein haben, den wir kennen. Ansonsten sind wir einfach die falsche Anlaufstelle für dein Problem.

 

[b1zarRe]

naja... deswegen steht es auch im Unterforum Softwareentwicklung und da ich stark davon ausgehe, dass hier auch Leute kreisen, die Informatik studieren, studiert haben, oder studieren werden, ging ich davon auch aus, dass das nicht der falsche Ort ist hier zu fragen.

Kenne mich leider nicht super mit RegExp direkt in Java aus, aber ich weiß zb das die Klasse String eine matches Methode beinhaltet, wo man zb Reguläre Ausdrücke wie ich sie meine testen kann:

        String einNeuerString = "1";
        System.out.println("Neue RegExp: " + einNeuerString.matches("011*|1"));

Deswegen alleine schon, und der Grund oben veranlassten mich das hier zu erfragen... - und denke nicht, dass es so verkehrt ist, oder?!

 

[Marcinek]

Also + und | haben die gleiche bedeutung in der formalen Sprache, wie in Java RegEx.

 

[Tomate_Salat]

Oben steht sogar 2x ein link zur Patternklasse, aber egal. Ja dann nimm unsere Aussagen an: + ist nicht das gleiche wie |. Das sagen hier mittlerweile 3 Leute.

 

[b1zarRe]

http://www8.pic-upload.de/09.08.11/vzlliqcn75.jpg

Und zudem: warum sagen mir dann die 2 Programme sowie in Java das gleiche....?

Sprich: (001*) | 1 ist in dem Sinne die gleiche SPrache wie 001* | 1

 

[Marcinek]

Hast du auch eine Quelle für dein Bild? ;D

Meiner Meinung nach ist es die gleiche Sprache. Jedenfalls sehe ich kein Wort, dass von der einen Sprache mehr akzeptiert wird, als von der anderen.

 

[SlaterB]

"011*|1" matcht in der Tat "1" in Java, das hätte ich geraten wohl anders beantwortet,
so würde ich dann annehmen dass | alles links davon als einen Block ansieht, bis zu Klammern

ergibt mehr und mehr Sinn, man möchte ja z.B. "Herr M(ü|ue)ller" schreiben, nicht "Herr Mü|(ue)ller",
ok ginge auch..


ist letztlich doch nicht so spannend oder? man braucht schon eine genaue Definition der Sprache, ob mit + in der Theorie oder mit | in Java,
entweder es bezieht sich auf möglichst wenig davor, wie * oder auf möglichst viel wie | anscheinend,

irgendwo wirds stehen, ansonsten ausprobieren bis es passt,
idealerweise immer klammern, wie bei Und-Oder-Konstruktoren oder normalen mathematischen Konstrukten mit +, -, *, / auch

nach derzeitigen Stand ist für mich dann in der Ursprungsfrage (011*)+0 in der Tat äquivalent zu 011*+0,
darüber zu diskutieren ist aber recht müßig ohne exakte Regeln

 

[b1zarRe]

Gut, denke ich mittlerweile auch und danke für die Hilfe hier.. auch wenn einige nicht gerade nett und zuvorkommend waren ^^

und @TomateSalate
Wie Du in deinem ersten Post auf die Beispiele gekommen bist bleibt mir weiter ein Rätstel?! Vielleicht ist in Java der Begriff + bzw | anders als in der theoretischen Informatik... nur dann musst du auch offen gegenüber "neuem" sein und nicht direkt alles ovn mir als falsch deklarieren

 

[Tomate_Salat]

Matcher matcher=Pattern.compile("011*+0").matcher("011011101010");

System.out.println(matcher.matches()); // false

Matcher matcher2=Pattern.compile("(011*)+0").matcher("011011101010"); 

System.out.println(matcher2.matches()); // true

so: nachgeprüft und meine Aussagen stimmen (laut Java).
Und nochmal: ich kann dir nur sagen, was ich von der Java-Seite aus weiß. Und das deckt sich ziemlich gut mit z.B. der version von JS, PHP oder Perl. Marcinec bestätigt, dass + und | in beiden Sprachen das gleiche ist und auf (Java)Regex-Seite ist dort einfach ein Unterschied. Nur weil du es so gerne hättest, ist es nicht so ;-). Mein obiges Beispiel kannst du gerne selbst mal in Java ausprobieren.

Wie Du in deinem ersten Post auf die Beispiele gekommen bist bleibt mir weiter ein Rätstel?!

[c]011*+0[/c]
Der interessante Teil ist hier *+, davor steht die 1. Vereinfacht sagen wir jz einfach mal: die 1 darf beliebig oft vorkommen. Somit sind die festen Angaben: es muss mit 01 beginnen und mit 0 enden. Dazwischen darf die 1 n-mal vorkommen.

[c](011*)+0[/c]
Die Klammern bedeuten eine Gruppierung. D.h: 011* ist jz eine Einheit (Gruppe). Die letzte 1 hat einen Stern [c]*[/c]. Sie darf also beliebig oft vorkommen (also 0..n mal). Für diese Gruppe gilt also: Es muss mind. 01 vorkommen gefolgt von einer beliebigen Menge an einsern. Hinter der Gruppe steht das Zeichen: [c]+[/c]. Das bedeutet: Diese Gruppe muss mind. einmal vorkommen, darf sich aber wiederholen(also: 1..n mal). Die 0 zum Schluss setzt die Bedingung, dass das ganze mit 0 enden muss. Mein Beispiel für ein Match war:
[c]011011101010[/c]
wenn ich jz die Klammern für die Gruppen setze, wird es vllt deutlich.
[c](011)(0111)(01)(01)0[/c]
Jeder Wert in der Klammer, passt auf deine Gruppierung ([c]011*[/c]). Die Gruppierung darf sich wiederholen, was sie hier auch tut. Und das ganze endet mit 0. Also ist es ein Match.

 

[xehpuk]

Soweit ich es noch weiß, haben wir in der Vorlesung zur Automatentheorie ebenfalls '+' und '|' äquivalent behandelt. Nur weiß ich gerade nicht, ob wir einen Ersatz für "x+" hatten oder dann einfach "xx*" genommen haben. Irgendwie habe ich in Erinnerung, dass wir da ein hochgestelltes '+' verwendet haben. :reflect:

 

[Tomate_Salat]

Wenn es um soetwas geht. Dann sollte es wirklich äquivalent sein und hat mit den Regex dich ich kenne, nicht viel gemein.

 

[XHelp]

War bis eben fest der Überzeugung, dass

+

ein

+

ist und

|

eben

|

. Allerdings gerade von einem Mitarbeiter des Theoretische Informatik-Lehrstuhls aufklären lassen:
Heutzutage sollte im praktischen bereich +=+ |=| gelten... aber so war es nicht immer und in dem theoretischem Teil findet man auch jetzt noch häufig +=|, wobei wenn es das + als Exponent steht ist die Bedeutung klar.
Die +=| Sache ist wohl auf die uralt-Unix-Zeit zurückzuführen, wo das Pipe-Symbol ja eine andere Bedeutung hat.

Man sollte also zwischen regulären Sprachen in der Theorie und Praxis unterscheiden

 

[fastjack]

Vorsicht: die regulären Ausdrücke, die der TO hier meint, sind so gut wie gar nicht mit den "regular expressions" aus Java/PHP/Perl zu vergleichen, da diese einfach mal nicht regulär im Sinne von regulären Sprachen sind.

+ und | sind äquivalent und bedeuten ODER, das deutet schon mal auf einen NEA hin

Um zu zeigen, daß die beiden Ausdrücke äquivalent sind, kannst Du z.B. einen NEA mit Epsilonübergängen verwenden. Danach würde ich einen induktiven Beweis über die Operation Konkatenation, Einhüllung usw. machen.

Zur Hilfe:

* zu jedem NEA mit Epsilon-Übergängen gibt es einen äquivalenten NEA ohne Epsilon-Übergänge (bereits beweisen)
* zu jedem NEA gibt es einen äquivalenten DEA mit mindestens 2 hoch X Zuständen (bereits beweisen)

Fängt Deine Aufgabe mit "Zeigen sie, das die regulären Ausdrücke A und B äquivalent sind...", weist Du schon das sie es sind und sollst es zeigen (Beweis). Steht dort z.B. "Prüfen sie ... sind die Asudrücke äquivalent?" hast Du gute Chancen, das sie es nicht sind. In diesem Fall kannst Du mit Glück oder Verstand eine Eingabe finden, die von dem einen akzeptiert wird und von dem anderen nicht, dann brauchst Du keinen Beweis.

 

[b1zarRe]

@fastjack

Genau solche regulären Ausdrücke meine ich... in Bezug zu Theoretische Informatk, Automatentheorie, Grammatiken & NEA & DEA & epsilon Automaten etc.

Wusste nicht, dass anscheinend der Unterscheid zu Java RegExp so gravierend ist?! Hatten die Sachen auch überwiegend in der Theorie angesprochen und nie wurde erwähnt, dass es in der Praxis noch viel mehr Bedeutungen haben könnte für ein Zeichen wie + oder | .

Naja, jedenfalls bin ich nun sehr sicher, dass (011*)+0 sowie 011*+0 genau die gleiche Sprache L liefern. Wenn ich zb eine Sprache haben wollen würde, wie Tomate_Salat beschrieben hat, also
01 gefolgt von beliebig vielen 1 und am ende eine 0 müsste ich folgendes schreiben:
011*0 -> (Punkte mittig als Konkatenationszeichen kann man sich sparen) Diese SPrache würde jetzt zb nichtmehr das Wort "0" erkennen, sondern nurnoch Wörter
wie: 010,0110,01110,011110,.... Kann sein, dass Tomate_Salat da recht hat, und das mit Java RegExp anders aussieht... aber so haben wir halt Reguläre Ausdrücke definiert und gelernt.

 

[Illuvatar]

Gut, dann hat sich ja alles geklärt. Ich wollte nur noch anmerken:

Wusste nicht, dass anscheinend der Unterscheid zu Java RegExp so gravierend ist?!

Das ist keine Eigenheit von Java. Daher stammte vermutlich auch die Verwirrung hier
Und auch wenn es für das, was du gerade konkret lernst, nichts bringt, ist es doch gut zu wissen denke ich: Unter regular expression versteht man normalerweise (in der Praxis) etwas anderes, als was du hier meintest. Und zwar nicht nur in Java, sondern in so gut wie jeder Sprache, und es ist immer das Gleiche gemeint:
Regular expression - Wikipedia, the free encyclopedia