Denksport - ein kleines Informatik-Rätsel

[Bernhard Peissl]

Hi Leute!

Ich will hier mal einen Versuch starten, und schaun wie's ankommt ;-)

Es ist zwar OFF-TOPIC, und ich weiss auch gar nicht, ob sowas im Forum erlaubt ist, aber es hat ja doch irgendwie Bezug zum Thema PERL, und es ist vielleich ganz gut geeignet, um die Stimmung ein bischen zu heben, aber auf alle Fälle einen kleinen Gute-Nacht-Gedanken wert!

Werd ja sehen ob ich einen Anschiss kassiere, aber einen Versuch ist's Wert

Ich lerne gerade mit meinen Studienkollegen für eine Informatikprüfung (Theoretische Informatik - Automaten, Turingmaschinen), und dabei sind wir über eine ziemlich hundsteufelgemeine Frage gestolpert, die keiner von uns lösen kann, und sich hervorragend für ein kleines Rätsel eignet!

Wir können in Worten beschreiben ;-) wie die gefragte RegExpr. aussehen soll, aber nicht hinschreiben!

Also hier die Aufgabe:

Stellt euch vor ihr habt eine Sprache die sich aus nur drei Buchstaben zusammensetzt! Es geht also um eine Sprache aus dem Alphabet {a,b,c}*, WOBEI vor jedem 'c' zumindest ein 'a' oder 'b' stehen MUSS. Ansonsten Syntaxfehler ;-) Anders gesagt: Es kann kein c vorkommen, vor dem nicht entweder mindestens ein a oder b steht!

a,b oder c können dabei * ( >=0 ) mal vorkommen. Die Worte, die man mit dieser Sprache bilden kann, sollen durch einen regulären Ausdruck beschrieben werden.

Das heisst der Ausdruck soll auf alle diese Möglichkeiten matchen, quasi die Syntax der Sprache checken. Also ein Wort einlesen und prüfen ob es überhaupt zum "Sprachschatz" gehört. Wie wenn ihr ein Programm schreibt, das prüfen soll, ob der Ausdruck "$var=3;" ein zulässiger Ausdruck in der Sprache "PERL" - mit dem Alphabet {$,3,v,a,r,=,;} - ist!

Mögliche Worte(Zeichenketten) sind z.b: aaa, abcabcc, ac, bcbbbb, ba, ... Keine Worte aus dieser Sprache wären: cabac, c, abccb

Ein Ausdruck der die Sprache z.B. nicht richtig bestimmt, wäre /a*b*c+/ da 'c' nicht zwingend vorkommen muss, ausserdem könnte nach c noch ein anderer Buchstabe (a oder b) kommen. /(a*b*c+)*/ geht auch nicht! Es kann dann zwar nacher nachmal ein a oder ein b oder ein c kommen, allerdings ist mit dem 'c+' festelegt, dass ein 'c' im Ausdruck sein muss - was im Wiederspruch zur Definition steht, da c auch _nicht_ vorkommen kann ;-)

Ihr seht, eine haarige Sache also, und gar nicht _soooo_ leicht.

Für die Informatiker unter euch:
Ein Beschreibung der Sprache, die folgender endlicher Automat erzeugt:

• Zustände {qo,q1,q2}
• Alphabet {a,b,c}
• Anfangs und Endzustand ist {q0}
• Übergangsfunktion: (q0,a) -> {qo,q2}
                       (q0,b) -> {q0,q1}
                       (q1,c) -> {q0}
                       (q2,b) -> {q1}
                       (q2,c) -> {q0}

;-)

Es ist wirklich nur zum Spass, ein kleiner Test, wie gut eure RegExpr-Künste wirklich sind ;-) Ich weiss auch gar nicht, ob ihr euch da reindenken könnt oder überhaupt verstanden habt was ich euch sagen will!

Um möglichen Fragen zuvorzukommen: Das ist keine besonders kreativ formulierte Ausrede um nicht im perldoc nachsclagen zu müssen ;-) es soll sich jedenfalls keiner gezwungen fühlen, diese Frage zu beantworten, daher auch keine perldoc-links bitte ;-) und keine Beschimpfungen denn wer's blöd findet braucht ja nix zu antworten!

Ich hoffe ich habe die Aufgabe deutlich formulieren können!

Viel Spass beim Grübeln,
Bernhard

[AlexBausW]

Hallo Bernhard,

Mögliche Worte(Zeichenketten) sind z.b: aaa, abcabcc, ac, bcbbbb, ba, ... Keine Worte aus dieser Sprache wären: cabac, c, abccb

^....wäre ja eigentlich auch ungueltig, oder?

Also darf ac,bc,a und b jeweils beliebig oft vorkommen. Wie dazu die RegEx ausschaut sollte eigentlich klar sein ;-) (siehe auch perldoc perlre *vbg* SCNR)

$var =~ /^(acbcab)+$/; sollte imho Deinen Anforderungen genügen *hoffemichnichtzublamieren*

Einfache Tests haben soweit die Richtigkeit bestätigt, aber ich hab noch nicht _alle_ möglichen richtigen und falschen Kombinationen durch ;-)

Um möglichen Fragen zuvorzukommen: Das ist keine besonders kreativ formulierte Ausrede um nicht im perldoc nachsclagen zu müssen ;-) es soll sich jedenfalls keiner gezwungen fühlen, diese Frage zu beantworten, daher auch keine perldoc-links bitte ;-) und keine Beschimpfungen denn wer's blöd findet braucht ja nix zu antworten!

Und wenn es nebenbei Deine Hausaufgaben löst, solls nicht so schlimm sein, den wenn meine Lösung stimmt, saß ich wenigstens nicht zu lange dran, um darüber verärgert zu sein. :-)

Gruß AlexBausW

Please visit my SELFvisitingcard @ http://www.atomic-eggs.com/selfspezial/daten/150.html

[Bernhard Peissl]

Hi Alex!

Ich seh schon, ich werd mich noch voll blamieren hier ;-)

Mögliche Worte(Zeichenketten) sind z.b: aaa, abcabcc, ac, bcbbbb, ba, ... Keine Worte aus dieser Sprache wären: cabac, c, abccb
                                                      ^....wäre ja eigentlich auch ungueltig, oder?

UUuuuppssi! stimmt, zu schnell getippt!

Also darf ac,bc,a und b jeweils beliebig oft vorkommen. Wie dazu die RegEx ausschaut sollte eigentlich klar sein ;-) (siehe auch perldoc perlre *vbg* SCNR)

$var =~ /^(acbcab)+$/; sollte imho Deinen Anforderungen genügen

Alle Möglichkeiten aufzählen hätte ich auch gekonnt ;-)

Stell dir mal vor du hättest mehr Buchstaben, oder mehrere Kominationen die nicht vorkommen dürfen, dann wirds mit "das darf vorkommen, oder das darf vorkommen, oder das darf vor..." ein bischen kompliziert ;-)

*hoffemichnichtzublamieren*

ganz meinerseits, spaziere nämlich "on the edge" - wie du vielleicht weisst bin ich ja nicht der grösste Freund/Kenner von RegExpr.

Ohne Dacherl und Perl-Statements (^, $)!
Es sollte Allgemein gültig sein :-(

Du hast nur die folgenden Mengen-Operatoren zur Verfügung:
*  >=0
+  >0
() Gruppierung

Keine $-Tricks bitte sehr ;-)

Und wenn es nebenbei Deine Hausaufgaben löst, solls nicht so schlimm sein, den wenn meine Lösung stimmt, saß ich wenigstens nicht zu lange dran, um darüber verärgert zu sein. :-)

Es ist keine Hausaufgabe, wir sind einfach nur beim Üben drübergestolpert!

liebe grüsse
Bernhard

[Bernhard Peissl]

Hi nochmal!

Und wenn es nebenbei Deine Hausaufgaben löst, solls nicht so schlimm sein, den wenn meine Lösung stimmt, saß ich wenigstens nicht zu lange dran, um darüber verärgert zu sein. :-)

Ausserdem kenn ich die Lösung selbst nicht ;-) *g*

Jedenfalls steht in der Angabe nix von Perl, muss also auch so (mit logischen Ausdrücken) zu lösen sein! Das hab ich nur als Entschuldigung genommen, damit ich keinen Flame abkrieg ;-)

liebe grüsse
Bernhard

[n.d. parker]

hi bernhard

Ohne Dacherl und Perl-Statements (^, $)!
Es sollte Allgemein gültig sein :-(

also:
^ = String/Zeilen- Anfang
$ = String/Zeilen-Ende

es ist nix perlspezifisches

und eine programmiersprache _nur_ mit regexes zu parsen ist technisch _unmoeglich_ (das regexes iterativ arbeiten, also verschachtelungen nicht koennen, nur bist zu einer festgelegten ebene)

cua

n.d.p.

[Bernhard Peissl]

Hi!

und eine programmiersprache _nur_ mit regexes zu parsen ist technisch _unmoeglich_ (das regexes iterativ arbeiten, also verschachtelungen nicht koennen, nur bist zu einer festgelegten ebene)

keine Sorge, ich will keine Programmiersprache erfinden, es geht darum, dass man theoretisch jede Sprache mit einem Regulären Ausdruck beschreiben kann!

Zum Beispiel kann man die Menge der erlaubten Bezeichner (Variablen) durch den Ausdruck /b(bz)*/ beschreiben, wenn man b als Menge aller Buchstaben [a..z][A..Z] und z als Menge aller Ziffern [0..9] definiert! Es kann nie eine Zahl an erster Stelle sein! Ist doch cool oder?

Aber vielleicht war das Rätsel ja doch ne blöde Idee! Ohne die Theorie im Hintergrund tut ihr euch natürlich schon schwer! Ihr denkt da logischerweise an ein Problem in einer Programmiersprache :-(

Aber was solls,
probieren wollt ich es einfach mal,
und vielleicht kommt ja noch was!

liebe Grüsse
Bernhard

[F.Heyer]

Die Lösung lautet:

( ((a+)(b+)) (a*) (b*) (()(c)) )+

Wenn ich mich nicht täusche deckt dieser Ausdruck
jedes bel. Wort der Sprache ab. Ich habe POSIX genommen
weil ich das besser kann als die Perl Variante.
Sollte aber leicht übertragbar sein.

Gespannt ob jemand eine leichtere findet. (ca. 2min)

Nicht weiter lesen, wenn man es selbst erkennen will:

Der erste Block ((a+)(b+)) erzwingt das am Anfang _ein_ a oder b steht, danach können soviele a oder b kommen wie will * erlaubt auch keinmal! dann darf _nichts_ oder _ein_ c kommen, der ganze Ausdruck ist geklammert, damit er mit dem + einmal oder beliebig oft auftreten kann. Dieser Ausdruck matched vom kleinsten Wort der Sprache bis zum ganzen Programm alles, was der vorgegebenen Syntax entspricht.

War das eine eher schwere oder eine leichtere Aufgabe?

Die schönste an die ich mich erinnern kann:

Man schreibe ein Programm das seinen _eigenen_ Quellcode auf den Bildschirm schreibt, _ohne_ dabei auf den Quellcode oder eine andere Datei zuzugreifen.

Ein Spass zum Abend:

Das Loch im Heise Ticker war leichter zu finden.

http://www.juramail.de/forum/index.cgi?read=2269

[Bernhard Peissl]

Hi!

Der erste Block ((a+)(b+)) erzwingt das am Anfang _ein_ a oder b steht, danach können soviele a oder b kommen wie will * erlaubt auch keinmal! dann darf _nichts_ oder _ein_ c kommen, der ganze Ausdruck ist geklammert, damit er mit dem + einmal oder beliebig oft auftreten kann. Dieser Ausdruck matched vom kleinsten Wort der Sprache bis zum ganzen Programm alles, was der vorgegebenen Syntax entspricht.

ja, wenn man '()' durchgehen lässt ;-)
was unser Prof sicher nicht tun würde :-(

liebe Grüsse
Bernhard

[F.Heyer]

Hi!

ja, wenn man '()' durchgehen lässt ;-)
was unser Prof sicher nicht tun würde :-(

Ein leerer Asudruck ist aber in eurer Syntax und auch in POSIX regex einwandfrei erlaubt (selbst der eigenwillige Matcher von Perl macht das richtig), aber wie es sei mit copy and paste einfach alles zweimal hinschreiben, einmal mit und einmal ohne c, dann geht es auch ohne leerem Ausdruck:

((((a+)(b+))(a*)(b*)(c))(((a+)(b+))(a*)(b*)))+

Das ist aber die Lösung für lamer!
Es ist unübersichtlicher, langsamer und fehlerträchtiger.
Ein regulärer Ausdruck sollte immer minimal sein,
so hat man es mir zumindest in der stoneage Zeit beigebracht.

cu
F.Heyer

[Bernhard Peissl]

Hi!

Ein leerer Asudruck ist aber in eurer Syntax und auch in POSIX regex einwandfrei erlaubt (selbst der eigenwillige Matcher von Perl macht das richtig), aber wie es sei mit copy and paste einfach alles zweimal hinschreiben, einmal mit und einmal ohne c, dann geht es auch ohne leerem Ausdruck:

((((a+)(b+))(a*)(b*)(c))(((a+)(b+))(a*)(b*)))+

jaja, ist ja schon gut, ich glaubs ja ;-) *g*
Sagen wir mal für die Lösung in Posix bekommst du den ersten Preis :-)

