Hallo. Ich hätte mal zwei Fragen zum neuen FGI Blatt zwei Fragen.

Auf welcher Seite/Folie befindet sich denn das "Verfahren aus der Vorlesung" (Aufgabe 11.1, Eliminierung von e-Produktionen). Gibt es in Vossen Witt etwas dazu?

11.2
Ich weiss, dass es höchste Zeit ist, aber ich kann immer noch nicht eindeutig diese mathematischen Notationen von Sprachen lesen.

L11.1 := {z element {0,1}*| |z|2 = |z|}

Ich würde es so lesen: das Wort z ist ein Element der Menge {0,1}* (kann also nur aus nullen, einsen oder epsilon bestehen). Den zweiten Teil verstehe ich nicht. Was ist |z|2 ? Heisst das, dass jedes Wort gleich lang sein muss? (wäre dann i anstatt der 2 nicht sinnvoller?) oder heisst es, dass nur das zweite Wort so lang sein muss wie das erste? (Welchen Sinn das machen würde kann ich auch nicht sagen).

L11.2 := {z element {1}{0,1}* | |z|2=|z|}
Hier denke ich: Wort z ist Element der Menge {1} konkateniert mit der Menge {0,1}* , also z.b. 1, 10 oder 11. Der zweite Teil genau wie oben.

Wäre das was ich lesen konnte korrekt? Was bedeutet der z Teil?
Ich will keine Lösungen/Lösungswege/-vorschläge o.ä. !

Wäre sehr dankbar, wenn das jemand (er)klären könnte.

Oh ich sehe schon dass das, was ich zu L11.1 geschrieben habe Bullshit ist. z kann natürlich aus nullen und einsen und epsilon bestehen (nicht oder :D).

Die Frage zu [z]2 = |z| bleibt. :(

[z]2 ist Kurzschreibweise für "Wert des Wortes, wenn es als Ziffernfolge im 2-er-Zahlensystem interpretiert wird."

Beispiel:  [0110]2 = [ 6]10, da die Binärziffernfolge 0110 dem Dezimalwert 6 entspricht.

Und woher weiß man, in welchem System die Basis dargestellt wird?

Und woher weiß man, in welchem System die Basis dargestellt wird?

allgemein gilt diese Notation [w]_b für b-näre Zahlendarstellungen, Also ist [w]_2 das für Binärzahlen!
Zu finden ist das im Skriptteil
<Turingmaschinen (korrigierte Version vom 24.06.09) (.pdf)>
siehe Webseite von TGI-1!
Dort findet man es auf Folien 9/10 in Def. 41.
(in der Vorlesung wurde auf einen gravierenden/dämlichen Fehler in der Definition hingewiesen!
Wer in der Vorlesung war, versteht besser worum es hier geht.)
Unterschied b-adisch zu b-när (2-adisch =dyadisch, 2-när = binär)!

ich hoffe, das hilft.

Der Witz ist, dass das b per Konvention dezimal ist, und nicht z.B. in derselben Basis wie w, sonst würde man ja immer 10 schreiben. 2 ist 10 in binär, 16 is 10 in hexadezimal etc.

Zu jeder Regulären Sprache kann man einen endlichen Automaten angeben. Gibt es für Kontextsensitive Sprachen also keinen endlichen Automaten? Oder: Wäre die Angabe eines endlichen Automaten ein Beweis für "Regulärität" ?

Du brauchst für kontextfreie Sprachen ja bereits einen Kellerautomat. Also kriegst Du kontextsensitive Sprachen erst recht nicht mit einem endlichen Automaten hin (falls damit das einfache Modell ohne Keller gemeint ist).

L11.1 := {z element {0,1}*| |z|2 = |z|} Soll nicht kontextfrei sein, aber akzeptiert der folgende endliche (sogar deterministische) Automat sie nicht?

http://img151.imageshack.us/img151/382/automat.png

ich verstehe deine Bezeichnung nicht ganz. Was soll "|z|2 = |z|" heißen? Aber der Automat, den du gezeichnet hast akzeptiert L={0,1}* ohne Zusatzbedingung.

Was soll "|z|2 = |z|" heißen?

Ich verstehe dass so, dass das Wort als Bitkette interpretiert gleich der Länge des Worts sein soll. Also zum Beispiel bilden die 4 (!) Bit 0100 den Wert 4.

Etwas weniger formal:
public class BeispielAutomat {     public static boolean akzeptiert(String wort)     {         return Integer.parseInt(wort, 2) == wort.length();     } } Etwas mehr funktional:
accept word = accept' word 0 0 where     accept' "" acc len = (acc == len)     accept' (x:xs) acc len = accept' xs (2*acc + digitToInt x) (len+1)

Das sollte natürlich [z]2 = |z| heissen, oben ist es falsch geschrieben und ich habe es nur kopiert.

Was meinst du mit Zustandsbedingung? Hat das nicht nur der Kellerautomat?

Zu jeder Regulären Sprache kann man einen endlichen Automaten angeben. Gibt es für Kontextsensitive Sprachen also keinen endlichen Automaten? Oder: Wäre die Angabe eines endlichen Automaten ein Beweis für "Regulärität" ?

Eine Sprache ist genau dann regulär, wenn sie
von einem endlichen Automaten akzeptiert wird.
Und da die regulären Sprachen eine Teilklasse
der kontextsensitiven Sprachen bilden, gibt es
auch kontextsensitive Sprachen, die von einem
EA akzeptiert werden. Aber es gibt auch welche,
die nicht regulär sind und daher nicht von einem
EA akzeptiert werden.

Nach Definition ist die Angabe eines endlichen
Automaten ein Beweis dafür, dass die Sprache
regulär ist.

Der Automat den du gezeichnet hast akzeptiert z. B. das Wort 11 aber |11| = 2 und [11]_2 = 3. Das heißt das Wort 11 ist nicht in der Sprache. Der Automat akzeptiert also mehr als in der Sprache L11.1 enthalten ist.

Hallo,

auch ich habe eine Frage zu 11.2 d)
L11.1 := {z element {0, 1}∗ | [z]2 = |z|}

