Reguläre Ausdrücke

[Kira_newbie]

Hey. ich brauche mal kurz eure Hilfe
ich muss einen regulären Ausruck angeben für: etwas das mit einem a beginnt, gefolgt von einer beliebig langen Folge von c
oder mit einer beliebig langen folge von b beginnt und mit c endet.
Alphabet a,b,c,

ich habs jetzt so gemacht:

a(c*) | (b*)c

aber ich weiß nicht, ob die klammern richtig gesetzt sind oder ob das * nicht hinter die klammer muss?

als 2. soll ich in natürlicher sprache folgendes wiedergeben:

(a|(aa)|(aaa))) ((bb)|(cc))))?-d*

ich würde sagen es heißt:
etwas das mit einem, zwei oder drei a´s beginnt (für was steht der Doppelpunkt?) optional mit bb oder cc weitergeht und mit einer beliebigen Anzahl d´s endet.


Beschreiben sie kontextrfrei eine Sprache, die zwar durch eine kontextfreie Grammatik, jedoch nicht durch einen regulären Ausdruck definiert werden kann. Begründen sie ihre Antwort.

Eine kontextfreie Grammatik ohne regulären Ausdruck? - sollen wir da was neues erfinden? mir fällt echt nichts ein.
Mir würde höchstens eine Reguläre Definition in den Sinn kommen?

LG Kira

 

[JavaHugo]

Zu 1

Am stärksten bindet der * dann erst die Konkatenation.Am schwächsten ist das "oder" ...

Von daher kannst Du die Klammern auch einfach weglassen.Zumindest so wie Du sie gesetzt hast sind sie überflüssig.

 

[HoaX]

Zu zweitens: Ein Doppelpunkt hat keine besondere Bedeutung, und auch den - hast du einfach so unterschlagen in deiner Beschreibung.

Und zur kontextfreien Grammatik: Ja, da sollst du dir selbst was ausdenken, da gibt es zig simple Möglichkeiten wenn man weiß worin die Unterschiede liegen.

 

[JavaHugo]

Beschreiben sie kontextrfrei eine Sprache, die zwar durch eine kontextfreie Grammatik, jedoch nicht durch einen regulären Ausdruck definiert werden kann. Begründen sie ihre Antwort.

z.B. die Sprache A^n B^n also die Sprache in der alle Wörter immer genau so viele As wie Bs haben ...

AABB,AAABBB,AAAABBBB wären z.B. Wörter dieser Sprache ... AABBB,ABBBB,AAAAAAB wären keine Wörter dieser Sprache ...

Diese Sprache ist kontextfrei aber nicht regulär.Man kann also eine kontextfrei Grammatik angeben die diese Sprache beschreibt aber keinen regulären Ausdruck.

Eine kontextfreie Grammatik ohne regulären Ausdruck? - sollen wir da was neues erfinden? mir fällt echt nichts ein.
Mir würde höchstens eine Reguläre Definition in den Sinn kommen?

Eine kontextfreie Grammatik kann mehr beschreiben als ein reguläre Ausdrücke (siehe Beispiel oben).
Du solltest Dir auf jeden Fall klar machen dass diese beiden Dinge nicht das selbe sind und es einen fundamentalen Unterschied gibt.(in regulären Ausdrücken kannst Du z.B. nicht vergleichen 'genau soviel "A"s wie "B"s da hast Du keinen Operator für ... in einer kontextfreien Grammatik kannst Du das realisieren indem Du auf den rechten Regelseiten immer gleich viele As und Bs hinzufügst .... s-> AsB usw.') ....

Allerdings gibt es bei den kontextfreien Grammatiken auch Grenzen ... z.B. ist a^n b^n c^n ...also alle Wörter die gleich viele As Bs Cs hat (AABBCC,AAABBBCCC.....) nicht kontextfrei.... Man kan keine kontextfreie Grammtik angeben die diese Sprache erzeugt (kann man mit dem sog. Pumping Lemma beweisen)....

Du könntest vielleicht mal nach "Chomsky-Hierarchie" googlen dann wird Dir der Zusammenhang zwischen diesen vielleicht klarer ...

 

[Kira_newbie]

okay. also wenn ich das richtig verstehe stimmt Aufgabe 1, wenn ich die Klammern weglasse.

okay. in Aufgane 2 zählt der strich - und der doppelpunkt : auch zum Alphabet.
heißt es dan :
es beginnt mit einem, zwei oder drei a´s, gefolgt von optional : bb oder : cc weiter geht es mit einem - und es endet mit einer beliebigen länge an d´s ?

(ein - und beliebig viele d´s oder auch beliebig viele striche?) *bindet ja am stärksten, also dürfte es sich nur auf das d beziehen und der strich ist nur einmal?

Zu Aufgabe 3: a^B ist doch auch regulär?

 

[JavaHugo]

Du müsstest uns erstmal erklären wie bei euch alle Zeichen definiert sind.

Wenn ihr z.B. die Klammern so benutzt wie man sie normalerweise benutzt dann ist das was da steht überhaupt kein regulärer Ausdruck ....

(a|(aa)|(aaa))) dieser Teil hat schon mehr schliessende Klammern als öffnende ...von daher ist das an der Stelle schon kein regulärer Ausdruck mehr und es gibt nichts was man ablesen könnte ...



"*bindet ja am stärksten, also dürfte es sich nur auf das d beziehen und der strich ist nur einmal?"

Ja.