Formale Sprachen und Automaten

[Barill]

Ich habe ein Übungsblatt und komme einfach nicht weiter. Ich muss dieses Übungsblatt aber auf alle Fälle vollständig machen.

Wäre euch sehr dankbar wenn mir jemand helfen könnte und gewisse Hilfestellungen und Lösungen geben könnte.

Vielen Dank euch

Gegeben sei das Alphabet sum() = {0,1}, sowie L_1 = {0, 00, 000}

und L_2 = {0, 1, 01}.

Für welche Sprachen stehen die folgenden Ausdrücke:

a) L_1*L_2

Mein Ergebnis:

= {00, 01, 001, 000, 0001, 0000, 00001}

c)

L_1^C

Wie bilde ich den das Komplement einer Sprache?

d)

L_1^x (x steht eigentlich für den Stern, also Kleene)

Meine Lösung:

vereinigung(L_1^i,i=0,\inf)

e)

\0^x (x steht für Stern, Kleene)

Meine Lösung:

= {\0}

2.Aufgabe ____________

Geben sie eine induktive Definition an für die Wortumkehr w^R

Wie mache ich dies. Wir haben bisher eine Induktion gemacht aber irgendwie find ich keine Parallele

4. Aufgabe___________

Gegeben sei das Alphabet sum() = {0,1,#)

a)

Wieviele verschiedene Wörter mit der Länge n gibt es?

Meine Lösung:

3^n

Wieviele verschiedene Wörter der Länge n gibt es, in denen ein Symbol

c element von sum() genau k-mal vorkommt?

Ich habe irgendwie alle kombis aufgeschrieben aber finde keine Gleichung

c)Wie viele verschiedene Wörter der Länge n gibt es, in denen ein Symbol c element von sum() mindestens k-mal vorkommt?

[flashpixx]

Hallo,

ich hab' zwar etwas Probleme mit der Schreibweise weil z.B. das sum ja eigentlich ein Sigma ist und keine Summe, aber egal.

Ich kann Dir nur dringend raten es selbstständig zu lernen, denn sonst verstehst Du das nicht. Zusätzlich gilt hier auch die Bemerkung, dass wenn es für Dich wichtig ist, noch lange nicht für die Community dringend ist.

a) L_1*L_2

* sind meines Wissens alle möglichen Kombinationen der Wört aus den beiden Sprachen L1 und L2. * ist für mich die Konkatination (assoziativ), somit gilt L1*L2 = L2*L1

c)

L_1^C

Wie bilde ich den das Komplement einer Sprache?

Es muss gelten L1 * L1^c = {}

d)

L_1^x (x steht eigentlich für den Stern, also Kleene)

Der Kleene Stern ist eine Sprache L ist L* = Vereinigung mit i >= 0 über L^i

e)

\0^x (x steht für Stern, Kleene)

was ist \0 ? Ist das Epsilon, das leere Wort? Wenn ja, dann überlege Dir, ob es überhaupt so möglich ist, denn das Epsilon kommt in deinem Alphabet (Sigma) nicht vor (siehe oben die Def. von sum). Falls es doch gültig ist, dann überlege Dir, was es genau bedeutet, wenn Du den Kleene-Abschluss über einem leeren Wort (also epsilon hoch *) nimmst (Achtung nicht zu verwechseln mit der leeren Menge)

Gegeben sei das Alphabet sum() = {0,1,#)

a)

Wieviele verschiedene Wörter mit der Länge n gibt es?

Meine Lösung:

3^n

Eine Begründung wäre nicht schlecht, bzw ggf formal Beweisen (Tipp Induktion von n -> n-1)

HTH

Phil

P.S. an den Rest setze ich mich ggf später