Der Tipp der da unten im Kasten steht

Da beim Verdoppeln der Teilwörter v und x immer irgendwelche Binärzahlen
entstehen, ist es günstig, sich auf spezielle Formen und Darstellungen der Zahlen
zu beschränken. Bilden Sie also den Durchschnitt C := L11.1 AND {0}∗{1}∗ oder mit
einer ähnlichen regulären Menge. Falls L11.1 kontextfrei ist, wäre dann auch die
neue Sprache

Was genau soll mir der Durchschnitt bringen? Und wie bilde ich ihn, in diesem Zusammenhang. Bitwise And verknüpfen? Hat jemand ein Beispiel, was nicht unbedingt Teil der Lösung ist? Ich wäre sehr dankbar.

Gruß

der durchschnitt beider sprachen wäre ja eine sprache, die alle wörter aus beiden sprachen enthält. Wenn du zum Beispiel Sprache1 = {z \in irgendwas | Bedingung1}
Sprache2 = {z \in irgendwas | Bedingung2}

müsste jedes Element deiner neuen Sprache beide Bedingungen erfüllen
also
Sprache1 geschnitten mit Sprach2 = {t \in irgendwas | Bedingung1 und Bedingung2}
das AND in dem hinweis heißt dann wohl einfach nur, dass man den Durchschnitt der Sprachen bilden soll und hat nichts mit bitweisem und zu tun (meine Vermutung)

An einem konkreten Beispiel

Ist L1 = {z \in {a,b,c} | |a| = |b| = |c|} kontextfrei? Wenn ja müsste es ja geschnitten mit einer regulären Sprache wieder eine kontextfreie Sprache ergeben. Nehmen wir mal L2 = {a}*{b}*{c}* (Die Sprache ist regulär).
Wenn man nun den durchschnitt der Sprachen bildet muss ja zum einen |a|=|b|=|c| (von L1) gelten und zum anderen muss die Reihenfolge so sein wie in L2 (also alle a's vor b' und alle b's vor den c's) und das erfüllt nur die Sprache L3 = {a^nb^nc^n} und die ist ja ein paradebeispiel für eine nicht-kontextfreie Sprache (kann man mit dem uvwxy-Theorem nachweisen). Also ist L1 auch nicht kontextfrei.

