Sind so tolle Sachen wie der Epsilon-FA, den ich irgendwie sinnlos finde.. Klausurrelevant?

Sind so tolle Sachen wie der Epsilon-FA, den ich irgendwie sinnlos finde.. Klausurrelevant?

Warum denn nicht?

Mhh ich nötige mal diesen leeren Thread für eine Aufgabe:

ISBN-Nummern sind alle Folgen x_1 …x_10 der Länge 10 über dem Alphabet { 0,1,…,9,X } die genau folgende Eigenschaften erfüllen:

(1) x_i Element aus {0,1,…,9 } , 1 <=i<=9: Die ersten 9 Ziffern dürfen nicht X sein.
(2) x_10 Element aus {0,1,…,9,X}: x_10 kan auch X sein. X steht für die Ziffer 10.
(3) Es muss \Sigma_von_i=1_bis_10 i*x_i = 0 mod 11 gelten: Die Summe der mit der Stelle gewichteteten Ziffern muss durch 11 teilbar sein.

Konstruieren Sie einen endlichen Automaten, der gerade die ISBN-Nummern akzeptiert.


So steht die Aufgabe im Vossen & Witt( S. 56 Übung 2.4)

Mein Ansatz ist etwas aufwändig(naiv?) : Erstmal brauchen wir mindestens 10 Zustände um die Bedingung (1) (die ersten 9 Ziffern dürfen nicht X sein) abzutesten. Dann bei jedem Zustandswechsel den aktuellen Rest modolu 11 berechnen(Gewichtung mitbeachten), d.h. für jeden Zustand gibt es 10 Folgezustände(wegen 10 Restklassen). Am Ende müsste dann rauskommen ob der Rest 0 ist , und nur dann wird akzeptiert.
Ist aber ein wenig aufwändig wegen der Anzahl der Zustände(10^10 +1?) ;)

Warum ich das hier poste? Weil Vossen & Witt leider keine Lösungen bereitstellt. Kennt einer einen Link zu Lösungen? Oder hat einer Lust und Laune die Aufgabe mal selbst zu knacken?

Wäre dankbar für nen hilfreichen Tipp um die Aufgabe effizienter zu lösen…

Mhh ich nötige mal diesen leeren Thread für eine Aufgabe:

ISBN-Nummern sind alle Folgen x_1 …x_10 der Länge 10 über dem Alphabet { 0,1,…,9,X } die genau folgende Eigenschaften erfüllen:

(1) x_i Element aus {0,1,…,9 } , 1 <=i<=9: Die ersten 9 Ziffern dürfen nicht X sein.
(2) x_10 Element aus {0,1,…,9,X}: x_10 kan auch X sein. X steht für die Ziffer 10.
(3) Es muss \Sigma_von_i=1_bis_10 i*x_i = 0 mod 11 gelten: Die Summe der mit der Stelle gewichteteten Ziffern muss durch 11 teilbar sein.

Konstruieren Sie einen endlichen Automaten, der gerade die ISBN-Nummern akzeptiert.


So steht die Aufgabe im Vossen & Witt( S. 56 Übung 2.4)

Mein Ansatz ist etwas aufwändig(naiv?) : Erstmal brauchen wir mindestens 10 Zustände um die Bedingung (1) (die ersten 9 Ziffern dürfen nicht X sein) abzutesten. Dann bei jedem Zustandswechsel den aktuellen Rest modolu 11 berechnen(Gewichtung mitbeachten), d.h. für jeden Zustand gibt es 10 Folgezustände(wegen 10 Restklassen). Am Ende müsste dann rauskommen ob der Rest 0 ist , und nur dann wird akzeptiert.
Ist aber ein wenig aufwändig wegen  der Anzahl der Zustände(10^10 +1?) ;)

Warum ich das hier poste? Weil Vossen & Witt leider keine Lösungen bereitstellt. Kennt einer einen Link zu Lösungen? Oder hat einer Lust und Laune die Aufgabe mal selbst zu knacken?

Wäre dankbar für nen hilfreichen Tipp um die Aufgabe effizienter zu lösen…

Nö, naiv ist das nicht, denn bis 10 zählen muss man ja ohnehin schon wegen der Anzahl der Symbole.
Das sind bei mir 11 Zustände. Und das mit den Restklassen passt ja auch ganz gut.
Wie man nun Zustände sparen kann (d.h. mehrfach verwenden), ist eher Trickserei,
wenn man nicht auf 10*10 = 100 (wieso denn 10^10=10000000000?) kommen möchte.
Aber mit 100 (oder 101, so genau sehe ich das jetzt im Kopf nicht) sollte es immer gehen.
Das könnte ja auch gut "parametrisiert" notiert werden (bitte kein Zustandsdiagramm malen…)!
Oder?
Hab' gerade wenig Zeit für Genaueres hinsehen.

Stimmt man kann das ja auch anders notieren (hatte nur Zustandsdiagramme im Kopf) ;)