Es ist unübersichtlicher, langsamer und fehlerträchtiger.
Ein regulärer Ausdruck sollte immer minimal sein,
so hat man es mir zumindest in der stoneage Zeit beigebracht.

Stimmt, daher schau'ma mal ob's jemand in nem kürzerem zusammenkriegt ;-)

Aber es sollte ja bloss ein wenig Spass bringen,
ich hoffe den hattest du :-)

liebe Grüsse
Bernhard

[F.Heyer]

»»

Aber es sollte ja bloss ein wenig Spass bringen,
ich hoffe den hattest du :-)

liebe Grüsse
Bernhard

Aber ja, sonst hätte ich sicher nicht mit gemacht.

Ich hörte einmal das es da sogar so eine Art Sport gibt,
spassige reguläre Ausdrücke also Formen und man soll dann heraus bekommen was diese Ausdrücke machen.

Leider weiss ich nicht wo ich das geshen hatte.

cu
F.Heyer

[Bernhard Peissl]

Hi!

Ich hörte einmal das es da sogar so eine Art Sport gibt,
spassige reguläre Ausdrücke also Formen und man soll dann heraus bekommen was diese Ausdrücke machen.

*g*

Unser Informatik-Prof hat mal was von einem Wettbewerb erzählt, wo jedes Jahr die am kompliziertesten verschachtelten, am wirrsten, aber korrekt programmierten C++ Programme prämiert werden, das wär doch mal ein Spass :-)

Vielleicht steht das ja cuh irgendwo im Netz!

liebe Grüsse
Bernhard

[n.d. parker]

hi ho

Ich hörte einmal das es da sogar so eine Art Sport gibt,

es gibt auch noch sowas wie den "Obfuscated Perl Contest", der Wettbewerb fuer die unleserlichsten Perl-Programme (der allerdings nach einem solchen C-Wetterbewerb entstanden ist.. :-)

Beispiel (quelle: Jeffrey Friedl: Regulaere Ausdruecke, Autor des miniprogs: Randal Schwartz):

$Old_MacDonald = q#print #; $had_a_farm = (q-q:Just another Perl hacker,:-);
s/^/q[Sing it, boys and girls...],$Old_MacDonald.$had_a_farm/eieio;

http://www.itknowledge.com/tpj/obfusc-5.html :-))

cua

n.d.p.

[Bernhard Peissl]

Hi!

$Old_MacDonald = q#print #; $had_a_farm = (q-q:Just another Perl hacker,:-);
s/^/q[Sing it, boys and girls...],$Old_MacDonald.$had_a_farm/eieio;

http://www.itknowledge.com/tpj/obfusc-5.html :-))

Genial :-)

liebe Grüsse
Bernhard

[Bernhard Peissl]

Hi nochmal!

http://www.itknowledge.com/tpj/obfusc-5.html :-))

ich weiss ich weiss, ihr könnt selber klicken, aber es hat mir so gefallen, ich muss das hier jetzt loswerden!

#!/usr/bin/perl -l

print ocr(<<TPJ);
#  # # ## ##  ## ##  #    #  #  # # ##  #  #  #  #

# # #  # # #  # # #    # # # # # # # ## # # #

#  ### ## ##  ## ##  #    # # # # # ##  # ## ### #
#  # # #  #   #  # # #  # # # # # # # # #  # # # #
#  # # ## #   ## # # ## ###  #  ### # # #  # # # ##
TPJ

sub ocr{@{$-[$@++]}=split$,for(split'\n',shift);for$@(0..4){for(0..51){++$_{$_
}if($-[$@][$_]=~$")}}@&=(-1);for(sort{$a<=>$b}keys%_){push@&,$_ if($_{$_}>4)
  }push@&,52;for$@(0..13){@{$[$@][$_]}=@{$-[$_]}[$&[$@]+1..$&[$@+1]-1]for(0..
   4)}for(@){**=$_;$w=@{$*[$^=$$=0]}-1;for$@(0..4){for(1..$w){$^++if$*[$@][$_
    ]ne$*[$@][$_-1]}}for(0..$w){for$@(1..4){$$++ if$*[$@][$_]ne$*[$@-1][$_]}}
     for(0..20){push@},chr$_+65if(7*(8,4,2,9,2,3,7,8,1,$@,5,4,9,10,10,6,3,8,4,
      8,8)[$_]+(5,8,3,3,4,2,1,2,8,2,7,1,5,4,6,$@,3,6,8,4,1)[$_]==7*$^+$$)}}@}}

Keine Ahnung was das Ding macht, aber vielleicht kanns mir ja jemand erklären ;-) Cheatah, Calocybe, Michael (und alle anderen, die ich für echte Perl Profis halte) was ist los mit euch ?

:-)

Das war ein Gold-Link - Der wird mir noch ein paar Schmunzler kosten!

Danke,
Bernhard

[Christian Kruse]

Hi,

( ((a+)(b+)) (a*) (b*) (()(c)) )+

IMHO ein wenig eleganter wäre
(((a+)(b+))(a*)(b*)(c*))+

Und es sollte genau so funzen ;)

Man schreibe ein Programm das seinen _eigenen_ Quellcode auf den Bildschirm schreibt, _ohne_
dabei auf den Quellcode oder eine andere Datei zuzugreifen.

Hm, das dürfte eigentlich nicht möglich sein. Das sollte eine rekursive Rückschachtelung geben. Da
sich ja eine Pipe oder das öffnen von Dateien ausschließt, würde nur die "harte" Methode über bleiben:

print "ich tue dies und das";
print "print "ich tue dies und das"";
print "print " print "ich tue dies und das""";
usw

will heißen, es gäbe, wenn man das Problem über Rekursion "löst", eine Endlos-Rekursion.

mfg
CK1

[F.Heyer]

Hi,

( ((a+)(b+)) (a*) (b*) (()(c)) )+

IMHO ein wenig eleganter wäre
(((a+)(b+))(a*)(b*)(c*))+

Und es sollte genau so funzen ;)

Nein es ist falsch.

Dein Ausdruck erlaubt c* aber es ist laut Aufgabe _nicht_ erlaubt mehr als ein c hintereinander stehen zu haben.

Bsp: "acc" das matched dein regex, und es ist nicht zulässig.

cu
F.Heyer

[Christian Kruse]

Hi,

Dein Ausdruck erlaubt c* aber es ist laut Aufgabe _nicht_ erlaubt mehr als ein c hintereinander
stehen zu haben.

Stimmt, habe ich nicht beachtet. Aber dazu gibt es ja Mengen-Klammern:
(((a+)(b+))(a*)(b*)(c{0,1}))+

mfg
CK1

[F.Heyer]

Hi,

Dein Ausdruck erlaubt c* aber es ist laut Aufgabe _nicht_ erlaubt mehr als ein c hintereinander
stehen zu haben.

Stimmt, habe ich nicht beachtet. Aber dazu gibt es ja Mengen-Klammern:
(((a+)(b+))(a*)(b*)(c{0,1}))+

Das ist ja fast schon chat.

So ist es richtig, ich würde in einer echten app auch mit der Mengenklammer arbeiten, wusste aber nicht ob das eine für die Aufgabe zulässige Erweiterung ist. Der Autor meinte ja sogar schon eine leere Anweisung wäre event. nicht erlaubt. Interessant wäre noch die Frage was mehr Performance bringt, wobei ich vermute das nach dem kompilieren die beiden Ausdrücke gleich aussehen.

cu
F.Heyer

[Bernhard Peissl]

Hi,

Stimmt, habe ich nicht beachtet. Aber dazu gibt es ja Mengen-Klammern:
(((a+)(b+))(a*)(b*)(c{0,1}))+

Also: Ich würd mal sagen da haut was nicht so ganz hin:

((a+)(b+) ...)+

somit würde a oder b doch mindestens 1 mal vorkommen oder, kann aber auch gar nicht vorkommen ;-) Man könnte das letzte + durch ein *ersetzen, aber jetzt muss ich selbst mal überlegen, ....

Und: Wir sind hier nicht in Perl, hier gibts sowas wie Regeln ;-) *g*
soll heissen {0,1} gilt nicht :-( Es muss auch irgendwie mit * und + gehen!

So ist es richtig, ich würde in einer echten app auch mit der Mengenklammer arbeiten, wusste aber nicht ob das eine für die Aufgabe zulässige Erweiterung ist. Der Autor meinte ja sogar schon eine leere Anweisung wäre event. nicht erlaubt. Interessant wäre noch die Frage was mehr Performance bringt, wobei ich vermute das nach dem kompilieren die beiden Ausdrücke gleich aussehen.

Ach, ihr denkt doch immer nur ans Programmieren, schweift ab, lasst euch treiben ...
;-)