Ich hoffe das war verständlich…

super!danke. aber wie genau soll mir das helfen?

wenn ich die L11.1 mit  {0}*{1}* vereinige bekomme ich 0^n 1^n ? aber das ist doch eine kontext freie sprache. scheinbar habe ich immer noch einen denkfehler.

jemand einen tipp? :)

nicht vereinigen, sondern den durchschnitt bilden… das ist ein gewaltiger unterschied!

L11.1 mit {0}*{1}* ist auch nicht 0^n 1^n sondern L = { 0^n 1^n | [z]2 = |z| }

Inwiefern dir das aber für deine Aufgabe hilft kann ich dir spontan nicht sagen.

…. ich kanns dir doch sagen

In der Aufgabe steht, du sollst das uvwxy-Theorem benutzen und den Durchschnitt nur als Hilfe benutzen.
Wenn L11.1 kontextfrei ist, dann müsste ja auch die durchschnittsprache kontextfrei sein. Wenn du nun also mit dem uvwxy-Theorem zeigst, dass die durchschnittsprache nicht kontextfrei ist bedeuetet das, dass L11.1 auch nicht kontextfrei ist.

tut mir leid. meine wort gewandtheit auf dem gebiet ist etwas schwach. du hast natürlich recht.

nun soll ich aber Zeigen, dass L = { 0^n 1^n | [z]2 = |z| } nicht kontextfrei ist. Mein problem ist hier: 0^n1^n ist kontextfrei :D das einzige was mir bleibt ist also zu zeigen, dass nicht alle Wörter die Bedingung erfüllen. Reicht das, oder was genau will mein Übungsleiter dann sehen?

Vielen Dank soweit. Super schnelle und gute Hilfe,danke

0^n 1^n ist imo falsch. das würde ja bedeuten, dass genauso viele 0 wie 1 vorkommen.
MfG

Bei mir fällt die vermeintlich reguläre Sprache L11.2 auch durch das Pumping Lemma. o.O

Der Automat, der sie akzeptiert darf ja keine Schleife haben. Ich bin sehr verwirrt.

die sprache L11.2 akzeptiert wenn ich mich nicht irre nur 2 worte.

jupp bei mir auch nur 2 ;)

Ja genau, bei mir eben auch. Deswegen fällt sie auch durch das Pumping Lemma, weil es keinen mittleren Teil gibt den man aufpumpen könnte ohne dass das Wort plötzlich nicht mehr in der Sprache wäre.

Was nützt das Pumping Lemma also, wenn es mal so und mal so ist? Dass eine Sprache es nicht erfüllt heisst also garnicht unbedingt, dass diese nicht regulär ist sondern sie könnte auch nur irgend ein Sonderfall sein.

Es fällt mir schwer L11.1 durch das uvwxy-Theorem als nicht kontextfrei hinzustellen weil die reguläre Sprache L11.2 durch dieselben Kriterien durchfallen würde.

Ah, nvm. Habe die Antwort auf dieses "Problem" bereits selbst bei Wiki gefunden.

"Falls L endlich ist, so existiert eine obere Schranke für die Länge der Wörter aus L. Es existiert also eine natürliche Zahl n ∈ N, für die gilt: |x| < n ∀ x ∈ L. Umgekehrt gilt, dass die Menge aller Wörter aus L, die mindestens die Länge n haben, eine leere Menge ist: L' := {x ∈ L | |x| ≥ n} = ø. Da für leere Mengen Aussagen der Form „für alle Elemente der Menge gilt…“ trivialerweise immer erfüllt sind, ist auch die Behauptung für dieses n trivialerweise erfüllt. Das Pumping-Lemma ist also trivial, falls L endlich ist."

Zum Thema passend habe ich heute nacht noch eine Anfrage per Mail bekommen, die ich mal zusammen mit meiner Antwort poste.  Vielleicht klärt das ja noch einige offene Fragen:

Zu meinem Problem:
L11.1 := {z element {0,1}* | [z]_2 = |z|}
Es ist schwierig hier das PL anzuwenden. Daher errechne ich den Durchschnitt:
C:= L11.1 AND {0}*{1}*
Dadurch erhalte ich eine Sprache, die sowohl die Bedingung von  L11.1 als auch die Reihenfolge von der andren Menge hat (erst  Nullen, dann die Einsen).
Damit komme ich zu einer Menge: 0^n 1^m   (soweit richtiger  Gedankengang?)

Ja, soweit ist der Hinweis aus der Aufgabenstellung richtig umgesetzt.

Und nun bin ich verloren. In der Vorlesung und in vielerlei Büchern finde ich nur Aufgaben der Form: a^n b^n c^n (also mit 3 Basen).   HIer habe ich aber nur 2. Kann man trotzdem zeigen, dass es nicht kontextfrei ist? Die einzige Möglichkeit, die mir da einfiele, wäre es mit der Bedingung von L11.1 zu argumentieren! Ist das zulässig und ausreichend?

Natürlich muss die Bedingung von L11.1 mit genutzt werden.  Dass die Sprache nicht kontextfrei ist, liegt an dem bestimmten Verhältnis von  n zu m, welches in der Sprache L' = { 0^n1^m | n = m … } gilt.  Die drei Punkte sind hier durch mathematische Operationen zu ersetzen, welche das Verhältnis genau beschreiben.  Und dieses Verhältnis ergibt sich durch die Bedingung aus L11.1.  Da das Herausfinden dieses Verhältnisses Teil der Aufgabenstellung ist, kann ich es leider nicht verraten. :-)

Sobald Du das Verhältnis kennst, kannst Du für die Sprache L' den üblichen Weg des Pumping-Lemma-Widerspruchsbeweises gehen (geeignetes Wort wählen, alle Zerlegungen aufzählen, jede Zerlegung ausschließen).  Mit dem Hinweis aus der Aufgabenstellung gilt dann unmittelbar, dass, wenn L' nicht kontextfrei ist, auch L11.1 nicht  kontextfrei sein kann.
(Edit: Tippfehlerkorrektur)

Was auch oft zu Aha-erlebnissen führen kann, ist das Aufschreiben auch längerer Wörter aus der Sprache, die alle die Form 0^n1^m haben! Deren Länge ist ja offensichtlich immer n+m, aber die Zahlen die durch diese Binärzahlen dargestellt werden sind dann immer hübsch daneben zu schreiben; etwa so:

Wort         | Länge | Zahl

10            |  2   |  2        nicht in L \cap 0^*1^*
011          |  3   |  3         in L \cap  0^*1^*
0100         |  4   | 4         nicht in L \cap  0^*1^*
00101       |  5   | 5          nicht in L \cap  0^*1^*
000110     |  6   |  6         nicht in L \cap  0^*1^*
0000111    | 7    | 7          in L \cap  0^*1^*
…            | … | …          alles nicht in L \cap  0^*1^*
000000000001111  | 15 | 15          in L \cap  0^*1^*

na, dämmert's

obv

obv

Was heißt dass denn?
hier: <Definitions of Web Jargon Terms from Internet Connection> fand ich es nicht.
oder soll das als "ohne besondere Verwendung" gelesen werden????

Oder ist es nicht zu sehen, dass die Zahl n der Nullen exponentiell genüber der der Einsen wächst…?

"obviously" wäre mein Tipp.

ja meiner auch :D

Meiner nicht >:(

ja ich meinte damit, dass die nullen für den wert der binärzahl offensichtlich "ohne besondere Verwendung" sind…
mfg

Wieviele FGI Blätter wirds eigentlich insgesamt geben?

FGI SoSe 09
13 obv

FGI SoSe 09
13 obv

Ja, es gibt das 13. Blattt, nur steht der Link noch nicht auf der Seite von FGI (s.o.).
Blatt 13 enthält eine nicht zu schwere Bonusaufgabe mit 4 Punkten.
Insgesamt werden es 155 Punkte (ohne alle Bonuspunkt) sein,
von denen (etwa!) 50% erreicht worden sein sollten.
In der Vorlesung wurde dazu, so weit ich mich erinnere, etwas Genaueres gesagt.