Theoretische Informatik Frage zu Formalismus RegExp

b1zarRe

Bekanntes Mitglied
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

Top Contributor
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

Bekanntes Mitglied
Regex dazu (also 0 und 1 müssen sich abwechseln):
Java:
"((01)+|(10)+)"
??
 

b1zarRe

Bekanntes Mitglied
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 :/
 
S

SlaterB

Gast
[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?
 
Zuletzt bearbeitet von einem Moderator:

RySa

Bekanntes Mitglied
Das Regex, das ich vorher angegeben habe funktioniert doch und is wesentlich kürzer, warum dann weiter versuchen ? :p
Also nochmal ein Beispiel zum copy-pasten:
Java:
	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 :)
 
Zuletzt bearbeitet:

RySa

Bekanntes Mitglied
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

Bekanntes Mitglied
@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.. :/&
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Airwolf89 Theoretische Frage - In Java Java-Programme schreiben Softwareentwicklung 5
L informatik beleg? Softwareentwicklung 12
C SOLID Single Responsibility Priciple Frage Softwareentwicklung 2
K Frage OOP Softwareentwicklung 8
dgtKotlin Frage zu Kotlin source code Softwareentwicklung 5
A Frage zu testdriven developement Softwareentwicklung 1
H Regex Frage Softwareentwicklung 2
D Frage Schichtenarchitektur Softwareentwicklung 3
T Frage bezüglich MVC Softwareentwicklung 1
Shams Frage wegen guava-Eventbus. Softwareentwicklung 0
B Frage zu Schnittstellen (lose Kopplung) Softwareentwicklung 5
H Frage zur Stanford NLP-API Softwareentwicklung 2
E Frage zu Dekorator-Pattern Softwareentwicklung 2
O Frage zu Regulärer Ausdruck Softwareentwicklung 3
H WEKA - Frage zu Methode in Evaluation Softwareentwicklung 2
S Frage zu Zusicherungen: Softwareentwicklung 12
D Frage zu String Algorithmen / String Metric Softwareentwicklung 7
D Frage zur Objektorientierung mit Interfaces Softwareentwicklung 9
Wepster LGPL, MPL Frage Softwareentwicklung 3
D Frage zur Benutzeroberflächenprogrammierung Softwareentwicklung 8
D Frage zu Klassendiagramm und Konstruktor (UML) Softwareentwicklung 3
M [OOP] Frage zu Methode-Namen / Funktionsweise Softwareentwicklung 9
P Frage zu Processing Softwareentwicklung 9
S Regex Frage Softwareentwicklung 4
D Frage zu meiner Vorgehensweise in einem Projekt Softwareentwicklung 5
A Frage zu GPL Softwareentwicklung 3
K Frage zu UML Aktivitätsdiagramm Softwareentwicklung 3
J Frage zu Lizenzrechten Softwareentwicklung 5
B bash frage Softwareentwicklung 6
F allgemeine exe frage Softwareentwicklung 10
G Frage zur LGPL? Softwareentwicklung 5
0x7F800000 "Wozu ist denn CSS / CSS2 gut" Dumme Frage? Softwareentwicklung 9
G Frage zur UML Softwareentwicklung 2
B Ajax Frage Softwareentwicklung 2
J Frage zu Relation Softwareentwicklung 2
W Frage zu a)Innere Klassen und b)OO Design Softwareentwicklung 13
G MVC Frage Softwareentwicklung 4
P Frage zu Prolog! Softwareentwicklung 7
E Frage zu Excel und Filtern Softwareentwicklung 4
Y OpenGL/C Frage - externe Funktionen Softwareentwicklung 5
G C# Frage Softwareentwicklung 12
T SQL, Feld mehrmals abfragen, IN Frage Softwareentwicklung 3
C Grundsätzliche Frage zur OOP bzw. zum MVC Softwareentwicklung 5
RaoulDuke Frage zu Datenmodel / Zugriff Softwareentwicklung 5
J Frage zu C Softwareentwicklung 2
H Frage ueber Prototype Pattern? Softwareentwicklung 2
L Noch 'ne Perl-Frage. Kehre dann auch reumütig zu Java zurück Softwareentwicklung 10
S Design-Frage: Wie viele Fassaden? Softwareentwicklung 4
J Frage zu MVC, Swing, Gui Softwareentwicklung 3
L Frage zu Beziehungen zwischen Klassen und UML Softwareentwicklung 10
T Frage zu Mysql Softwareentwicklung 3
C Mysql-Frage(Problem mit nicht durchgeführten Zugriff) Softwareentwicklung 5

Ähnliche Java Themen

Neue Themen


Oben