cu
F.Heyer

[Christian Kruse]

Hi,

Und: Wir sind hier nicht in Perl, hier gibts sowas wie Regeln ;-) *g*

Wieso Perl? Mengenklammern sind POSIX-valied.

soll heissen {0,1} gilt nicht :-( Es muss auch irgendwie mit * und + gehen!

Dann sag das sofort in der Aufgabe ;) POSIX wäre {0,1} auf jeden Fall.

mfg
CK1

[F.Heyer]

Hi,

Und: Wir sind hier nicht in Perl, hier gibts sowas wie Regeln ;-) *g*

Wieso Perl? Mengenklammern sind POSIX-valied.

soll heissen {0,1} gilt nicht :-( Es muss auch irgendwie mit * und + gehen!

Dann sag das sofort in der Aufgabe ;) POSIX wäre {0,1} auf jeden Fall.

Wo du recht hast hast du recht.
Mengenklammern gehören zu POSIX regex, sind sowohl in php als auch in den cc++ libregex erlaubt. Nur für reines ja nein nehme ich die leeren Klammern, bei grösseren Spannen sind die Mengenklammern sinnvoller.

cu
F.Heyer

[F.Heyer]

Hi,

Stimmt, habe ich nicht beachtet. Aber dazu gibt es ja Mengen-Klammern:
(((a+)(b+))(a*)(b*)(c{0,1}))+

Also: Ich würd mal sagen da haut was nicht so ganz hin:

((a+)(b+) ...)+

somit würde a oder b doch mindestens 1 mal vorkommen oder, kann aber auch gar nicht vorkommen ;-) Man könnte das letzte + durch ein *ersetzen, aber jetzt muss ich selbst mal überlegen, ....

Das hängt von der definierten Sprache ab.
Anders gefragt gehört ein leeres Programm zur Sprache dazu ja oder nein. Wenn nein muss es ein + sein wenn ja muss es ein * sein.
Rein logisch gesehen gehört ein leeres Programm dazu. Aber da hat sicher der Prof. das letzte Wort.

Und: Wir sind hier nicht in Perl, hier gibts sowas wie Regeln ;-) *g*

Das war gut! Ich bevorzuge für Scripte eh PHP, aber das ist vermutlich nur eine reine Geschmacksfrage.

cu
F.Heyer

[Bernhard Peissl]

Hi!

Wofür steht das F. eigentlich?

Anders gefragt gehört ein leeres Programm zur Sprache dazu ja oder nein. Wenn nein muss es ein + sein wenn ja muss es ein * sein.
Rein logisch gesehen gehört ein leeres Programm dazu. Aber da hat sicher der Prof. das letzte Wort.

Definitionssache eben :-)

Und: Wir sind hier nicht in Perl, hier gibts sowas wie Regeln ;-) *g*

Das war gut! Ich bevorzuge für Scripte eh PHP, aber das ist vermutlich nur eine reine Geschmacksfrage.

Wenn mich mal jemand echt beeindrucken will, dann kann er mir ja mal eine Formularabfrage mit HTML-Ausgabeseite in C++ geschrieben schicken (mailto:[e-mail]) Als Preis lade ich ihn/sie mal auf {0,1}* Getränke ein, wenn ich mal in seine/ihre Stadt kommen sollte

;-)

liebe Grüsse
Bernhard

[F.Heyer]

Hi!

Wofür steht das F. eigentlich?

Friedhelm Heyer steht im Pass.

Wenn mich mal jemand echt beeindrucken will, dann kann er mir ja mal eine Formularabfrage mit HTML-Ausgabeseite in C++ geschrieben schicken (mailto:[e-mail]) Als Preis lade ich ihn/sie mal auf {0,1}* Getränke ein, wenn ich mal in seine/ihre Stadt kommen sollte

Ist auf jeder Linux Distribution drauf.
Heisst so ähnlich wie libcgi++ oder so.

Aber einfacher als mit php geht es damit auch nicht.

cu

[Björn Höhrmann]

( ((a+)(b+)) (a*) (b*) (()(c)) )+

IMHO ein wenig eleganter wäre
(((a+)(b+))(a*)(b*)(c*))+

Und es sollte genau so funzen ;)

Nein, das erlaubt abccccccc

[Linksetzer]

<113417.html>

[Marko]

Hi Bernhard,

ich glaube die Formulierung der Aufgabe, die Du gegeben hast entspricht nicht genau dem Automaten. Wenn Du das Zustandsdiagramm aufzeichnest ist nämlich auch: abcabcc nicht möglich, da Du vor dem letzten c schon wieder in q0 bist, und es für C keine Übergangsfunktion gibt. Ausserdem gibt es auch beim b restriktionen, da es von q1 auch mit b nicht weitergeht.
Wenn ich mich recht erinnere löst man solche Aufgaben irgendwie über eine Grammatik in Backus-Nauer Form, aber frag mich nicht mehr wie, ich probier mal, vielleicht komm ich ja noch auf den Ausdruck.

Gruss

Marko

P.S.: Da ich das mal vor 5 Jahren gelernt habe, bitte ich um Nachsicht, falls ich gerade Schwachsinn verzapft habe.

[Marko]

Sorry,

hab grad meinen ersten Fehler gefunden:

(q0,a) -> {qo,q2}

bedeutet doch, dass es in Beide Richtungen geht, oder ? Das hab ich übersehen.
Und

(q1,c) -> {q0}

geht nur in eine. Aber dann muss trotzdem aus q1 ein b oder c rausführen, niemals ein a. Also kann auch bac nicht am Wortanfang vorkommen.

Gruss

Marko

[Bernhard Peissl]

Hi Marko!

(q1,c) -> {q0}

geht nur in eine. Aber dann muss trotzdem aus q1 ein b oder c rausführen, niemals ein a. Also kann auch bac nicht am Wortanfang vorkommen.

(q0,b) -> q0
(q0,a) -> q2
(q2,c) -> q0

e voilá: bac ;-)

grüsse
Bernhard

[Marko]

Hi Bernhard,

ich hab mich für ein paar Semester an technischer Informatik an der Uni-Mannheim probiert, mach jetzt das gleiche immernoch aber an der FH-Mannheim. Wir haben das damals im ersten Semester gemacht.

(q2,c) -> q0

Du hast recht, aber oben im Automaten stand die Funktion nicht drin, noch ein Tippfehler, wie ich vermute ?

Gruss

Marko

[Bernhard Peissl]

Hi Marko,

ich hab mich für ein paar Semester an technischer Informatik an der Uni-Mannheim probiert, mach jetzt das gleiche immernoch aber an der FH-Mannheim. Wir haben das damals im ersten Semester gemacht.

Mann, mann, mann, dann musst ja eh der volle Crack sein ;-)

(q2,c) -> q0

Du hast recht, aber oben im Automaten stand die Funktion nicht drin, noch ein Tippfehler, wie ich vermute ?

Schau nochmal, besonders auf die letzte Übergangsfunktion ;-)

schöne Grüsse nach Mannheim
Bernhard

[Marko]

Hallo Bernhard,

wär ich voll der Crack, wär ich jetzt Diplominformatiker und würd ne Doktorarbeit schreiben, und kein Student mehr ;-)
Irgendwie bin ich jetzt echt schon ein bisserl Banane (sonst wär das eben nicht passiert), aber könnte es sein, dass die Übergangsfunktion:

(q2,c) -> q0 bedeutet, dass Du auf q2 kommst, wenn Du von q0 mit c springst. Oder was bedeutet andernfalls das(q0,a) -> {qo,q2}: Was passiert wenn ich von q0 mit a springe komm ich auf q0 oder auf q2 ? Das wäre ja nicht mehr deterministisch. Vielleicht raff ich einfach die Notation nicht so ganz, wir haben das damals irgendwie anders notiert. Oder ich hab vergessen wie so ein Automat funktioniert.
Habt Ihr den Automat mal aufgezeichnet ? Ich hab irgendwie das dumpfe Gefühl dass irgendwo noch ein Wurm drinnen ist, kann aber auch sein, dass ich jetzt einfach zuviel aus meinem Halbwissen gedacht habe ;-)

Gruss

Marko

• Zustände {qo,q1,q2}
• Alphabet {a,b,c}
• Anfangs und Endzustand ist {q0}
• Übergangsfunktion: (q0,a) -> {qo,q2}
                       (q0,b) -> {q0,q1}
                       (q1,c) -> {q0}
                       (q2,b) -> {q1}
                       (q2,c) -> {q0}

[Bernhard Peissl]

Hallo Marko,

wär ich voll der Crack, wär ich jetzt Diplominformatiker und würd ne Doktorarbeit schreiben, und kein Student mehr ;-)

;-)

Irgendwie bin ich jetzt echt schon ein bisserl Banane (sonst wär das eben nicht passiert), aber könnte es sein, dass die Übergangsfunktion:

(q2,c) -> q0 bedeutet, dass Du auf q2 kommst, wenn Du von q0 mit c springst.

Nein! Wenn der Automat im Zustand 2 ein c einliest, dann geht er in Zustand 0 über

Oder was bedeutet andernfalls das(q0,a) -> {qo,q2}: Was passiert wenn ich von q0 mit a springe komm ich auf q0 oder auf q2 ? Das wäre ja nicht mehr deterministisch.

Na, wer sagt denn dass es ein deterministischer endlicher Automat ist ;-)
Ich dachte nicht, dass sich damit jemand auskennen wird, also hab ich nur "endlicher Automat geschrieben", aber es ist - wie du richtig erkannt hast - ein nicht-deterministischer endlicher Automat. Das heisst, es stehen ihm 2 Zustände offen in die er wechseln kann, wenn er in q0 ein a einliest :-)

Vielleicht raff ich einfach die Notation nicht so ganz, wir haben das damals irgendwie anders notiert. Oder ich hab vergessen wie so ein Automat funktioniert.

Wahrscheinlich ersteres ;-) Es ist anzunehmen, dass es mehrere Notationen gibt! Auch die von mir gewählte ist im Grunde nicht ganz korrekt. Eigentlich sollte es heissen:

d(q0,a) = {qo,q2} , ... wobei d eigentlich ein "delta" sein sollte, und die Übergangsfunktion darstellt. Aber da ich den richtigen ASCII-Code für delta, sigma und co. grad nicht bei der Hand hatte, und der Pfeil imho verständlicher ausdrückt, was geschieht, hab ich's halt so angeschrieben.

Habt Ihr den Automat mal aufgezeichnet ? Ich hab irgendwie das dumpfe Gefühl dass irgendwo noch ein Wurm drinnen ist, kann aber auch sein, dass ich jetzt einfach zuviel aus meinem Halbwissen gedacht habe ;-)