Mhh also 10^10 ist vielleicht falsch.
Im Grunde wird ja ein Baum aufgespannt, also aus dem ersten Zustand gibt es 10 Folgezustände(wegen 10 Restklassen). Dann aus jedem Folgezustand wieder 10 Restklassen usw.
Müssten also doch eigentlich mehr als 10*10 sein…

Mhh müssten doch dann eigentlich 10^1 + 10^2 + … + 10^10 + 1
wobei die letzte 1 der Startzustand ist, Zustände sein.
Ist doch Beim Binärbaum zB auch so.
|
| |
| | | |

Das sind 2^0 + 2^1 + 2^2 Zustände.

Das sind 2^0  + 2^1 + 2^2 Zustände.

Eher [latex]$\sum\limits_{i=0}^{10}2^i = 2^{11} - 1$ [/latex]

Aber ich schaue morgen mal wieder rein…

Also ich komm auf 22 Zustaende: 11 zum "normalen" zaehlen, 11 fuer die letzte Ziffer. Von den letzteren ist einer Endzustand, die anderen 10 eben nicht.

*edit* Achso, Laenge 10, hatte ich ueberlesen. Dann halt ~110 Zustaende in einer 11x10-Matrix angeordnet. Viel weniger wird aber nicht gehen.

Hab jetzt mal was gebastelt.

delta(q_0,a) = q_1_i für a Element aus {1,…,9} und a mod 11 = i

delta(q_j_i,a) = q_(j+1)_k für a Element aus {1,…,9} ; j Element aus {1,…,8 }; i Element aus {0,…,10} und (j+1)*a + i mod 11 = k

delta( q_9_i, a ) = q_fin falls a Element aus {1,…,9,X}; i Element aus {0,…,10} und 10*a + i mod 11 = 0

q_fin ist Endzustand. delta meint die Überführungsfunktion.
Müsste so doch klappen, oder?

Hab jetzt mal was gebastelt.

delta(q_0,a) = q_1_i für a Element aus {1,…,9} und a mod 11 = i

delta(q_j_i,a) = q_(j+1)_k für a Element aus {1,…,9} ; j Element aus {1,…,8 }; i Element aus {0,…,10} und (j+1)*a + i mod 11 = k

delta( q_9_i, a ) = q_fin falls  a Element aus {1,…,9,X}; i Element aus {0,…,10} und 10*a + i  mod 11 = 0

q_fin ist Endzustand. delta meint die Überführungsfunktion.
Müsste so doch klappen, oder?

Das sieht schon ziemlich gut aus, nur scheint mir dies hier unten richtiger (statt der ersten beiden Definitions-Zeilen für das \delta()…)
j gibt an, wie viele Symbole schon gelesen wurden. Und wenn i der Rest mod 11 der bisherigen Summe (= Summe der ersten Ziffern bis zur j-ten) war,
so ist a+i mod 11 der Rest von (1o*bisherige Summe plus a) mod 11!
10*a+i mod 11 ist nicht richtig, denn a ist ja nur die nächste Ziffer (warum diese *10?) und nicht die bisherige Summe.
Also dies plus der letzte Übergang mit a in {0,…9,X}:

[latex]$\delta(q_{j_i},a) := q_{{j+1}_{k}}$ [/latex] für [latex]$0\leq a\leq 9, 0\leq j \leq 9, k\equiv a+i \mod 11$
[/latex]

