Theoretische Informatik Frage zu Formalismus RegExp

[b1zarRe]

Kann mir jemand vielleicht das mittlere erklären? http://www8.pic-upload.de/20.05.11/nm4lgtpayog5.jpg
Unten wird das erklärt, und ich habe die Aufgabe auch bearbeitet... will mich aber nicht darauf verlassen, dass das in der Klausur, die ich bald schreibe auch nochmal so erläutert wird, sondern das dann nur dieser mathematischer Formalismus auftritt...

Was ich bisher daraus lese:
Eingabezeichen = {0, 1}

Sprache L besteht aus den "Wörtern" omega aus der Menge der Eingabezeichen.
Ein Wort omega ist gleich a1, a2... an also eine Folge. n ist hierbei >= 0. Also ist das leere Wort epsilon auch enthalten. Für alle Folgen die >= 1 sind aber kleiner als n gilt:
das das Element der Folge ak und ak+1(also ein Element weiter) aus den Eingabezeichen 10, 01 besteht. Ist dies richtig formuliert?

Sind also folgende, ausschließlich folgende Kombinationen möglich? ->
epsilon e
0
1
10
01
1010
0101
101010
010101
....

Irgendwie verstehe ich den letzten Teil dieser Sprache nicht...
Aus meiner Übung geht hervor,(wenn ich es richtig im kopf habe) dass auch so eine Zahl möglich ist 101 oder 010 etc.
Halt stellenweise abwechselend ne 1 bzw ne 0...

wäre cool, wenn mir das einer erläutern würde, danke!

 

[Marco13]

Was genau ist die Frage? Ich würde auch sagen, dass 010 oder 101 mit drin sind...

 

[b1zarRe]

Die genaue Frage ist, wie man einen solchen Formalismus(link) genau liest?!

 

[Marco13]

Die wörtliche "Übersetzung" ist schon ziemlich genau das, was du schon geschreiben hattest (deswegen war nicht so deutlich, dass gerade DAS die Frage sein könnte 😉 ).

Der Teil
Für alle Folgen die >= 1 sind aber kleiner als n gilt:
das das Element der Folge ak und ak+1(also ein Element weiter) aus den Eingabezeichen 10, 01 besteht.
würde man so wohl nicht schreiben. Eine Folge kann nicht kleiner oder größer sein, als eine Zahl (ich mag so was, da kann man endlich mal gerechtfertigterweise Korinthen kacken 🙂 ). Die präziseste wörtliche Beschreibung des letzten Teils wäre sowas wie "für alle Zahlen k, bei denen 1 kleiner oder gleich k ist, und die kleiner als n sind..." ja, das macht keinen Sinn, deswegen schreibt man das ja als Formel hin. Eine etwas unpräzisere aber verständlichere Beschreibung wäre vielleicht: "Alle zwei-elementigen Teilstrings des Wortes sind entweder 01 oder 10".

 

[RySa]

Regex dazu (also 0 und 1 müssen sich abwechseln):

"((01)+|(10)+)"

??

 

[b1zarRe]

Ich hätte die RegExp so gemacht:

(1+0)* ((10) + (01))*

Wäre aber dennoch cool, wenn jemand nochmal den Formalismus in eignen Worten erklären könnte :/

 

[Ariol]

Ich hätte die RegExp so gemacht:

(1+0)* ((10) + (01))*

Wäre aber dennoch cool, wenn jemand nochmal den Formalismus in eignen Worten erklären könnte :/

So wird das nix: 11001 wäre hier gültig oder auch 11111111

Was wäre denn hiermit?

((1?(01)*0?)|(0?(10)*1?))?

 

[SlaterB]

[c]((1?(01)*)|(0?(10)*))[/c]
den hinteren optionalen Teil kann man sich jeweils sparen,
wenn es auf 1 enden soll, dann reicht irgendwas aus der ersten Hälfte, dort kann man 1, 101, 10101 usw. erzeugen, genauso 01, 0101 usw.,
für 0 die rechte Seite,

oder mit festen Anfang (dann lohnt sich auch das ? ganz außen):
[c]((1(01)*)|(0(10)*))?[/c]

oder wie wärs mit
[c]1?(01)*0?[/c]
das entspricht einer der Hälften, reicht doch auch für alles?

 

[RySa]

Das Regex, das ich vorher angegeben habe funktioniert doch und is wesentlich kürzer, warum dann weiter versuchen ? 😛
Also nochmal ein Beispiel zum copy-pasten:

	public static void main(String[] args) {
		String s = "01101110101110101011101010101110100101110010";
		Pattern pattern = Pattern.compile("((01)+|(10)+)");
		Matcher matcher = pattern.matcher(s);
		
		while(matcher.find()){
			System.out.println(matcher.group());
		}
		
		

	}

EDIT: Funktioniert aber nicht für 1-stellige Fälle, habe ich gerade festgestellt ^^ Dann ist das Regex vom SlaterB die beste und einfachste Lösung 🙂

 

[b1zarRe]

wofür steht das " ? " in regexp? Danke vorrab euch für die Mühe!

 

[SlaterB]

Pattern (Java 2 Platform SE 5.0)
bzw. ein sonstiges Lehrbuch dazu bemühen bitte?!

 

[RySa]

Also mich wundert es immer wieder, wie manche Leute es bevorzugen ~30min für eine Antwort auf so eine triviale Frage zu warten, anstatt es mal zu googeln und es innerhalb 1 Minute zu erfahren...Naja, da ich aber schon antworte:

? - das Zeichen davor (bzw. die Gruppe davor, falls es mit () zusammengefasst wurde) darf nur einmal oder aber gar nicht vorkommen.

 

[b1zarRe]

@RySa

Das liegt daran, weil meine Anfangsfrage vielleicht woanders lag und nicht direkt bei Regulären Ausdrücken und ich, zu dem Zeitpunkt, mich damit auch nicht sooo groß beschäftigt hatte...

Ich wollte nur wissen, wie ihr die Aufgabe in eigene Worte, Prosa sprechen/deuten würdet? Weil ich darauf einfach nicht klar komme.. :/&