<img src="http://www.wt-akademie.at/automat.jpg" alt="">

Ich hoffe das mit dem Bild-einbinden hat geklappt und man sieht so halbwegs was ;-)
Sollte so stimmen!

liebe Grüsse
Bernhard

[Marko]

Hallo Bernhard,

jetzt muss ich leider echt passen, die theoretische Informatik Vorlesung hab ich nie gehört, nur in Praktische Informatik 1 haben wir mit endlichen, deterministischen Automaten rumgespielt. Dehalb hab ich automatisch angenommen es sei einer. Da gab es dann Verfahren wie man von dem Automat zur Grammatik und zum regulären Ausdruck kommt.
Ich vermute aber, dass auch bei nicht deterministischen Automaten eignetlich nicht rumprobieren der Weg ist, sondern dass es Algorithmen gibt, wie man das Ding in Grammatik und Regulären Ausdruck überführt (im praktischen Leben würden zwar wahrscheinlich 99% der Leute mit ausprobieren arbeiten, ich auch).

viel Glück für die Klausur !!!

Gruss

Marko

[Michael N.]

Hallo Bernhard,

Ich habe mir Deinen Automaten mal angeschaut und fand ihn an einer Stelle etwas widersprüchlich, von q(0) gehst Du mit "a" nach q(0) und nach q(2) ("b" --> q(0) und q(1)) gleichzeitig gehst Du aus q(2) mit "b" nach q(1), aber mit "a" nicht aus q(1) nach q(2), somit kann der Automat parallel in unter Umständen in zwei Zuständen sein, oder im Fall, daß er in q(1) ist in keinen Zustand wechseln, obwohl ein legales Element vorhanden ist.

<img src="http://www.wt-akademie.at/automat.jpg" alt="">

Ich würde daher eher folgenden Automaten vorschlagen:

a,b
                        ---------
                              
                              
  ########          ########    
  #      #  a,b     #      #    
  # q(0) #---------># q(1) #<----
  #      #<---------#      #
  ########   c      ########

(Ich hoffe, daß diese ASCII-Grafik geklappt hat.)

Folgender Ausdruck liegt dabei zugrunde:

((ab)[c])*

Legende:
() ==> Eines der Elemente aus der Klammer
[]  ==> kann vorkommen, muß aber nicht
*   ==> Wiederholung (zwischen 0 und n)

Bis denndann

Michael N.

[Bernhard Peissl]

Hallo Michael,

Ich würde daher eher folgenden Automaten vorschlagen:

a,b
                        ---------
                              
                              
  ########          ########    
  #      #  a,b     #      #    
  # q(0) #---------># q(1) #<----
  #      #<---------#      #
  ########   c      ########

(Ich hoffe, daß diese ASCII-Grafik geklappt hat.)

ja, sieht toll aus

Folgender Ausdruck liegt dabei zugrunde:

((ab)[c])*

Legende:
() ==> Eines der Elemente aus der Klammer
[]  ==> kann vorkommen, muß aber nicht
*   ==> Wiederholung (zwischen 0 und n)

Stimmt, der Automat ist richtig, (wenn beides Endzustände sind) aber den Automat den ich vorgestellt habe stand so in der Angabe, die wir von unserem Professor erhalten haben, also habe ich mich an die gehalten, aber zweifelsohne, deiner wäre einfacher und besser :-)

Ich habe mir Deinen Automaten mal angeschaut und fand ihn an einer Stelle etwas widersprüchlich, von q(0) gehst Du mit "a" nach q(0) und nach q(2) ("b" --> q(0) und q(1)) gleichzeitig gehst Du aus q(2) mit "b" nach q(1), aber mit "a" nicht aus q(1) nach q(2), somit kann der Automat parallel in unter Umständen in zwei Zuständen sein, oder im Fall, daß er in q(1) ist in keinen Zustand wechseln, obwohl ein legales Element vorhanden ist.

Tut mir leid, da komm ich nicht mit! Wieso gleichzeitig in 2 Zuständen? Wie gesagt, es ist ja ein NICHT-deterministischer Automat, hat also die Wahl zw. mehreren Zuständen wenn er ein gewisses Zeichen einliest, aber gehen kann er ja nur in einen!

Was du über q1 sagt stimmt _fast_, es ist richtig, dass er von q1 aus kein a einlesen kann, sonder nur ein c, aber 'ab' geht ja auch über eine Scheife in q0, es kann also jedes Wort gebildet werden! Aber ich geb dir recht, der Automat verwirrt ein wenig! Deiner gefällt mir eindeutig besser, aber es kann ja auch sein, dass uns unsere Professoren ja auch bloss ein wenig ärgern ähm... ich meine fordern ;-) wollen

Deiner Antwort nach kennst du dich aus wovon du sprichst, was machst du?

Naja, jedenfalls weisst ja sicher auch dass man aus jedem nicht-det.Aut. einen deterministischen machen kann. Ich hab hier mal "quick & dirty" (hab ich kürzlich aufgeschnappt, gefällt mir) einen deterministischen Automat draus gebastelt:

<img src="http://www.wt-akademie.at/automat2.JPG" alt="">

Vielleicht gefällt dir der besser ;-)

liebe Grüsse
Bernhard

[Michael N.]

Hallo Bernhard,

[...]aber zweifelsohne, deiner wäre einfacher und besser :-)

Das ist das, was ich immer versuche bei Lösungen, einfach und übersichtlich (dann werden sie auch von Professoren verstanden). Übrigens gibts da irgendwo auch sowas wie eine "Lehraussage" oder ein Prinzip, nämlich KISS, was da heißt "Keep it simple, stupid." und das ist nicht immer das schlechteste.

[...] Wie gesagt, es ist ja ein NICHT-deterministischer Automat, hat also die Wahl zw. mehreren Zuständen wenn er ein gewisses Zeichen einliest, aber gehen kann er ja nur in einen!

Und der hängt bei Deinem ursprünglichen Automaten ja vom Folgezeichen ab.

Deiner Antwort nach kennst du dich aus wovon du sprichst, was machst du?

Ich sitze hier und programmiere beruflich mit HTML, JavaScript, NET.DATA und VBA rum. Irgendwann hab ich mal den Informatikassistenten Fachrichtung Softwaretechnologie am BIB in Bergisch-Gladbach gemacht.

<img src="http://www.wt-akademie.at/automat2.JPG" alt="">

Vielleicht gefällt dir der besser ;-)

Ja, der gefällt mir besser :-))).

Bis denndann

Michael N.

[Bernhard Peissl]

hi marko!

Wow, ein Kundiger *freu*!
Gibst du auch Nachhilfe ;-)

ich glaube die Formulierung der Aufgabe, die Du gegeben hast
entspricht nicht genau dem Automaten.

Na, ich muss es doch so erklären, dass es auch die verstehen, die nicht wissen was ein Automat ist ;-)

Wenn Du das Zustandsdiagramm aufzeichnest ist nämlich auch:
abcabcc nicht möglich, da Du vor dem letzten c schon wieder in q0
bist, und es für C keine Übergangsfunktion gibt.

Hast vollkommen Recht, das war ein Tippfehler - hab mich auch schon bei Alex entschuldigt ;-)

Ausserdem gibt es auch beim b restriktionen, da es von q1 auch
mit b nicht weitergeht.

Stimmt, von q1 aus nicht, aber man kann trotzdem jedes beliebige Wort mit b bauen, oder hab ich was übersehen?

abc ist z.b: möglich über (q0,a) -> q0
                          (q0,b) -> q1
                          (q1,c) -> q0

abb über (q0,a) -> q0
         (q0,b) -> q0
         (q0,b) -> q0

Wenn ich mich recht erinnere löst man solche Aufgaben irgendwie
über eine Grammatik in Backus-Nauer Form, aber frag mich nicht
mehr wie, ich probier mal, vielleicht komm ich ja noch auf den
Ausdruck.

Ja, wir lernen: Jede Sprache lässt sich über einen Regulären Ausdruck beschreiben, mit den daraus zu bildenden regulären Grammatiken kann man Sätze aus dieser Sprache erzeugen, und dann diese mit endlichen Automaten auf ihre Richtigkeit prüfen, wobei der Automat wiederum nur eine Sprache akzeptiert, die diesem Regulären Ausdruck entspricht! Schöner Kreislauf oder ;-)

P.S.: Da ich das mal vor 5 Jahren gelernt habe, bitte ich um
Nachsicht, falls ich gerade Schwachsinn verzapft habe.

Echt, was hast du studiert ?

liebe Grüsse
Bernhard

[n.d. parker]

re hi

Ja, wir lernen: Jede Sprache lässt sich über einen Regulären Ausdruck beschreiben, [...]

naja, das stimmt leider nicht, es sei denn, du meinst nur nie bezeichner (oder woerter), wie gesagt, schachtelsaetze kann ein regex nicht logisch zuordnen (...bis in unendliche Tiefe)

also, definiere die aufgabe genau, und wir loesen sie .-))

cua

n.d.p.

[Bernhard Peissl]

Hallo n.d.p

Ja, wir lernen: Jede Sprache lässt sich über einen Regulären Ausdruck beschreiben, [...]
naja, das stimmt leider nicht, es sei denn, du meinst nur nie bezeichner (oder woerter), wie gesagt, schachtelsaetze kann ein regex nicht logisch zuordnen (...bis in unendliche Tiefe)

So gut bin ich auch wieder nicht, dass ich dir das stichhaltig widerlegen könnte, und ehrlichgesagt gibt es einiges in meinem Studium, dessen tieferen Sinn ich noch nicht so richtig durchschaut habe, aber ich kann meinem Prof ja mal deine email-Adresse zukommen lassen ;-)

Wenn du damit z.b. verschachtelte if-statements meinst, geht das schon, dann macht der Automat einfach eine schleife in demselben Zustand solange er ein "if" einliest, wenn er was anderes liest, hört er mit der Schleife auf und geht in einen anderen Zustand über!

Aber wie gesagt, er erkennt eben nur, ob ein Wort zur Sprache gehört, den Sinn hinter dem Wort, bzw, in welchem Kontext das Wort stehen darf, pffhhhh ich weiss auch nicht .... BNF, Grammatiken, wp-Verifikation, was weiss ich, ... ich bin ja auch bloss ein Student, der das für eine Grundzüge(!) der Informatik-Prüfung pauken muss :-(

liebe Grüsse
Bernhard

[n.d. parker]

re hi .-)

Wenn du damit z.b. verschachtelte if-statements meinst, geht das schon, dann macht der Automat einfach eine schleife in demselben Zustand solange er ein "if" einliest, wenn er was anderes liest, hört er mit der Schleife auf und geht in einen anderen Zustand über!

ja, der automat -> so eine regex hat aber kein gedaechtnis, die passt, oder sie passt nicht, rekursionen (nicht backtracking! ) sind eben nicht moeglich. ich kann also beispielsweise nicht pruefen ob folgendes korrekt ist, wenn die klammerungsebene (oder tiefe) beliebig ist:

