FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI 1 Blatt 2 Aufgabe 2.2

FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 20:23
Anonymer User
Hi,

könnte mir ma bitte jemand sagen was genau ich da machen muss?

Übungsaufgabe 2.2 : (Definition einer Sprache)

Die Standards für die Passwörter p des studentischen Verwaltungssystems SVS lauten:
• p enthält mindestens 4 und höchstens 6 Zeichen.
• p enthält mindestens zwei Ziffern.
• p enthält mindestens einen direkten Wechsel von Klein- auf Großbuchstabe (z.B. aB).
Beschreiben Sie die Menge der Zeichenketten, die die genannten Standards erfüllen.

Lösungsansatz:

soll ich mit Konkatenationen die möglichen wörter aus Zeichenmengen beschreiben( wie kann ich dann beachten an welcher stelle die zahlen stehen? sie können ja überall vorkommen) oder soll das durch Ableitungen und Grammatiken hergeleitet werden?

Sorry, ich steh komplett auf dem Schlauch.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:06
doodles
Hallo,

hier muss keine Grammatik benutzt werden. Es sollen Mengen angegeben werden.

Wenn zum Beispiel die Aufgabe wäre "das Passwort muss eine 5 und eine 7 enthalten" könnte die Menge z. B. folgendermaßen aussehen L = {a*5a*7a* | a element aus Sigma} vereinigt mit {a*7a*5a* | a element aus Sigma}. Nun musst du für die gesuchte Sprache aber alle drei Bedingungen einbauen und sehen, wie du eine Menge zusammenbaust, in der nur Wörter enthalten sind, die alle drei Bedingungen erfüllen.

Gruß
Doodles

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:09
Wulf
Ich find das ja nicht nett, dass SVS mit solch schwachen Passwörtern in Verbindung gebracht wird!

Es gibt natürlich mehrere Arten, so eine Sprache zu beschreiben. Zum Beispiel als regulärer Ausdruck (ist die Sprache überhaupt regulär?), als kontextfreie Grammatik (ist sie kontextfrei?) oder der (hoffentlich) aus der Schule bekannten Mengenschreibweise. L = { abcdef | a Ziffer oder b Ziffer }.

Zur Übung solltest du einfach mal alle 3 Wege nehmen, soweit der Stoff schon drankam und es überhaupt möglich ist. Ich weiß leider nicht, welcher der "richtige" ist.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:14
doodles
Die Mengenschreibweise sollte am einfachsten sein. Die anderen Sachen sind aber natürlich (abhängig von den Bedingungen regulär/kontextfrei) auch möglich.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:23
T4Y
Ist wirklich eine kontextfreie Grammatik konstruierbar? (Die 3. Bedingung ist doch kontextgebunden)

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:33
doodles
Eine kontextfreie Grammatik ist natürlich nur konstruierbar, wenn die Sprache auch kontextfrei ist. Wenn die 3. Bedingung kontextgebunden ist, ist sie das wohl nicht. Deswegen schrieb ich "abhängig von den Bedingungen".

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:38
T4Y
Achso, ok. Dein Einschub schien mir kontextgebunden (an die Aufgabe). [10]

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:48
Anonymer User
@doodles:

dein beispiel ist ja schon mal nicht schlecht, aber für mich wird daraus nur ersichtlich, dass es 2 definierten stellen 5 und 7 bzw 7 und 5 sein muss. wie aber kann ich jetzt sagen dass an jeder beliebigen stelle eine Zahl, ein kl. oder gr. buchstabe stehen soll und es mindestens 2 zahlen sein müssen?

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 21:55
T4Y
Guck mal im Skript nach, wie Sprachen beschrieben werden. Insbesondere bei den kfG's und Kapitel 1, Folien 8, 16, 17.
Für die 2 Zahlen kannst du ja z.B. eine Variable n wählen mit n >= 2. Das musst du dann nur noch an die richtige Stelle packen. Guck dir mal obige Folien an und lass dich von den formalen Beschreibungen inspirieren.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 22:18
Loom
[…], dass es 2 definierten stellen 5 und 7 bzw 7 und 5 sein muss. wie aber kann ich jetzt sagen dass an jeder beliebigen stelle […]
Doodles Beispiel ist gerade dafür, dass an beliebiger Stelle eine 5 oder 7 sein kann. Wichtig ist hierbei der Stern (*). Er besagt, dass a beliebig oft vorkommen darf (null bis unendlich (bei endlichen Sprachen wohl nicht ;)).
Da steht
a*5a*7a*
und heißt
belibieg oft a, dann eine 5 gefolgt von beliebig of a eine 7 und beliebig oft a.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 22:43
theorinix
Ist wirklich eine kontextfreie Grammatik konstruierbar? (Die 3. Bedingung ist doch kontextgebunden)

Da die Menge sogar regulär ist sollte ein regulärer Ausdruck dafür möglich sein! (Beweis dafür durch die Angabe eines regulären Ausdrucks, einer einseitig linearen kontextfreien Grammatik oder eines endlichen Automaten! Das kommt alles noch wesentlich ausführlicher dann im Teil nach den Pfingstferien, hier geht es um die eindeutige und vollständige Spezifikation der Menge solcher - zugegeben absichtlich simplen - Passwörter),
Die diversen Tipps hier (T4Y und @doodles) sollten gut helfen können.

RE: FGI 1 Blatt 2 Aufgabe 2.2 2010-04-19 23:25
Wulf
Die Wortlänge ist begrenzt (6 Zeichen) und wenn man von einem endlichen Alphabet, z. B. {"Ziffer", "Großbuchstabe", "Kleinbuchstabe", "anderes"} ausgeht, ist die Menge der Wörter in der Sprache endlich; damit ist die Sprache automatisch regulär, kontextfrei, etc. Aber ich glaube auch, dass die Mengenschreibweise bei weitem einfacher ist.