Entsprechend auch der letzte Übergang in q_{fin}…
oder hab' ich mich nun vertan?
(Probiere ein Beispiel mit ISBN_Nummer der Länge 3, dann sieht man's leichter.
So das wars von mir.
viel Glück. (Für Klausurfragen wäre so etwas aber wahrscheinlich eh' zu umständlich…)

Habe ne andere Aufgabe.

L= { a^p : p ist Primzahl } .

Zeigen sie dass L nicht kontextfrei ist.

Mir fälllt da nichts konstruktives ein. Mein Lösungsansatz wäre über das Pumping-Lemma und dann Wort a^p mit p ist Primzahl und p>= n (n ist die Zahl, für die das Pumping-Lemma gelten soll).
vwx darf ja maximal aus n a's bestehen. D.h. ich kann zB a^(p+n) (wenn ich hochpumpe) usw. bilden. Nur mir fehlt da jetzt keine Bedingung ein, wann dann p+n oder p+n^2 usw. keine Primzahl mehr ist.

Hat einer eine Idee?

Habe ne andere Aufgabe.

L= { a^p : p ist Primzahl } .

Zeigen sie dass L nicht kontextfrei ist.

Mir fälllt da nichts konstruktives ein. Mein Lösungsansatz wäre über das Pumping-Lemma und dann Wort a^p mit p ist Primzahl und p>= n (n ist die Zahl, für die das Pumping-Lemma gelten soll).
vwx darf ja maximal aus n a's bestehen. D.h. ich kann zB a^(p+n) (wenn ich hochpumpe) usw. bilden. Nur mir fehlt da jetzt keine Bedingung ein, wann dann p+n oder p+n^2 usw. keine Primzahl mehr ist.

Hat einer eine Idee?

Na ja, die neuen Wörter, die man bekommt sehen doch alle so aus: [latex]a^{(p-k)+i\cdot k}[/latex], wobei k die Länge des Teils v ist, der ja weggelassen oder beliebig hochgepumpt werden darf.
Da wir über k nicht mehr wissen, als 1≤k≤n (n die Zahl aus dem Pumping-Lemma),
müssen wir i so wählen dass die Zahl  (p-k)+i\cdot k garantiert ein Produkt zweier Zahlen wird!
Das sollte doch so schwer nicht zu finden sein, gell? Die Auflösung des Rätsels lasse ich jetzt aber weg…

Jo danke Theorenix, ich hatte gedacht dass beim hochpumpen die Anzahl exponentiell wächst, also immer +n^2 + n^3, das stimmt ja aber nicht weil man ja i*n hochpumpt.
Mhh hatte mir jetzt eine einbisschen komplizierte Lösung des Rätsels überlegt.
Also, da p ja eine Primzahl ist, ist die Menge Zp (ganze Zahlen modolu p) mit der Verknüpfung + eine Gruppe. Sogar eine zyklische Gruppe(da die Gruppenordnung eine Primzahl ist, und die Ordnung jedes Elements ja ein Teiler von der Gruppenordnung sein muss).
k ist dann ja ein element der Gruppe. Es muss dann eine Zahl i*k geben mit i*k mod p = 0 , da ja k ein Element der Gruppe ist und da die Gruppe zyklisch ist, jedes Element der Gruppe durch Potenzieren(indem Fall entspricht potentieren multiplizieren, weil die Gruppenoperation + ist) von k erzeugt wird.
Dann wählen wir i also so, dass i*k mod p = 0 gilt.
Die Zahl a^(p + i*k) müsste durch hochpumpen ja auch in der Sprache sein. Allerdings gilt p mod p = 0 und i*k mod p = 0 und somit p+i*k mod p = 0 und damit ist p + i*k durch p teilbar und somit kann das Wort nicht in der Sprache sein.

Hui, geht natürlich noch viel einfacher ;)
a^(p + p*k) müsste durch hochpumpen auch in der Sprache sein.
Aber p+p*k ist durch p teilbar und daher keine Primzahl ;)

Wenn einer mal Zeit hat, wäre es nett wenn mir eine Verständnisfrage erklärt werden könnte.
Auf S.299/300 (siehe Link:http://books.google.de/books?id=Zo7I8kutRVIC&pg=PA299&vq=LOOP&dq=Grundkurs+theoretische+informatik&source=gbs_search_s&sig=ACfU3U0IlPgg_T_uX1uFIFgKk8del34FYA#PPA300,M1) im Vossen & Witt wird bewiesen, dass jedes LOOP-Programm durch eine Ackermannfunktion beschränkt ist. Dies wird induktiv gemacht.
Meiner Meinung nach ist da ein Fehler oder ich hab etwas übersehen.
Im Punkt ii) soll bewiesen werden, warum das für Sequenzen P_1: P_2 gilt (also die Induktionsbasis für elementare Anweisungen x_i := x_j + c wurde schon bewiesen) gilt.
Dann kommt der Ansatz

f_P(x) <= f_P_2( f_P_1(x)) . Und da haperts schon. Wie kommen die darauf?

Also angenommen (read bedeutet Eingabe erfolgt in Variable x_1, alle anderen Variablen werden 0 intialisiert, Ausgabe wird immer in x_0 geschrieben)

P_1 ist folgendes LOOP Programm: read(x_1) x_2 := x_1 + 5; x_0 = x_2 + 10 write(x_0)
Dann ist die von P_1 berechnete Funktion ja f_P_1(x) = x + 15;
Angenommen P_2 ist folgendes Programm: read(x_1) x_0 = x_2 + 5; write(x_0)
Dann ist f_P_2(x) = 5; (da x_2 und x_0 automatisch mit 0 initialisiert werden).
Komponiert man die Funktionen, dann erhaelt man f_P_2(f_P_1(x))= f_P_2( x + 15) = 5

Komponiert man aber die beiden LOOP Programme zum Programm P, erzeugt also die Sequenz erhält man ja folgendes LOOP-Programm:
read(x_1) x_2 := x_1 + 5; x_0 = x_2 + 10 ; x_0 = x_2 + 5; write(x_0)
Und P berechnet dann die Funktion f_P(x) = x + 10

Summasummarum gilt also NICHT f_P(x) <= f_P_2(f_P_1(x)) , sondern im Gegenteil
f_P(x) > f_P_2(f_P_1(x)) für alle x.

Wäre nett wenn mir da jemand weiterhelfen könnte. Falls ihr noch Informationne über LOOP Programme braucht(weil ihr den Vossen & Witt nicht kennt oder habt), schreib ich gerne noch was.

Es gelte F äquivalent zu G. Man zeige:
Wenn F' bzw. G' aus F bzw. G hervorgehen, indem man alle Vorkommen von AND durch OR und umgekehrt ersetzt, so gilt F' äquivalent zu G'.

Wie zeige ich das? Mit struktureller Induktion?