a=(b+(c+(d+(e+f))))

ich bin ja auch bloss ein Student, der das für eine Grundzüge(!) der Informatik-Prüfung pauken muss :-(

ein glueck, ich studiere "nur" ET *g*

liebe Grüsse

ebenso .-)

n.d.p.

[Klaus Mock]

Hallo,

Stellt euch vor ihr habt eine Sprache die sich aus nur drei Buchstaben zusammensetzt! Es geht also um eine Sprache aus dem Alphabet {a,b,c}*, WOBEI vor jedem 'c' zumindest ein 'a' oder 'b' stehen MUSS. Ansonsten Syntaxfehler ;-) Anders gesagt: Es kann kein c vorkommen, vor dem nicht entweder mindestens ein a oder b steht!

also
/^([ab]c?)+$/

Zuerst muß ein a oder b kommen [ab], dann eventuell 'c' (c?). das ganze mindestens einmal passieren (+).

die Begrenzer (^ und $) brauchst Du, damit nicht z.B. 'zab' erkennst, wenn allerding vorher schon feststeht, daß es nur die gegebenen drei Zeichen im String gibt, dann kannst Du das auch weglassen. Alternativ könntest Du auch

hier mein Test-code

@worte = ('aaa', 'abcabc', 'ac', 'bcbbbb', 'ba', 'cabac',
           'c', 'abccb','abcabcc');

foreach $wort(@worte)
{
print "$wort ist ".
            ($wort=~/^([ab]c?)+$/?"":"nicht ").
             "richtig\n";
}

Grüße
  Klaus

[Klaus Mock]

Nochmals Hallo,

die Begrenzer (^ und $) brauchst Du, damit nicht z.B. 'zab' erkennst, wenn allerding vorher schon feststeht, daß es nur die gegebenen drei Zeichen im String gibt, dann kannst Du das auch weglassen. Alternativ könntest Du auch

Nachtrag: die Begrenzer (^ und $) brauchst Du immer, da ja die Regeex versucht, Treffer zu finden, und somit z.B. auch 'cab' ein Treffer sein würde, da die regex 'ab' als Treffer anerkennt.

Grüße
  Klaus

[Bernhard Peissl]

Hallo,

also

»»  /^([ab]c?)+$/

Das könnte man übertragen etwa so formulieren oder?:

((ab)c*)+

Das ist meiner meinung nach schon verdammt knapp dran, aber auch du denkst dabei zu sehr an Perl! Wenn man aus einem Text diese Sprache isolieren will, dann stimmts! Aber wenn ich streng wäre, dann würde ich sagen, der (vorgegebene) Automat würde diese Sprache nicht erkennen, wegen dem Plus hinten ;-)

((ab)c*)* müsste glaube ich passen! Oder hab ich was vergessen ?

liebe Grüsse
Bernhard

[AlexBausW]

Hallo Bernhard,

((ab)c*)* müsste glaube ich passen! Oder hab ich was vergessen ?

^.....matched keins bis viele c

Vergessen hast Du, daß nicht 2 c hintereinander vorkommen dürfen ;-)

Gruß AlexBausW

Please visit my SELFvisitingcard @ http://www.atomic-eggs.com/selfspezial/daten/150.html

[Bernhard Peissl]

Hi!

((ab)c*)* müsste glaube ich passen! Oder hab ich was vergessen ?
          ^.....matched keins bis viele c

Vergessen hast Du, daß nicht 2 c hintereinander vorkommen dürfen ;-)

Ach verdammt, stimmt :-(

Ob wir jemals noch dahinter kommen werden ;-)

liebe Grüsse
Bernhard

[Klaus Mock]

Hallo,

also
»»  /^([ab]c?)+$/

Das könnte man übertragen etwa so formulieren oder?:

((ab)c*)+

nein, wenn dann schon

^((ab)c?)+$

? match o oder 1 Zeichen (perldoc perlre). Sollte das nicht immer sein, dann
/^([ab]c{0,1})+$/

Das ist meiner meinung nach schon verdammt knapp dran, aber auch du denkst dabei zu sehr an Perl!

verdammt knapp?  auch ohne Perl ein glatter Treffer ;-)

Wenn man aus einem Text diese Sprache isolieren will, dann stimmts!

Nur Elemente der Sprache sind erlaubt! Alles andere wird gnadenlos beanstandet.

Aber wenn ich streng wäre, dann würde ich sagen, der (vorgegebene) Automat würde diese Sprache nicht erkennen, wegen dem Plus hinten ;-)

Ich bin streng, also nur a,b oder c, kein wort ist nicht gültig, c muß nach a oder b kommen. Eigentlich gibt es nur 'a', 'b', 'ac' oder 'bc' oder beliebige Aneinanderreihungen dieser vier 'Grundelemente'.
Wenn Du allerding auch '' als gültiges Element der Sprache anerkennst, dann heißt die Regex

/^([ab]c?)*$/

Daß ich Die Begrenzer (^ und $) verwendet, habe ich zwar grob schon einmal erklärt, will es hier aber vielleicht wiederholen:
Wenn ich es nicht machen würde, dann würden auch Texte gemacht werden, in denen nur Teile von Deiner Sprache vorkommen würden. auch würde ein führendes 'c' oder doppelte 'c' gültig sein.

Wenn ich das gefunden Wort in $1 haben will, und die Regex

/(([ab]c?)*)/ # das äußere Klammernpaar ist nur für $1 relevant
lauten würde, dann würde in dem text

'aber cab ist da nicht richtig'
Treffer finden (hier mit den Treffern in Klammer)
'(ab)er c(ab) ist d(a) nicht richtig'
obwohl der text nicht teil Deiner Sprache ist.

Auch bei 'cab' == 'c(ab)' oder 'acc' == '(ac)c' würden Treffer gefunden.

Nein, ich bleib dabei

/^([ab]c?)+$/

oder bei '' als gültiger text

/^([ab]c?)*$/

Und das Ganze ist (so denk ich jedenfalls) sed, grep, awk usw. tauglich, ich sehe da keine Perl-spezifischen elemente in der Regex.

Grüße
  Klaus

PS.: ich frag mich gerade, was ist richtig 'der regex' oder 'die regex'. Für mich war es intuitiv immer 'die regex'.Vielleicht weil reguläre Ausdrücke eher weibliche Charakterzüge aufweisen ;-)

[Bernhard Peissl]

Hallo,

^((ab)c?)+$
? match o oder 1 Zeichen (perldoc perlre). Sollte das nicht immer
sein, dann /^([ab]c{0,1})+$/

? und {..} gilt trotzdem nicht :-(
nur *, +, , und () sind das einzige was im Reg.Exp vorkommen darf.
Freund Mathematik lässt grüssen .-)

^ und $ brauchst du auch nicht, da die Sprache ohnehin bloss aus a,b, und c besteht, kann also gar nix anderes vorkommen!

Das ist meiner meinung nach schon verdammt knapp dran, aber
auch du denkst dabei zu sehr an Perl!
verdammt knapp?  auch ohne Perl ein glatter Treffer ;-)

Sorry, aber Alex hat recht: <113368.html>

PS.: ich frag mich gerade, was ist richtig 'der regex' oder 'die
regex'. Für mich war es intuitiv immer 'die regex'.Vielleicht
weil reguläre Ausdrücke eher weibliche Charakterzüge aufweisen ;-)

Die da wären? Bis auf das $ und die Klammern seh ich keine Rundungen ;-) - Uuuiiii, ich glaub jetzt mach ich mich grad bei der 2.Bevölkerungshälfte ziemlich unbeliebt ;-)

liebe Grüsse
Bernhard

[Klaus Mock]

Hallo,

^((ab)c?)+$
? match o oder 1 Zeichen (perldoc perlre). Sollte das nicht immer
sein, dann /^([ab]c{0,1})+$/

? und {..} gilt trotzdem nicht :-(
nur *, +, , und () sind das einzige was im Reg.Exp vorkommen darf.

Freund Mathematik lässt grüssen .-)

Ich grüß zurück, wenn ich sie treffe.
(acbcab)+
Das Plus (+) steht übrigens für 1 oder mehr. Du scheinst das immer wieder zu verwechseln.

Da reguläre Ausdrücke versuchen Muster in einem gegebenen String zu erkennen, werden sie auch fündig wenn nur Teile vom String dem Muster entsprechen.
Sollte dies in Deiner vorgegebenen Engine anders sein, dann laß es mich wissen. Da ich kein Theoretiker bin, weiß ich nicht mit welchen Ansätzen hier gearbeitet werden.
Du hast übrigens im Ursprungsposting keinerlei Vorgaben gemacht, was die Möglichkeiten Deiner Engine betrifft.

Wenn Deine Engine nun nur matcht, wenn der gesamte durchsuchte Ausdruck der regex entspricht, dann kannst Du auf Anfang- und Ende-Begrenzer verzichten. Sollte das nicht der Fall sein, führt jede Regex nicht zum gewünschten Ergebnis. 'acc' würde ja gültig sein, weil 'ac' Gültig ist, und der Rest ignoriert wird. Um den vollständigen gegebenen Ausdruck zu untersuchen, mußt Du dies der Regex schon sagen.

Ich denke, Deine nachträglichen Einschränkungen führen dazu, daß diese Aufgabe unlösbar wird. Das ist wie wenn Du jemandem sagst, er soll irgendwohin kommen, sich aber nicht vom Fleck bewegen.
Aber ich bin gern bereit mich nochmals mit der Regex zu befassen, wenn Du mir sagst, mit welchen Eigenschaften Deine gegebene Engine arbeitet (ein Link auf die Beschreibung vielleicht).

^ und $ brauchst du auch nicht, da die Sprache ohnehin bloss aus a,b, und c besteht, kann also gar nix anderes vorkommen!

Stimmt nicht, Teilausdrücke werden sonst erkannt,s.o.

verdammt knapp?  auch ohne Perl ein glatter Treffer ;-)

Sorry, aber Alex hat recht: <113368.html>

Ich versteh nicht, was was Meine Aussage mit dem genannten Posting zu tun hat.

regex'. Für mich war es intuitiv immer 'die regex'.Vielleicht
weil reguläre Ausdrücke eher weibliche Charakterzüge aufweisen ;-)

Die da wären? Bis auf das $ und die Klammern seh ich keine Rundungen ;-) - Uuuiiii, ich glaub jetzt mach ich mich grad bei der 2.Bevölkerungshälfte ziemlich unbeliebt ;-)

Ich redete von Charakterzügen, nicht von körperlichen Eigenschaften.
Genau kann ich das nicht sagen, ich versuchs mal:
Toleranz (Eine Regex vesucht immer, was zu finden, auch wenns aussichtslos erscheint)
Ausdauernd (Wenn notwendig, wird solange gesucht, bis etwas gefunden wird)
Flexibel (mit wenigen Elementen können viele mögliche Kombinationen beschrieben werden)

Na ja, und oft versteht man(n) einfach nicht, was sie aussagen will ;-)

Es ginbt zwar einige maskuline Züge (gieriges Verhalten der Quantifier * und +), aber es überwiegen für mich die weiblichen Qualitäten;-)

Grüße
  Klaus

[Bernhard Peissl]

Hallo Klaus!

Du hast übrigens im Ursprungsposting keinerlei Vorgaben gemacht, was die Möglichkeiten Deiner Engine betrifft.

Die Engine, wie du sagst, ist ein Automat. Keine Programmiersprache, bzw. Interpreter, ... Es ist ein abstraktes Problem: Ein Automat liest ein Zeichen nach dem anderen ein, im übrigen immer ganze Wörter, also Leerzeichen davor und dahinter und sieht nach, ob das Wort Teil der Sprache ist, die von dem Regulären Ausdruck, bzw. der daraus ableitbaren regulären Grammtik beschrieben wird.

Wenn Deine Engine nun nur matcht, wenn der gesamte durchsuchte Ausdruck der regex entspricht, dann kannst Du auf Anfang- und Ende-Begrenzer verzichten. Sollte das nicht der Fall sein, führt jede Regex nicht zum gewünschten Ergebnis. 'acc' würde ja gültig sein, weil 'ac' Gültig ist, und der Rest ignoriert wird. Um den vollständigen gegebenen Ausdruck zu untersuchen, mußt Du dies der Regex schon sagen.

wie oben, es sollen ganze Wörter sein, und das Wort 'acc' ist eindeutig kein Wort der Sprache :-(

Ich denke, Deine nachträglichen Einschränkungen führen dazu, daß diese Aufgabe unlösbar wird. Das ist wie wenn Du jemandem sagst, er soll irgendwohin kommen, sich aber nicht vom Fleck bewegen.

Wieso nachträglich, ok, vielleicht hab ich mich nicht so verständlich ausdrücken können, aber es ist ja auch ein ziemlich schwieriges Thema! Und ich muss das Zeugs ja auch erst lernen! Wie soll man jemandem beibringen wozu ein Automat dient, wenn derjenige nicht den nötigen Background (Sprachentheorie) hat! Aber es war ja auch bloss als Versuch gedacht, erstens ob ich es schaffe euch das halbwegs zu erklären, und zweitens ob ihr es schafft das halbwegs zu lösen ;-)

Aber ich bin gern bereit mich nochmals mit der Regex zu befassen, wenn Du mir sagst, mit welchen Eigenschaften Deine gegebene Engine arbeitet (ein Link auf die Beschreibung vielleicht).

Ich will dich ja nicht zwingen, wenn du Spass daran hattest, dann sitz dich ruhig noch mal hin, aber sonst brauchst du nicht!

Link hab ich keinen, da es sich ja auch um kein "reales" Projekt handelt. Ich kann dir höchstens den Link sagen, wo das Skriptum zur Vorlesung runterladbar ist:

[http://www.par.univie.ac.at/teach/99S/GZInfVII/VO.pdf]

Na ja, und oft versteht man(n) einfach nicht, was sie aussagen will ;-)

Es ginbt zwar einige maskuline Züge (gieriges Verhalten der Quantifier * und +), aber es überwiegen für mich die weiblichen Qualitäten;-)

*g* :-)

liebe Grüsse
Bernhard

[Klaus Mock]

Hallo Bernhard,

Entweder reden wir aneinander vorbei, oder ich versteh's wirklich nicht.

Reguläre ausdrücke sind stark von einer verwendeten Engine abhängig. Jedes reale Programm, welches Reguläre Ausdrücke versteht, besitzt eine bestimmte Grammatik. Ob das nu Perl. sed, emacs, oder was auch immer ist.

Auch wenn wir hier nicht von regulären Ausdrücken sprechen, die in einem Programm implementiert sind, so muß ein bestimmtes Regelwerk vorhanden sein. Du sagst z.B. es dürfen keine ? und {0,1} vorkommen.

Auch ist es von fundamentaler Bedeutung festzulegen, wann die Mustererkennung zu einem positiven Ergebnis kommt. Ein 'dingsda', welche die Regex zur Entscheidungsfindung verwendet, wird, so lautet eigentlich die vorgabe bei regulären ausdrücken, immer versuchen, einen Treffer zu finden.

Daher meine Frage nach dem Regelwerk. Ohne diesem Regelwerk ist eine gültige Lösung nicht zu finden.
Beispiel 1:
Vorgabe: Positives Matching ist nur möglich, wenn der gesamte untersuchte Ausdruck übereinstimmt.

• matched bei 1 oder mehr
  * bei 0 oder mehr
  in verbinung mit () stellt mögliche Teilausdrücke dar
  Regex: (acbcab)+

Beispiel 2:
Wie 1 jedoch Positives Matching ist möglich, wenn ein Teil des untersuchten Ausdrucks übereinstimmt.
^ stellt den Beginn, $ das Ende des Ausdrucks dar

Regex: ^(acbcab)+$

Hier müssen wir unbedingt einen Mechanismus einführen, der uns ermöglicht, daß wir den gesamten Ausdruck auch beschreiben können.
Sonst ist es uns unmöglich, eine vollständige Beschreibung zu formulieren.

Es ist ja auch in der Praxis so, daß die Regex stark von dem vorgegebenen Regelwerk abhängig ist. DU kannst ja auch nicht jede in Perl funktionierende Regex in awk einsetzen, da das zugrundeliegende Regelwerk geändert wurde.

Hallo Klaus!

Du hast übrigens im Ursprungsposting keinerlei Vorgaben gemacht, was die Möglichkeiten Deiner Engine betrifft.

Die Engine, wie du sagst, ist ein Automat. Keine Programmiersprache, bzw. Interpreter, ... Es ist ein abstraktes Problem: Ein Automat liest ein Zeichen nach dem anderen ein, im übrigen immer ganze Wörter, also Leerzeichen davor und dahinter und sieht nach, ob das Wort Teil der Sprache ist, die von dem Regulären Ausdruck, bzw. der daraus ableitbaren regulären Grammtik beschrieben wird.

Hier haben wir wieder das Problem. _Wie_ erkennt der Automat die Wortgrenze?

Nur mit einem Regelwerk, welches genau festlegt, wie Wortgrenzen erkannt werden, ist das Problem zu lösen. Es kann durchaus auch sein, daß die Regex
\b(acabab)+\b
heißt, wenn '\b' im Regelwerk als Wortgrenze definiert ist. Allerdings würde eine übliche Regexe-Engine nicht erkennen, ob das nächste Wort nicht ungültig ist.
Genausogut kann ^ und $ herangezogen werden, wenn das Regelwerk es erlaubt, und der zu untersuchende Ausdruck nur ein Wort sein kann. Ist alles Definitionssache.

wie oben, es sollen ganze Wörter sein, und das Wort 'acc' ist eindeutig kein Wort der Sprache :-(

Nochmals, woran erkennt der Automat das Ende des Wortes? Sicherlich nicht am Ende eines gültigen Matching.

Solange Du Dir über das gesamte Regelwerk für eine zu verwendende Regex im Klaren bist, ist die Aufgabe auch nicht lösbar. Leider:-(

Ich könnte ja auch sagen:
[ steht für Anfang des Ausdrucks
] steht für Ende des Ausdrucks

für 1 oder mehr

{} für strukturelle zusammenfassung
, als Trennzeichen von Alternativen

daraus ergibt sich folgende Regex:
[{ac,bc,a,b}#]

Diese regex würde auch nur matchen, wenn gültige Wörter in Deiner Sprache übergeben werden. Nur die Formulierung ist anders.

BTW.: Das Leerzeichen ist _kein_ gültiges Sprachelement in der von Dir ursprünglich vorgestellten Sprache.

Grüße
  Klaus

[Bernhard Peissl]

Hallo Klaus,

Entweder reden wir aneinander vorbei, oder ich versteh's wirklich nicht.

Da dich das anscheinend doch interessiert, erkläre ich dir jetzt mal was ein Automat genau ist:

Er besteht aus drei Komponenten:

1. Eingabeband: Darauf steht das zu analysierende Wort!
2. Lesekopf: Zeigt zu Beignn auf das erste Zeichen und geht mit jedem Schritt um ein Feld(Zeichen) nach rechts
3. Kontrolleinheit: Darin wird der aktuelle Zustand (q0, q1, q2) abgespeichert

Je nach dem was als nächstes unter dem Lesekopf steht, wird der Zustand abgefragt und eins weitergegangen, und wieder abgespeichert in der Kontrolleinheit. Wenn er also im Zustand q1 ein c einliest, geht er aufgrund der Regel (q1,c)->{q0} in den Zustand q0 über, dann liest er wieder was ein ... solange bis der Lesekopf entweder:

• kein Zeichen mehr im Eingabeband findet, dann liefert der Automat zurück: Das Wort ist gültig! - wird akzeptiert.
• undef liefert, dann bricht er ab mit der Meldung "Nicht akzeptiert!"

Das Eingabeband kannst du dir so vorstellen:
-----------------------------------
abcaabc acbb ba...
-----------------------------------

Die Oder-Striche () markieren die Felder des Eingabebandes!

Daher meine Frage nach dem Regelwerk. Ohne diesem Regelwerk ist eine gültige Lösung nicht zu finden.
Beispiel 1:
Vorgabe: Positives Matching ist nur möglich, wenn der gesamte untersuchte Ausdruck übereinstimmt.

• matched bei 1 oder mehr
  * bei 0 oder mehr
  in verbinung mit () stellt mögliche Teilausdrücke dar
  Regex: (acbcab)+

stimmt ja eh, hab ich ja schon erlaubt ;-)

Beispiel 2:
Wie 1 jedoch Positives Matching ist möglich, wenn ein Teil des untersuchten Ausdrucks übereinstimmt.
^ stellt den Beginn, $ das Ende des Ausdrucks dar

Regex: ^(acbcab)+$

Von mir aus, wenn euch die $$ so gefallen ;-)

In Perl, oder POSFIX oder welche Programmiersprache auch immer würde diese RegEx wahrscheinlich korrekt matchen, jedoch ging es darum, es nur theoretisch zu formulieren, aber ich gebe ja zu, dass ich das vielleicht nicht so rüberbringen konnte, ist ja auch ein ziemlich abstraktes Themengebiet, oder kann mir jemand so einen Automaten mal in natura zeigen, damit ich einen anfassen kann?

Also, sorry for that :-(

Es ist ja auch in der Praxis so, daß die Regex stark von dem vorgegebenen Regelwerk abhängig ist. DU kannst ja auch nicht jede in Perl funktionierende Regex in awk einsetzen, da das zugrundeliegende Regelwerk geändert wurde.

Schon klar, aber wie gesagt, es ging irgendwie ums Allgemeine mit den besagten Operatoren (,+,,*,und )

Solange Du Dir über das gesamte Regelwerk für eine zu verwendende Regex im Klaren bist, ist die Aufgabe auch nicht lösbar. Leider:-(

Ich könnte ja auch sagen:
[ steht für Anfang des Ausdrucks
] steht für Ende des Ausdrucks

für 1 oder mehr

{} für strukturelle zusammenfassung
, als Trennzeichen von Alternativen

daraus ergibt sich folgende Regex:
[{ac,bc,a,b}#]

lass'ma durchgehen ;-)

BTW.: Das Leerzeichen ist _kein_ gültiges Sprachelement in der von Dir ursprünglich vorgestellten Sprache.

Das Alphabet lautete: {a,b,c}* - was auch {} inkludiert ;-)

Aber wie du dir sicher denken kannst, saug ich mir das nicht aus den Fingern, es gibt da haufenweise mathematische Definitionen, was ein Zeichen, ein Wort, ein Satz, ... ist, aber da sind soviele Sonderzeichen (Vereinigungs- und Durchschnittsmengen, griech. Buchstaben, ...) enthalten, dass ich unmöglich hier alles posten kann! Allerdings muss ich sie lernen :-(

Ich hoffe dass ich es auch so halbwegs erklären konnte ;-)

liebe Grüsse
Bernhard

[Bernhard Peissl]

Hallo Klaus,

Ich hab da nicht ganz genau die Wahrheit gesagt ;-)

richtig heisst es:

Je nach dem was als nächstes unter dem Lesekopf steht, wird der Zustand abgefragt und eins weitergegangen, und wieder abgespeichert in der Kontrolleinheit. Wenn er also im Zustand q1 ein c einliest, geht er aufgrund der Regel (q1,c)->{q0} in den Zustand q0 über, dann liest er wieder was ein ... solange bis entweder:

<neu>

• das letzte Zeichen erreicht ist und der aktuelle Zustand ein Haltezustand ist, dann liefert der Automat zurück: Das Wort ist gültig! - wird akzeptiert.
• oder die Regel (qx, y+1) undef zurückliefert, dann bricht er ab mit der Meldung "Nicht akzeptiert!"

wobei x für den aktuellen Zustand steht, und y für das aktuell sich unter dem Lesekopf befindliche Zeichen !
</neu>

liebe Grüsse
Bernhard

[Klaus Mock]

Hallo,

Je nach dem was als nächstes unter dem Lesekopf steht, wird der Zustand abgefragt und eins weitergegangen, und wieder abgespeichert in der Kontrolleinheit. Wenn er also im Zustand q1 ein c einliest, geht er aufgrund der Regel (q1,c)->{q0} in den Zustand q0 über, dann liest er wieder was ein ... solange bis der Lesekopf entweder:

• das letzte Zeichen erreicht ist und der aktuelle Zustand ein Haltezustand ist, dann liefert der Automat zurück: Das Wort ist gültig! - wird akzeptiert.
• oder die Regel (qx, y+1) undef zurückliefert, dann bricht er ab mit der Meldung "Nicht akzeptiert!"

also doch (acbcab)*,oder vielleicht ((ab)(c))* ( a oder b gefolgt von einem c oder nichts und Aneinanderreihungen dieser Kombination). Wobei ich mir wiederum nicht sicher bin, ob (c) ein gültiges Konstrukt für die Regex ist.

»»

BTW.: Das Leerzeichen ist _kein_ gültiges Sprachelement in der von Dir ursprünglich vorgestellten Sprache.

Das Alphabet lautete: {a,b,c}* - was auch {} inkludiert ;-)

{} also kein Zeichen, aber das Leerzeichen ist ein Zeichen, also nicht Bestandteil des Alphabets. Ich hatte zwar schon vor längerer zeit Mathematik, und damals war Mengenlehre (jetzt habe ich doch glatt MEngenleere geschrieben, bevor ich mich ausbesserte, wird wohl eine freud'sche Fehlleistung gewesen sein *g*) noch nicht wirklich Thema, aber soviel hab ich, glaube ich, mitbekommen, daß ich sehen kann, welche Elemente in einer Menge vorhanden sind, und {a,b,c} ist nicht {a,b,c, }.

So, wenns jetzt noch nicht funktioniert, dann lass ich es besser, und denk darüber nach, ob ich nicht doch einmal auf der Uni vorbeisehen und endlich mit meinem Studium anfangen sollte. Bezeichnenderweise heißt die Studienrichtung 'Technische Mathematik'. Hmm, wenn ichs wirklich mache, dann muß ich mich wieder mit den Grundlagen herumschlagen. Vielleich kauf ich mir nächstens mal 'Mathematische System für Dummies' oder sowas. Das soll ja eine hervorragende Buchreihe sein ;-)

Grüße
  Klaus

[Bernhard Peissl]

Hallo Klaus,

Je nach dem was als nächstes unter dem Lesekopf steht, wird der Zustand abgefragt und eins weitergegangen, und wieder abgespeichert in der Kontrolleinheit. Wenn er also im Zustand q1 ein c einliest, geht er aufgrund der Regel (q1,c)->{q0} in den Zustand q0 über, dann liest er wieder was ein ... solange bis der Lesekopf entweder:

• das letzte Zeichen erreicht ist und der aktuelle Zustand ein Haltezustand ist, dann liefert der Automat zurück: Das Wort ist gültig! - wird akzeptiert.
• oder die Regel (qx, y+1) undef zurückliefert, dann bricht er ab mit der Meldung "Nicht akzeptiert!"

also doch (acbcab)*,

genau !

oder vielleicht ((ab)(c))* ( a oder b gefolgt von einem c oder nichts und Aneinanderreihungen dieser Kombination). Wobei ich mir wiederum nicht sicher bin, ob (c) ein gültiges Konstrukt für die Regex ist.

neeeeeiiiiiiiiiiiiinnnnnnnnnnn!!!!! aaaaaaaaahhhhhhhhhhhhhh ! ;-)

Das Alphabet lautete: {a,b,c}* - was auch {} inkludiert ;-)

{} also kein Zeichen, aber das Leerzeichen ist ein Zeichen, also nicht Bestandteil des Alphabets.

Leerzeichen != Leere Menge ;-)
aber es kann ja auch sein, dass ich mich nicht korrekt ausgedrückt habe ;-)

Ich hatte zwar schon vor längerer zeit Mathematik, und damals war Mengenlehre noch nicht wirklich Thema,

na sag mal, welcher Jahrgang bist denn du? Mengenlehre gibts doch schon seit, ... wart' mal ... Adam und Eva ???? ;-)

aber soviel hab ich, glaube ich, mitbekommen, daß ich sehen kann, welche Elemente in einer Menge vorhanden sind, und {a,b,c} ist nicht {a,b,c, }.

exactemento!

Es kann ein Zeichen vorkommen, muss aber nicht sein! Ist quasi definitionssache, wie in der Mathematik generell, Leere Menge in die Definition dazunehmen oder nicht? Hier ist sie eben dazugenommen!

So, wenns jetzt noch nicht funktioniert, dann lass ich es besser, und denk darüber nach, ob ich nicht doch einmal auf der Uni vorbeisehen und endlich mit meinem Studium anfangen sollte. Bezeichnenderweise heißt die Studienrichtung 'Technische Mathematik'.

Ein Freund von mir studiert 'techn. Physik in Linz', der ist noch nicht mal fertig, und hat schon die Wahl bei welcher Firma er später mal arbeiten will (Derzeitiger Favorit: Infineon -die Suchen massenhaft Techniker) - Gegen die Physiker (und auch Mathematiker) sind wir "Web-designer" ja nur Rohrspatzen ;-)

Also, studier was gscheites!

liebe Grüsse
Bernhard

[Klaus Mock]

Hallo,

also doch (acbcab)*,

genau !

na wunderbar:-))

Ich hatte zwar schon vor längerer zeit Mathematik, und damals war Mengenlehre noch nicht wirklich Thema,

na sag mal, welcher Jahrgang bist denn du? Mengenlehre gibts doch schon seit, ... wart' mal ... Adam und Eva ???? ;-)

Maturiert habe ich '81, Mathematik das letzte mal '80. Ich bin irgendwie immer 'durchgerutscht'. 1,2 Jahre nachdem ich die jeweilige Schulstufe absolviert hatte, wurde Mengelehre in den Lehrplan aufgenommen. Hätte doch wohl einige Jährchen wiederholen sollen ;-) So bin ich einer, der vor Adam und Eva rumgehangen ist :-(

[...] Gegen die Physiker (und auch Mathematiker) sind wir "Web-designer" ja nur Rohrspatzen ;-)

Naja, die Physiker verdienen auch nicht gerade sensationell, und interessante Arbeit gibt hier wie dort.
Mein wichtigstes Kriterium für die Wahl meiner Arbeit ist sicherlich, daß es Spaß machen muß und ich was dazulernen kann. Wenn diese Anforderungen nicht erfüllt sind, ist mir acuh die Kohle egal. Gottseidank ist es so, daß je besser ich bezahlt werde, desto eher kannst ich bestimmen, was ic mache. ICh hoffe, dieser Zustand hält noch länger an.

Grüße
  Klaus

[Björn Höhrmann]

also
»»  /^([ab]c?)+$/

Das könnte man übertragen etwa so formulieren oder?:

((ab)c*)+

Nein, dann erlaubst du beliebig viele 'c' nacheinander, also abccccccccccccccccc als Beispiel, das ist nicht erlaubt.

[Björn Höhrmann]

»»  /^([ab]c?)+$/

die Begrenzer (^ und $) brauchst Du, damit nicht z.B. 'zab' erkennst, wenn allerding vorher schon feststeht, daß es nur die gegebenen drei Zeichen im String gibt, dann kannst Du das auch weglassen.

Nein, /[ab]c?/ matched auf 'qqw12321ccyä#33‚cccccabccccc'.

[Linksetzer]

http://www.teamone.de/selfaktuell/forum/forumsfaq_2.htm#a1

[Bernhard Peissl]

Hi!

http://www.teamone.de/selfaktuell/forum/forumsfaq_2.htm#a1

Lass ihm ein bissi Zeit, der Thread ist ja ziemlich lang geworden!

• was ich nicht gedacht hätte *freu*

Ausserdem sieht seine Antwort <113413.html> nicht schlecht aus!

linke grüsse
Bernhard

[Björn Höhrmann]

http://www.teamone.de/selfaktuell/forum/forumsfaq_2.htm#a1

http://www.kirchwitz.de/~amk/dni/faq Punkt 13, Gebyy.

[Björn Höhrmann]

Also hier die Aufgabe:

Stellt euch vor ihr habt eine Sprache die sich aus nur drei Buchstaben zusammensetzt! Es geht also um eine Sprache aus dem Alphabet {a,b,c}*, WOBEI vor jedem 'c' zumindest ein 'a' oder 'b' stehen MUSS. Ansonsten Syntaxfehler ;-) Anders gesagt: Es kann kein c vorkommen, vor dem nicht entweder mindestens ein a oder b steht!

a,b oder c können dabei * ( >=0 ) mal vorkommen. Die Worte, die man mit dieser Sprache bilden kann, sollen durch einen regulären Ausdruck beschrieben werden.

Das würde bedeuten, dass auch "" ein gültiger Name wäre. Ich gehe mal davon aus, dass du das nicht möchtest, mein Ausdruck erfordert daher ein Zeichen. Wenn du das nicht möchtest, änder das '+' in ein '*'.

Mögliche Worte(Zeichenketten) sind z.b: aaa, abcabcc, ac, bcbbbb, ba, ... Keine Worte aus dieser Sprache wären: cabac, c, abccb

wenn 'abccb' ein gültiger Name ist, kann 'abcabcc' keiner sein, dort steht nämlich kein 'a' oder 'b' vor dem letzten 'c'.

Ihr seht, eine haarige Sache also, und gar nicht _soooo_ leicht.

Finde ich nicht:

/^    # string beginnt mit
(     # ein Konstrukt aus
[ab]c # c mit vorhergehenden 'a' oder 'b'
     # oder
[ab]  # 'a' oder 'b'
)+    # das ganze mind. 1 Mal
$/x   # string endet

while (<DATA>) {
  chomp;
  if (/^([ab]c[ab])+$/) {
    printf("%20s ist ok\n", $_);
  } else {
    printf("%20s ist ein FEHLER\n", $_);
  }
}
__DATA__
aaa
abcabcc
ac
bcbbbb
ba
cabac
c
abccb

gibt aus:

aaa ist ok
abcabcc ist ein FEHLER
     ac ist ok
bcbbbb ist ok
     ba ist ok
  cabac ist ein FEHLER
      c ist ein FEHLER
  abccb ist ein FEHLER

Ich empfehle:

Reguläre Ausdrücke -- Jeffrey E. F. Friedl -- ISBN: 3930673622
http://www.amazon.de/exec/obidos/ASIN/3930673622/081181081181

Ich lese dann mal die anderen Antworten...

[Bernhard Peissl]

Hallo Björn

a,b oder c können dabei * ( >=0 ) mal vorkommen. Die Worte, die man mit dieser Sprache bilden kann, sollen durch einen regulären Ausdruck beschrieben werden.

Das würde bedeuten, dass auch "" ein gültiger Name wäre. Ich gehe mal davon aus, dass du das nicht möchtest,

Doch, möcht ich ;-) Das gehört auch dazu, * also

mein Ausdruck erfordert daher ein Zeichen. Wenn du das nicht möchtest, änder das '+' in ein '*'.

Mögliche Worte(Zeichenketten) sind z.b: aaa, abcabcc, ac, bcbbbb, ba, ... Keine Worte aus dieser Sprache wären: cabac, c, abccb

wenn 'abccb' ein gültiger Name ist, kann 'abcabcc' keiner sein, dort steht nämlich kein 'a' oder 'b' vor dem letzten 'c'.

Ihr seht, eine haarige Sache also, und gar nicht _soooo_ leicht.

Finde ich nicht:

/^    # string beginnt mit
(     # ein Konstrukt aus
[ab]c # c mit vorhergehenden 'a' oder 'b'
     # oder
[ab]  # 'a' oder 'b'
)+    # das ganze mind. 1 Mal
$/x   # string endet

Also das schaut gut aus, ich hab ein bissl herumprobiert, und nix gefunden, aber ich will nix verschreien, mal abwarten ob jemand noch was findet, wo dein regex nicht hinhaut ;-(

umgeschrieben also (sorry, aber ich tu mir da einfach leichter)

((ab)c(ab))*

aaa ist ok
abcabcc ist ein FEHLER
     ac ist ok

»»  bcbbbb ist ok

ba ist ok
  cabac ist ein FEHLER
      c ist ein FEHLER
  abccb ist ein FEHLER

Unwiderlegbar!

Reguläre Ausdrücke -- Jeffrey E. F. Friedl -- ISBN: 3930673622

http://www.amazon.de/exec/obidos/ASIN/3930673622/081181081181

Wenn sich herausstellt dass deins stimmt, dann verspreche ich, mir ernsthaft zu überlegen, ob ich mir das Buch kaufen soll ;-)
Da würden einige hier wohl ziemlich aufatmen ;-)

Im Hinblick auf den Frieden im Forum verspreche ich hiemit bis Jahresende das perlre durchzuackern! ob was hängenbleibt sei dahingestellt, aber der Wille ist da :-)

liebe Grüsse
Bernhard

[Björn Höhrmann]

Das würde bedeuten, dass auch "" ein gültiger Name wäre. Ich gehe mal davon aus, dass du das nicht möchtest,

Doch, möcht ich ;-) Das gehört auch dazu, * also

/^    # string beginnt mit
(     # ein Konstrukt aus
[ab]c # c mit vorhergehenden 'a' oder 'b'
     # oder
[ab]  # 'a' oder 'b'
)+    # das ganze mind. 1 Mal
$/x   # string endet

Also das schaut gut aus, ich hab ein bissl herumprobiert, und nix gefunden, aber ich will nix verschreien, mal abwarten ob jemand noch was findet, wo dein regex nicht hinhaut ;-(

/^([ab]c?)*$/ ist natürlich funktional äquivalent zum gewünschten nur ggf. schwerer verständlich.

umgeschrieben also (sorry, aber ich tu mir da einfach leichter)

((ab)c(ab))*

Wenn dann /^((ab)c(ab))*$/

Reguläre Ausdrücke -- Jeffrey E. F. Friedl -- ISBN: 3930673622
http://www.amazon.de/exec/obidos/ASIN/3930673622/081181081181

Wenn sich herausstellt dass deins stimmt, dann verspreche ich, mir ernsthaft zu überlegen, ob ich mir das Buch kaufen soll ;-)

Solltest du, es lohnt sich.

[Bernhard Peissl]

Hallo Björn!

Ich geh jetzt aus der Deckung und verrat mal meinen besten Versuch:

(a*b*(a+c)*(b+c)*)*

was irgendwie zu deinem hinkommt, nur halt ein wenig komplizierter oder ?

liebe Grüsse
Bernhard

[AlexBausW]

Hallo Bernhard,

(a*b*(a+c)*(b+c)*)*

Hier kannst Du imho auch die + weglassen , da es im "Prinzip" und in etwa (acbcab)* entspricht, nur etwas anders geschrieben ;-) Allerdings benötigst Du wie immer die Anker ^ und $.

Gruß AlexBausW

Please visit my SELFvisitingcard @ http://www.atomic-eggs.com/selfspezial/daten/150.html

[Bernhard Peissl]

Hallo Alex,

(a*b*(a+c)*(b+c)*)*

Hier kannst Du imho auch die + weglassen , da es im "Prinzip" und in etwa (acbcab)* entspricht, nur etwas anders geschrieben ;-)

stimmt, warum fällt mir das erst jetzt auf ????

Allerdings benötigst Du wie immer die Anker ^ und $.

Also gut, hiemit akzeptiere ich neben Björns Version (/^((ab)c(ab))*$/) auch diese /^(abbcac)*$/, mit Dacherl, Dollar und Sahne oben drauf ;-) und die anderen waren natürlich auch nicht falsch, nur könnte ich das bei der Prüfung nicht so hinschreiben, obwohl's funktioniert ;-)

Natürlich übernehme ich keine Garantie obs auch wirklich richtig ist, ich sag nur "meines Wissens" stimmen die von euch eingebrachten Lösungen!

Nichtsdestotrotz muss ich gestehen, Björns Variante finde ich am elegeantesten!

Please visit my SELFvisitingcard @ http://www.atomic-eggs.com/selfspezial/daten/150.html

Was ich dich schon immer fragen wollte: Warum auf Englisch, die Leute, die in diesem Forum schreiben, sprechen doch alle ausschliesslich Deutsch, es sind also niemand hier anwesend der nicht der deutschen Sprache mächtigen ist ;-) oder hat das einen bestimmten Grund ?

liebe Grüsse
Bernhard

[AlexBausW]

Hallo Bernhard,

Was ich dich schon immer fragen wollte: Warum auf Englisch, die Leute, die in diesem Forum schreiben, sprechen doch alle ausschliesslich Deutsch, es sind also niemand hier anwesend der nicht der deutschen Sprache mächtigen ist ;-) oder hat das einen bestimmten Grund ?

Ja, ich fand das Wortspiel so toll ".._visit_ my _Selfvisting_..." ;-)) Sach bloß, Du findest das nicht lustig? ;-)

Gruß AlexBausW

Bitte besuche meine SELFVisiten-Karte auf http://www.atomic-eggs.com/selfspezial/daten/150.html
(wie langweilig ;-)

[Michael N.]

Hallo Bernhard,

Ich lerne gerade mit meinen Studienkollegen für eine Informatikprüfung (Theoretische Informatik - Automaten, Turingmaschinen), und dabei sind wir über eine ziemlich hundsteufelgemeine Frage gestolpert, die keiner von uns lösen kann, und sich hervorragend für ein kleines Rätsel eignet!

Ich hab mal im Archiv meiner grauen Zellen gekramt (aua), und mir ist dann auch wieder eingefallen (Achtung Geistesblitz) , mit welchem Buch ich mich damals auf die Prüfung Compilerbau / Theoretische Informatik am BIB in Bergisch-Galdbach http://www.bg.bib.de vorbereitet habe und dann erinnerte ich mich, daß auf dieses Buch ein Verweis im Internet ist unter http://www.alenfelder.com/Buecher/index.html. Vielleicht interessant für Dich.

Bis denndann

Michael N.

[Bernhard Peissl]

Hallo Michael,

Ich hab mal im Archiv meiner grauen Zellen gekramt (aua), und mir ist dann auch wieder eingefallen (Achtung Geistesblitz) , mit welchem Buch ich mich damals auf die Prüfung Compilerbau / Theoretische Informatik am BIB in Bergisch-Galdbach http://www.bg.bib.de vorbereitet habe und dann erinnerte ich mich, daß auf dieses Buch ein Verweis im Internet ist unter http://www.alenfelder.com/Buecher/index.html. Vielleicht interessant für Dich.

Danke für den Link, aber meine Prüfung ist morgen, und sogar übers Internet, würde es sich wahrscheinlich nicht mehr ausgehen, es rechtzeitig zu bekommen, geschweige denn es durchzulesen, Post bleibt halt Post, also langsam ;-)

Aber falls ich (nochmal) durchrasseln sollte werde ich mir bestimmt in diese Richtung was überlegen :-(

Gibt es eigentlich Foren wo Studenten sich zum Austausch treffen, und ihre "Rätsel" sich gegenseitig stellen, bzw. generell ein Forum wo auch solche Dinge besprochen werden?

Übrigens: Ich bin auch eine der grössten Verehrer von KISS wie du im Archiv nachlesen kannst ;-)

Liebe Grüsse
Bernhard