Beweisen dass eine Grammatik eine Sprache erzeugt
- Themenstarter Kirby.exe
- Beginndatum
G
Gelöschtes Mitglied 65838
Gast
a) zeigen sie kannst du immer ganz einfach begründen -> mach 3 wörter und mal schauen ob du auf die Form raus kommst wenn ja hast du es "bewiesen"
b) die erste Regel ist S -> aSd die aber genau die gleichen Eigenschaften wie A->aAb hat also eine CH2 Sprache
kann es nicht sein dass S -> ABC gemeint war mit erste Regel ? weil dann wäre es eine CH2 Sprache aber so ist es eine CH0 Sprache mit der S -> ABC Regel, eskönnte auch gedacht worden sein dass die "S Regeln" weggelassen werden sollen für die bestimmung
b) die erste Regel ist S -> aSd die aber genau die gleichen Eigenschaften wie A->aAb hat also eine CH2 Sprache
kann es nicht sein dass S -> ABC gemeint war mit erste Regel ? weil dann wäre es eine CH2 Sprache aber so ist es eine CH0 Sprache mit der S -> ABC Regel, eskönnte auch gedacht worden sein dass die "S Regeln" weggelassen werden sollen für die bestimmung
Aber soll man nicht immer beweisen ohne Beschränkung der Allgemeinheit?
G
Gelöschtes Mitglied 65838
Gast
"zeigen sie" ist kein "beweisen sie"
LimDul
Top Contributor
Das reicht für a) aber nicht. Da muss ich zeigen, dass ich mit den Regeln alle Wörter erzeugen kann aus dieser Sprache und keins erzeugen kann, dass nicht aus dieser Sprache ist.
Ich bin was eingerostet - ich würde folgende Varianten für den Beweis sehen
Einmal mit zwei Beweisen:
Gegeben ein Wort der Sprache gemäß der Definition in a) - zeigen, dass ich es mit der Grammatik erzeugen erzeugen
Gegeben ein Wort aus der Grammatik - zeigen dass es der Definition in a entspricht.
Damit hab ich gezeigt, dass die Sprache eine Teilmenge der Grammatik ist und die Grammatik eine Teilmenge der Sprache => Daraus ergibt sich die Gleichheit
Oder alternativ die Grammatik transformieren, dass die Sprache rauskommt. Damit hat man dann auch die Äquivalenz gezeigt
G
Gelöschtes Mitglied 65838
Gast
weist du wie lange es braucht den beweis zu schreiben dass 0kleiner als 3 ist?
LimDul
Top Contributor
Doch in der Uni heißt "Zeigen sie" => Beweisen Sie
G
Gelöschtes Mitglied 65838
Gast
ok gut dann beweis erstmal dass es Überhaupt eine Grammatik ist dann beweise dass es überhaupt eine sprache ist dann musst du noch beweisenusw.. usw.. wenn man schon den "beweisen" pfad gehen will ein halber beweis ist nämlich nicht gütlig
LimDul
Top Contributor
Der erste Beweis, dass diese Sprache von der Grammatik erzeugt werden kann, ist recht einfach.
Zwei Dinge muss man da beweisen:
a) Die Reihenfolge der a,b,c,d ist fix (Sprich, aaaaaabbbbbbcccccdddd) => Ergibt sich aus den Regeln, man kann anhand der Regeln beweisen:
* Jedes a steht vor b
* Jedes b steht vor c
* Jedes c steht vor d
=> Fertig. (Wenn man es noch sauber aufschreibt)
b) Das die Anzahl der a und c gleich der Anzahl der b und d gibt.
- Jedes a was erzeugt wird, erzeugt auch ein b oder d
- Jedes b was erzeugt wird, erzeugt auch ein a oder c
- Jedes c was erzeugt wird, erzeugt auch ein b oder d
- Jedes d was erzeugt wird, erzeugt auch ein a oder c
=> Fertig (Wenn man es noch sauber aufschreibt)
Die andere Richtung ist etwas schwerer.
Edit: Wobei so schwer sollte der gar nicht sein - sind beiden gleichen Argumente, die Grammatik kann nur Wörter erzeugen der Form aaabbbcccdddd und mit der gleichen Argumentation wie oben ergibt sich die zweite Bedingung, dass a+c = b+d
Zwei Dinge muss man da beweisen:
a) Die Reihenfolge der a,b,c,d ist fix (Sprich, aaaaaabbbbbbcccccdddd) => Ergibt sich aus den Regeln, man kann anhand der Regeln beweisen:
* Jedes a steht vor b
* Jedes b steht vor c
* Jedes c steht vor d
=> Fertig. (Wenn man es noch sauber aufschreibt)
b) Das die Anzahl der a und c gleich der Anzahl der b und d gibt.
- Jedes a was erzeugt wird, erzeugt auch ein b oder d
- Jedes b was erzeugt wird, erzeugt auch ein a oder c
- Jedes c was erzeugt wird, erzeugt auch ein b oder d
- Jedes d was erzeugt wird, erzeugt auch ein a oder c
=> Fertig (Wenn man es noch sauber aufschreibt)
Die andere Richtung ist etwas schwerer.
Edit: Wobei so schwer sollte der gar nicht sein - sind beiden gleichen Argumente, die Grammatik kann nur Wörter erzeugen der Form aaabbbcccdddd und mit der gleichen Argumentation wie oben ergibt sich die zweite Bedingung, dass a+c = b+d
G
Gelöschtes Mitglied 65838
Gast
das wort gilt ja gar nicht für die Grammatik? also hast du nichts bewiesen
Wieso sollte es das nicht?
G
Gelöschtes Mitglied 65838
Gast
i + k = j + L
3+ 3 = 3 +4
das hast du im moment scheint mir nicht so gültig
a+c = b+d
du hast es so selber geschrieben nur das wort erfüllt es schlichtweg nicht
3+ 3 = 3 +4
das hast du im moment scheint mir nicht so gültig
a+c = b+d
du hast es so selber geschrieben nur das wort erfüllt es schlichtweg nicht
G
Gelöschtes Mitglied 65838
Gast
deswegen sagte ich auch 3 wörter... so hat der beweis nur wegen 1en buchstaben dreher keinen Sinn mehr...
LimDul
Top Contributor
Das war als Demo gedacht für den Teil, dass die Reihenfolge der a, b, und d fix ist. Und nein - mit 3 Wörtern hast du nix bewiesen.
Es ist doch etwas schwerer. Man muss ja auch zeigen, dass sich jedes Wort der Sprache tatsächlich mit der Grammatik erzeugen lässt.
Dabei ist wieder eine Fallunterscheidung hilfreich:
1. Fall: i > j
Wende (i-j)-mal die Regel S -> aSd an
Die übrigen Regeln ergeben sich dann fast automatisch.
1. Fall: i <= j
Wende keinmal die Regel S -> aSd an.
Damit ist auch die Teilaufgabe b) beantwortet.
G
Gelöschtes Mitglied 65838
Gast
Du kannst schlichtweg nicht "beweisen" dass es so ist da das dann eine aufgabe für 30 bis 40 min wäre...
bie uns ist immer die frage "zeige anhand der Wörter die Menge der Wörter der Sprache und bestimmte welches level es in der chmosky hierarichie hat"
bie uns ist immer die frage "zeige anhand der Wörter die Menge der Wörter der Sprache und bestimmte welches level es in der chmosky hierarichie hat"
Um zu zeigen, dass zwei Mengen gleich sind, dass also gilt A = B, ist es meistens angebracht, zu zeigen, dass
1. A eine Teilmenge von B ist und
2. B eine Teilmenge von A ist.
1. L(G) ist Teilmenge von {a^i b^j c^k d^l | i+k = j+l}
Dazu musst du zwei Dinge zeigen:
a) Von der Grammatik werden die a, b, c und d in dieser Reihenfolge erzeugt.
b) Die Formel i+k = j+l gilt (am Angang gilt sie mit i=j=k=l=0 und bei jedem Herleitungsschritt bleibt sie gültig).
2. {a^i b^j c^k d^l | i+k = j+l} ist Telmenge vom L(G)
Hierfür nimmst du ein beliebiges (festes) Wort der Sprache, also beliebige i, j, k und l, die die Formel i+k = j+l erfüllen, und zeigst,, dass du dieses Wort mit der Grammatik herleiten kannst.
Dafür ist die Fallunterscheidung hilfreich ob es mehr a's als b's gibt (i>j) oder nicht.
1. A eine Teilmenge von B ist und
2. B eine Teilmenge von A ist.
1. L(G) ist Teilmenge von {a^i b^j c^k d^l | i+k = j+l}
Dazu musst du zwei Dinge zeigen:
a) Von der Grammatik werden die a, b, c und d in dieser Reihenfolge erzeugt.
b) Die Formel i+k = j+l gilt (am Angang gilt sie mit i=j=k=l=0 und bei jedem Herleitungsschritt bleibt sie gültig).
2. {a^i b^j c^k d^l | i+k = j+l} ist Telmenge vom L(G)
Hierfür nimmst du ein beliebiges (festes) Wort der Sprache, also beliebige i, j, k und l, die die Formel i+k = j+l erfüllen, und zeigst,, dass du dieses Wort mit der Grammatik herleiten kannst.
Dafür ist die Fallunterscheidung hilfreich ob es mehr a's als b's gibt (i>j) oder nicht.
mihe7
Top Contributor
3 und 0 sind zwei verschiedene natürliche Zahlen. Peano-Axiom: 0 ist kein Nachfolger einer natürlichen Zahl -> fertig.
G
Gelöschtes Mitglied 65838
Gast
sieh dir mal den beweis an dass 0 kleiner ist als 3 ... das geht um 4 voll beschriebene word dateien
mihe7
Top Contributor
Hast Du einen Link? Wer schreibt denn bitte 4 Seiten, um eine Definitionssache zu "beweisen"?
G
Gelöschtes Mitglied 65838
Gast
Kapitel2.pdf (uni-paderborn.de)
du musts erstmal b3eweisen dass 0 eine Natürliche Zahl ist
dann musst du beweisen dass 3 eine Natürliche Zahl ist
dann musst du beweisen dass 1 größer als 0 ist
dass 2 größer als 1 ist ...usw und sofort
du musts erstmal b3eweisen dass 0 eine Natürliche Zahl ist
dann musst du beweisen dass 3 eine Natürliche Zahl ist
dann musst du beweisen dass 1 größer als 0 ist
dass 2 größer als 1 ist ...usw und sofort
mihe7
Top Contributor
Abgesehen davon, dass ich in dem PDF keinen Beweis in der Richtung sehe, kann nichts bewiesen werden, was schlicht definiert wurde. Beispielsweise die 0: in einer Definition zählt die 0 zu den natürlichen Zahlen, in anderen nicht. Das kann nicht bewiesen werden, das wird einfach festgelegt. Die Peano-Axiome beschreiben nun axiomatisch die Struktur der natürlichen Zahlen.
Man könnte die natürlichen Zahlen auch so definieren: N={0, s(0), s(s(0)), s(s(s(0))), ...} wobei s(n) den Nachfolger von n angibt. Wir stellen s(s(s(0))) symbolisch mit einer 3 dar, könnten also definieren 3 := s(s(s(0))).
Die Frage, ob 0 < s(0) und s(0) < s(s(0)) und s(s(0)) < s(s(s(0))) gilt, also die Kette, wie Du sie zeigen willst, stellt sich nicht, da die Axiome sofort hergeben, dass 0 < n für alle positiven natürlichen Zahlen n gilt.
Ich könnte mir vorstellen, dass der Punkt a
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}in der Vorlesung oder so zumindest grundsätzlich erklärt wurde.
Hast Du das nicht mitbekommen oder war die Vorlesung einfach zu abstrakt?
Aufgabe b soll sicher Aufgabe a nur vertiefen und besteht nicht ohne gelernte Vorkentnisse.
Dies soll kein Vorwurf oder eine Unterstellung von Missverständnis sein.
In diesem Bereich toben sich die Professoren mit Unverständlichkeit aus.
Ich habe zum Beispiel mal dieses Buch gekauft:
Buch Automatentheorie und Logik
Eine wertlose Formelwüste (zumindest für mich)
Ich vermute dass es gut wäre dies per Induktion zu beweisen, aber ich verstehe nicht wie der Schritt aussehen soll
Der Induktionsanfang wäre ja z.B. sowas:
Code:
S -> e
Da i = k = j = l = 0 liegt dieses Wort in der Sprache und der IA gilt.Nun sehe ich dennoch nicht wie die Indultionshypothese und der Schritt aussehen soll
mihe7
Top Contributor
Puh, das Zeug... ich probier es mal:
Lemma 1: Sei G = (N,T,P,S) gegeben. Für eine Produktionsregel X -> tXu mit X ∈ N, t,u ∈ T gilt: X ->ⁿ tⁿXuⁿ für alle natürlichen Zahlen n.
Beweis:
Für n = 0 ist X ->⁰ t⁰Xu⁰ = X. Die Behauptung gelte nun für n. Das Wort tⁿ⁺¹Xuⁿ⁺¹ entsteht durch einmalige Ableitung von tⁿXuⁿ. Nach Induktionsannahme ist also X ->ⁿ tⁿXuⁿ -> tⁿ⁺¹Xuⁿ⁺¹ und damit X ->ⁿ⁺¹ tⁿ⁺¹Xuⁿ⁺¹. ∎
Lemma 2: Sei G = (N,T,P,S) gegeben. Existiert zur Produktionsregel aus Lemma 1 eine Alternative X -> ε, dann gilt:
X ->ⁿ tⁿXuⁿ oder X ->ⁿ tⁿ⁻¹uⁿ⁻¹ für alle natürlichen Zahlen n.
Beweis: X ->ⁿ tⁿXuⁿ gilt nach Lemma 1, ebenso auch X ->ⁿ⁻¹ tⁿ⁻¹Xuⁿ⁻¹. Durch Anwendung der Alternative erhält man
X ->ⁿ⁻¹ tⁿ⁻¹Xuⁿ⁻¹ -> tⁿ⁻¹uⁿ⁻¹ und damit X ->ⁿ tⁿ⁻¹uⁿ⁻¹. ∎
Für alle natürlichen Zahlen v gilt nach Lemma 1: S ->ᵛ aᵛSdᵛ. Einzige Alternative ist der Fall S -> ABC, also S ->ᵛ aᵛSdᵛ -> aᵛABCdᵛ.
O.B.d.A. können wir der Reihe nach A, B und C durch entsprechende Ableitungen (Lemma 2) ersetzen:
aᵛABCdᵛ ->ʷ aᵛaʷAbʷBCdᵛ -> aᵛaʷbʷBCdᵛ ->ˣ aᵛaʷbʷbˣBcˣCdᵛ -> aᵛaʷbʷbˣcˣCdᵛ ->ʸ aᵛaʷbʷbˣcˣcʸCdʸdᵛ -> aᵛaʷbʷbˣcˣcʸdʸdᵛ = aᵛ⁺ʷbʷ⁺ˣcˣ⁺ʸdʸ⁺ᵛ = aⁱbʲcᵏdˡ mit i=v+w, j=w+x, k=x+y, l=y+v, dann ist i+k = v+w+x+y = w+x+y+v = j+l.
Lemma 1: Sei G = (N,T,P,S) gegeben. Für eine Produktionsregel X -> tXu mit X ∈ N, t,u ∈ T gilt: X ->ⁿ tⁿXuⁿ für alle natürlichen Zahlen n.
Beweis:
Für n = 0 ist X ->⁰ t⁰Xu⁰ = X. Die Behauptung gelte nun für n. Das Wort tⁿ⁺¹Xuⁿ⁺¹ entsteht durch einmalige Ableitung von tⁿXuⁿ. Nach Induktionsannahme ist also X ->ⁿ tⁿXuⁿ -> tⁿ⁺¹Xuⁿ⁺¹ und damit X ->ⁿ⁺¹ tⁿ⁺¹Xuⁿ⁺¹. ∎
Lemma 2: Sei G = (N,T,P,S) gegeben. Existiert zur Produktionsregel aus Lemma 1 eine Alternative X -> ε, dann gilt:
X ->ⁿ tⁿXuⁿ oder X ->ⁿ tⁿ⁻¹uⁿ⁻¹ für alle natürlichen Zahlen n.
Beweis: X ->ⁿ tⁿXuⁿ gilt nach Lemma 1, ebenso auch X ->ⁿ⁻¹ tⁿ⁻¹Xuⁿ⁻¹. Durch Anwendung der Alternative erhält man
X ->ⁿ⁻¹ tⁿ⁻¹Xuⁿ⁻¹ -> tⁿ⁻¹uⁿ⁻¹ und damit X ->ⁿ tⁿ⁻¹uⁿ⁻¹. ∎
Für alle natürlichen Zahlen v gilt nach Lemma 1: S ->ᵛ aᵛSdᵛ. Einzige Alternative ist der Fall S -> ABC, also S ->ᵛ aᵛSdᵛ -> aᵛABCdᵛ.
O.B.d.A. können wir der Reihe nach A, B und C durch entsprechende Ableitungen (Lemma 2) ersetzen:
aᵛABCdᵛ ->ʷ aᵛaʷAbʷBCdᵛ -> aᵛaʷbʷBCdᵛ ->ˣ aᵛaʷbʷbˣBcˣCdᵛ -> aᵛaʷbʷbˣcˣCdᵛ ->ʸ aᵛaʷbʷbˣcˣcʸCdʸdᵛ -> aᵛaʷbʷbˣcˣcʸdʸdᵛ = aᵛ⁺ʷbʷ⁺ˣcˣ⁺ʸdʸ⁺ᵛ = aⁱbʲcᵏdˡ mit i=v+w, j=w+x, k=x+y, l=y+v, dann ist i+k = v+w+x+y = w+x+y+v = j+l.
LimDul
Top Contributor
Du hast 8 Regeln in der Grammatik. Für jede Regel zeigst nun, dass i+k = j+l nach Anwendung der Regel weiterhin gilt.Ich vermute dass es gut wäre dies per Induktion zu beweisen, aber ich verstehe nicht wie der Schritt aussehen soll
Der Induktionsanfang wäre ja z.B. sowas:
Code:S -> e Da i = k = j = l = 0 liegt dieses Wort in der Sprache und der IA gilt.
Nun sehe ich dennoch nicht wie die Indultionshypothese und der Schritt aussehen soll
Nehmen wir mal die Regel A->aAb.
Vorher gilt: i+k = j+l
Durch Anwendung dieser Regel gilt für die Werte danach (Jeweils i', j', k', l' genannt)
i' = i+1 (Es kommt ein a hinzu)
j' = j+1 (Es kommt ein b hinzu)
k' = k (Es kommt kein c hinzu)
l' = l (Es kommt kein d hinzu)
Das heißt, wir wollen nun wissen gilt: i'+k' = j'+l' wenn vorher i+k = j+l gegolten hat.
Formen wir die Formal mal um, indem wir gemäß den 4 obigen Aussagen die Werte ersetzen
Code:
i'+k' = j'+l'
<=> i+1 + k = j+1 + l
<=> i +k = j + lDas ganze für jede der 8 Regeln und Beweis für diese Richtung ist fertig.
Ein Nachtrag:
Das ganze klappt natürlich nicht in der Form bei jeder Grammatik - es muss nicht zwangsweise gelten, dass bei Anwendung jeder Regel so eine Invariante wie hier erhalten bleibt. Die Grammatik macht es einem aber einfach, weil sie das sicherstellt und jeder Zwischenschritt ebenfalls nur Wörter erzeugt, die bezüglich der Zeichen der Invariante gültig sind.
mihe7
Top Contributor
Nö, warum? Das sind ja alles nur Ideen zur Inspiration.
Dem kann ich nur zustimmen
Ich darf ja das Internet verwenden um diese Aufgaben zu lösen Sei G = ( {S, A, B, C}, {a, b, c, d}, P, S) mit {
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
Beweis Reihenfolge:
Jedes a erscheint in einem gültigen Wort vor einem b, c, oder d.
Jedes b erscheint nach einem a.
Jedes b erscheint in einem gültigen Wort vor einem c, oder d.
Jedes c erscheint nach einem a oder b.
Jedes c erscheint in einem gültigen Wort vor einem d.
Jedes c erscheint nach einem a, b oder c.
Dies wird nicht durch folgende Produktionsregeln verletzt:
A -> aBb
A -> empty
B -> bBc
B -> empty
C -> cCd
C -> empty
Folgende Produktionsregel verletzt die Reihenfolge ebenfalls nicht:
S -> ABC
Folgende Produktionsregel verletzt die Reihenfolge ebenfalls nicht:
S -> aSd
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
Beweis Reihenfolge:
Jedes a erscheint in einem gültigen Wort vor einem b, c, oder d.
Jedes b erscheint nach einem a.
Jedes b erscheint in einem gültigen Wort vor einem c, oder d.
Jedes c erscheint nach einem a oder b.
Jedes c erscheint in einem gültigen Wort vor einem d.
Jedes c erscheint nach einem a, b oder c.
Dies wird nicht durch folgende Produktionsregeln verletzt:
A -> aBb
A -> empty
B -> bBc
B -> empty
C -> cCd
C -> empty
Folgende Produktionsregel verletzt die Reihenfolge ebenfalls nicht:
S -> ABC
Folgende Produktionsregel verletzt die Reihenfolge ebenfalls nicht:
S -> aSd
Zuletzt bearbeitet:
Sei G = ( {S, A, B, C}, {a, b, c, d}, P, S) mit {
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
Beweis der Gleichung (Bedingung):
Sprache a)
i (count of a) := count of not_empty S + count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C + count of not_empty S
Die Gleichung ist bei leerem Wort:
i + k == j + l mit i, j k und l == 0
0 + 0 == 0 + 0
Also ist die Gleichung bei leerem Wort (Anwendung S -> ABC, A -> empty, B -> empty, C -> empty) erfüllt.
Wird Produktionsregel A -> aAb mit A -> empty angewendet, wird i und j um 1 erhöht.
i und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel B -> aBb mit B -> empty angewendet, wird j und k um 1 erhöht.
k und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel C -> aCb mit C -> empty angewendet, wird k und k um 1 erhöht.
k und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel S -> aSd angewendet, wird i und l um 1 erhöht.
i und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Sprache b)
i (count of a) := count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C
Die Gleichung ist bei leerem Wort:
i + k == j + l mit i, j k und l == 0
0 + 0 == 0 + 0
Also ist die Gleichung bei leerem Wort (Anwendung S -> ABC, A -> empty, B -> empty, C -> empty) erfüllt.
Wird Produktionsregel A -> aAb mit A -> empty angewendet, wird i und j um 1 erhöht.
i und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel B -> aBb mit B -> empty angewendet, wird j und k um 1 erhöht.
k und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel C -> aCb mit C -> empty angewendet, wird k und k um 1 erhöht.
k und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
(Hier fällt die Produktionsregel S -> aSd weg.
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
Beweis der Gleichung (Bedingung):
Sprache a)
i (count of a) := count of not_empty S + count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C + count of not_empty S
Die Gleichung ist bei leerem Wort:
i + k == j + l mit i, j k und l == 0
0 + 0 == 0 + 0
Also ist die Gleichung bei leerem Wort (Anwendung S -> ABC, A -> empty, B -> empty, C -> empty) erfüllt.
Wird Produktionsregel A -> aAb mit A -> empty angewendet, wird i und j um 1 erhöht.
i und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel B -> aBb mit B -> empty angewendet, wird j und k um 1 erhöht.
k und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel C -> aCb mit C -> empty angewendet, wird k und k um 1 erhöht.
k und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel S -> aSd angewendet, wird i und l um 1 erhöht.
i und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Sprache b)
i (count of a) := count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C
Die Gleichung ist bei leerem Wort:
i + k == j + l mit i, j k und l == 0
0 + 0 == 0 + 0
Also ist die Gleichung bei leerem Wort (Anwendung S -> ABC, A -> empty, B -> empty, C -> empty) erfüllt.
Wird Produktionsregel A -> aAb mit A -> empty angewendet, wird i und j um 1 erhöht.
i und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel B -> aBb mit B -> empty angewendet, wird j und k um 1 erhöht.
k und j befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
Wird Produktionsregel C -> aCb mit C -> empty angewendet, wird k und k um 1 erhöht.
k und l befinden sich jeweils auf der linken und rechten Seite der Gleichung, die Gleichung wird nicht verletzt.
(Hier fällt die Produktionsregel S -> aSd weg.
Ich habe auch ein wenig Code dazu geschrieben.
Die beiden Sprachen sind nicht äquivalent.
Die Bedingung oben i + k = j + l wird aber von beiden Sprachen eingehalten.
Den Unterschied, den ich gefunden habe, findet man im Code.
Eventuell gibt es noch mehr Unterschiede oder man kann den Unterschied anders formulieren:
[CODE lang="java" title="AbstractCartesianProductIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
abstract public class AbstractCartesianProductIterator<RESULT, LEFT, RIGHT>
implements Iterator<RESULT>
{
private final Iterator<LEFT> leftIterator;
private boolean hasLeft;
private LEFT currentLeft;
private final Iterable<RIGHT> rightIterable;
private Iterator<RIGHT> rightIterator;
/**
* Constructor.
*
* @param leftIterator
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterator<LEFT> leftIterator ,
final Iterable<RIGHT> rightIterable )
{
this.leftIterator = Objects.requireNonNull( leftIterator );
this.rightIterable = Objects.requireNonNull( rightIterable );
if ( this.leftIterator.hasNext() )
{
this.hasLeft = true;
this.currentLeft = leftIterator.next();
this.rightIterator = Objects.requireNonNull( rightIterable.iterator() );
}
}
/**
* Constructor.
*
* @param leftIterable
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterable<LEFT> leftIterable ,
final Iterable<RIGHT> rightIterable )
{
this(
leftIterable.iterator() ,
rightIterable );
}
/**
* Method to implement to combine two elements of the left and the right source.
* @param left element from the left source
* @param right element from the right source
* @return result of combination of the given elements
*/
abstract RESULT combine(
final LEFT left ,
final RIGHT right );
@Override
final public boolean hasNext()
{
return
this.hasLeft &&
this.rightIterator.hasNext();
}
@Override
final public RESULT next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final RIGHT right = this.rightIterator.next();
final RESULT result =
combine(
this.currentLeft ,
right );
if ( ! this.rightIterator.hasNext() )
{
if ( this.leftIterator.hasNext() )
{
this.currentLeft = this.leftIterator.next();
this.rightIterator = Objects.requireNonNull( this.rightIterable.iterator() );
}
else
{
this.hasLeft = false;
this.currentLeft = null; // free memory
}
}
return result;
}
}
[/CODE]
[CODE lang="java" title="ConcatIterator"]import java.util.Iterator;
import java.util.Objects;
/**
* Concatenation of two {@link Iterator}.
*/
public class ConcatIterator<E>
implements Iterator<E>
{
private final Iterator<E> first;
private final Iterator<E> second;
/**
* Constructor.
*
* @param first
* @param second
*/
public ConcatIterator(
final Iterator<E> first ,
final Iterator<E> second )
{
this.first = Objects.requireNonNull( first );
this.second = Objects.requireNonNull( second );
}
@Override
public boolean hasNext()
{
return
this.first.hasNext() ||
this.second.hasNext();
}
@Override
public E next()
{
if ( this.first.hasNext() )
{
return this.first.next();
}
return this.second.next();
}
}
[/CODE]
[CODE lang="java" title="ConcatIteratorWithIterable"]import java.util.Iterator;
import java.util.Objects;
public class ConcatIteratorWithIterable<E>
implements Iterator<E>
{
private final Iterator<E> firstIterator;
private final Iterable<E> secondIterable;
private Iterator<E> secondIterator;
/**
* Constructor.
*
* @param firstIterator
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterator<E> firstIterator ,
final Iterable<E> secondIterable )
{
this.firstIterator = Objects.requireNonNull( firstIterator );
this.secondIterable = Objects.requireNonNull( secondIterable );
}
/**
* Constructor.
*
* @param firstIterable
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterable<E> firstIterable ,
final Iterable<E> secondIterable )
{
this(
firstIterable.iterator() ,
secondIterable );
}
@Override
public boolean hasNext()
{
return
this.firstIterator.hasNext() ||
( this.secondIterator != null && this.secondIterator.hasNext() );
}
@Override
public E next()
{
if ( this.firstIterator.hasNext() )
{
final E next = this.firstIterator.next();
if ( ! this.firstIterator.hasNext() )
{
this.secondIterator = Objects.requireNonNull( this.secondIterable.iterator() );
}
return next;
}
return this.secondIterator.next();
}
}
[/CODE]
[CODE lang="java" title="Pair"]
public final class Pair<LEFT, RIGHT>
{
public final LEFT left;
public final RIGHT right;
/**
* Constructor.
*
* @param left
* @param right
*/
public Pair(
final LEFT left ,
final RIGHT right )
{
this.left = left;
this.right = right;
}
@Override
public String toString()
{
return "[" + this.left + ", " + this.right + "]";
}
}
[/CODE]
[CODE lang="java" title="LimitIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class LimitIterator<E>
implements Iterator<E>
{
public final int limit;
private final Iterator<E> iteratorToLimit;
private int count;
/**
* Constructor.
*
* @param iteratorToLimit
* @param limit
*/
public LimitIterator(
final Iterator<E> iteratorToLimit ,
final int limit )
{
this.iteratorToLimit = Objects.requireNonNull( iteratorToLimit );
this.limit = limit;
}
@Override
public boolean hasNext()
{
return
( this.count < this.limit ) &&
this.iteratorToLimit.hasNext();
}
@Override
public E next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
this.count++;
return this.iteratorToLimit.next();
}
}
[/CODE]
[CODE lang="java" title="LimitIterable"]import java.util.Iterator;
import java.util.Objects;
public class LimitIterable<E>
implements Iterable<E>
{
public final int limit;
private final Iterable<E> iterableToLimit;
/**
* Constructor.
*
* @param iterableToLimit
* @param limit
*/
public LimitIterable(
final Iterable<E> iterableToLimit ,
final int limit )
{
this.iterableToLimit = Objects.requireNonNull( iterableToLimit );
this.limit = limit;
}
@Override
public Iterator<E> iterator()
{
return new LimitIterator<>(
// iteratorToLimit
this.iterableToLimit.iterator() ,
this.limit );
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class StringWrapFromZeroToCountIterator
implements Iterator<String>
{
public final int wrapCount;
public final String leftWrapStr;
public final String rightWrapStr;
private final Iterator<String> iteratorToWrap;
private int currentWrapCount;
private boolean hasNextStr = false;
private String nextStr;
/**
* Constructor.
*
* @param iteratorToWrap
* @param leftWrapStr
* @param rightWrapStr
* @param wrapCount
*/
public StringWrapFromZeroToCountIterator(
final Iterator<String> iteratorToWrap ,
final String leftWrapStr ,
final String rightWrapStr ,
final int wrapCount )
{
this.iteratorToWrap = Objects.requireNonNull( iteratorToWrap );
this.leftWrapStr = leftWrapStr;
this.rightWrapStr = rightWrapStr;
this.wrapCount = wrapCount;
if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
hasNextStr = true;
}
}
@Override
public boolean hasNext()
{
return hasNextStr;
}
@Override
public String next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final String result = nextStr;
skip();
return result;
}
private void skip()
{
if ( this.currentWrapCount < this.wrapCount )
{
this.nextStr =
this.leftWrapStr +
"" + // avoid NullPointerException
this.nextStr +
this.rightWrapStr;
this.currentWrapCount++;
}
else if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
}
else
{
hasNextStr = false;
}
}
}
[/CODE]
[CODE lang="java" title="AbstractCartesianProductIteratorTest"]import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class AbstractCartesianProductIteratorTest
{
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.util.Iterator, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIteratorOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.lang.Iterable, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIterableOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#combine(java.lang.Object, java.lang.Object)}.
*/
@Test
public void testCombine()
{
final Iterable<String> leftIterable =
Arrays.asList(
"a" ,
"b" ,
"c" );
final Iterable<Integer> rightIterable =
Arrays.asList(
0 ,
1 ,
2 );
final AbstractCartesianProductIterator<String, String, Integer> cartesianProductIterator =
new AbstractCartesianProductIterator<String, String, Integer>(
leftIterable ,
rightIterable )
{
@Override
String combine(
final String left ,
final Integer right )
{
return left + right;
}
};
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c2" ,
//actual
cartesianProductIterator.next() );
Assert.assertFalse( cartesianProductIterator.hasNext() );
}
/**
* Test method for {@link AbstractCartesianProductIterator#hasNext()}.
*/
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#next()}.
*/
@Ignore
@Test
public void testNext() {
fail("Not yet implemented");
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIteratorTest"]import static org.junit.Assert.fail;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class StringWrapFromZeroToCountIteratorTest
{
@Ignore
@Test
public void testStringWrapFromZeroToCountIterator() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testNext()
{
fail("Not yet implemented");
}
@Test
public void test()
{
final StringWrapFromZeroToCountIterator wrapIterator =
new StringWrapFromZeroToCountIterator(
//iteratorToWrap
Arrays.asList( "1" , "2" ).iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"b" ,
//wrapCount
2 );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"1" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a1b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa1bb" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"2" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a2b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa2bb" ,
//actual
wrapIterator.next() );
Assert.assertFalse( wrapIterator.hasNext() );
}
}
[/CODE]
[CODE lang="java" title="GenerateWords"]import java.util.Arrays;
import java.util.Iterator;
/*
https://www.java-forum.org/thema/beweisen-dass-eine-grammatik-eine-sprache-erzeugt.192150/#post-1254785
Sei G = ( {S, A, B, C}, {a, b, c, d}, P, S) mit {
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
*/
/*
Sprache a)
i (count of a) := count of not_empty S + count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C + count of not_empty S
Sprache b)
i (count of a) := count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C
*/
public class GenerateWords
{
static final int LIMIT = 4;
// A -> aBb
static class A_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public A_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "a" , "b" ) ) ,
//rightIterable
() -> new A_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// A -> empty, A -> aBb
static class A_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public A_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new A_Iterator_without_empty() );
}
}
// B -> bBc
static class B_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public B_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "b" , "c" ) ) ,
//rightIterable
() -> new B_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// B -> empty, B -> bBc
static class B_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public B_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new B_Iterator_without_empty() );
}
}
// C -> cCd
static class C_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public C_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "c" , "d" ) ) ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// C -> empty, C -> cCd
static class C_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public C_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new C_Iterator_without_empty() );
}
}
// BC
static class BC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new B_Iterator() , LIMIT ) ,
//rightIterable
new LimitIterable<>( () -> new C_Iterator() , LIMIT ) );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new A_Iterator() , LIMIT ) ,
//rightIterable
() -> new BC_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> aSd
//static class S_recursive_Iterator
//extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
//{
// /**
// * Constructor.
// */
// public S_recursive_Iterator()
// {
// super(
// //leftIterable
// Arrays.asList( new Pair<>( "a" , "d" ) ) ,
// //rightIterable
// new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT ) );
// }
//
// @Override
// String combine(
// final Pair<String, String> left ,
// final String right )
// {
// return left.left + right + left.right;
// }
//}
static class S_Iterator
extends StringWrapFromZeroToCountIterator
{
/**
* Constructor.
*/
public S_Iterator()
{
super(
//iteratorToWrap
new ABC_Iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"d" ,
//wrapCount
LIMIT );
}
}
public static void main(String[] args)
{
System.out.println( "A:" );
final Iterable<String> a_Iterable = new LimitIterable<>( () -> new A_Iterator() , LIMIT );
System.out.println( size( a_Iterable ) );
for ( final String aStr : a_Iterable )
{
System.out.println( aStr );
}
System.out.println( "============================================================================================" );
System.out.println( "B:" );
final Iterable<String> b_Iterable = new LimitIterable<>( () -> new B_Iterator() , LIMIT );
System.out.println( size( b_Iterable ) );
for ( final String bStr : b_Iterable )
{
System.out.println( bStr );
}
System.out.println( "============================================================================================" );
System.out.println( "C:" );
final Iterable<String> c_Iterable = new LimitIterable<>( () -> new C_Iterator() , LIMIT );
System.out.println( size( c_Iterable ) );
for ( final String cStr : c_Iterable )
{
System.out.println( cStr );
}
System.out.println( "============================================================================================" );
System.out.println( "BC:" );
final Iterable<String> bc_Iterable = () -> new BC_Iterator();
System.out.println( size( bc_Iterable ) );
for ( final String bcStr : bc_Iterable )
{
System.out.println( bcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "ABC:" );
final Iterable<String> abc_Iterable = () -> new ABC_Iterator();
System.out.println( size( abc_Iterable ) );
for ( final String abcStr : abc_Iterable )
{
System.out.println( abcStr );
checkCondition( abcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "S:" );
//final Iterable<String> s_recursive_Iterable = new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT );
//
//for ( final String s_recursiveStr : s_recursive_Iterable )
//{
// System.out.println( s_recursiveStr );
//}
//
//System.out.println( "============================================================================================" );
final Iterable<String> s_Iterable = () -> new S_Iterator();
System.out.println( size( s_Iterable ) );
for ( final String sStr : s_Iterable )
{
System.out.println( sStr );
checkCondition( sStr );
// wenn dies in einer Endlosschleife hängen bleibt, sind die Sprechen a) und b) nicht äquivalent
//check_ABC_contains( sStr );
}
System.out.println( "============================================================================================" );
}
private static int size(
final Iterable<?> iterableToCount )
{
int size = 0;
for ( final Object obj : iterableToCount )
{
size++;
}
return size;
}
private static void checkCondition(
final String sStr )
{
final long i = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'a' ).count();
final long j = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'b' ).count();
final long k = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'c' ).count();
final long l = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'd' ).count();
if ( i + k != j + l )
{
throw new RuntimeException( i + " + " + k + " != " + j + " + " + l );
}
//if ( i + k - j - l != 0 )
//{
// throw new RuntimeException( i + " + " + k + " - " + j + " - " + l + " != 0" );
//}
//if ( ! isImplicatd( i == l , j == k ) )
if ( ( i == l ) != ( j == k ) )
{
throw new RuntimeException( i + " == " + l + " != " + j + " == " + k );
}
if ( ! isImplicatd( j == 0 , i == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( j + " == 0 =!=> " + i + " == 0" );
}
if ( ! isImplicatd( k == 0 , l == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( k + " == 0 =!=> " + l + " == 0" );
}
}
private static boolean isImplicatd(
final boolean left ,
final boolean right )
{
if ( left )
{
return right;
}
return true;
}
// BC
static class BC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator_unlimited()
{
super(
//leftIterable
() -> new B_Iterator() ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator_unlimited()
{
super(
//leftIterator
new A_Iterator() ,
//rightIterable
() -> new BC_Iterator_unlimited() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
private static void check_ABC_contains(
final String sStr )
{
final Iterator<String> abc_Iterator_unlimited = new ABC_Iterator_unlimited();
while ( ! abc_Iterator_unlimited.next().equals( sStr ) );
// runs infinity when not satisfied
}
}
[/CODE]
Die beiden Sprachen sind nicht äquivalent.
Die Bedingung oben i + k = j + l wird aber von beiden Sprachen eingehalten.
Den Unterschied, den ich gefunden habe, findet man im Code.
Eventuell gibt es noch mehr Unterschiede oder man kann den Unterschied anders formulieren:
[CODE lang="java" title="AbstractCartesianProductIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
abstract public class AbstractCartesianProductIterator<RESULT, LEFT, RIGHT>
implements Iterator<RESULT>
{
private final Iterator<LEFT> leftIterator;
private boolean hasLeft;
private LEFT currentLeft;
private final Iterable<RIGHT> rightIterable;
private Iterator<RIGHT> rightIterator;
/**
* Constructor.
*
* @param leftIterator
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterator<LEFT> leftIterator ,
final Iterable<RIGHT> rightIterable )
{
this.leftIterator = Objects.requireNonNull( leftIterator );
this.rightIterable = Objects.requireNonNull( rightIterable );
if ( this.leftIterator.hasNext() )
{
this.hasLeft = true;
this.currentLeft = leftIterator.next();
this.rightIterator = Objects.requireNonNull( rightIterable.iterator() );
}
}
/**
* Constructor.
*
* @param leftIterable
* @param rightIterable
*/
public AbstractCartesianProductIterator(
final Iterable<LEFT> leftIterable ,
final Iterable<RIGHT> rightIterable )
{
this(
leftIterable.iterator() ,
rightIterable );
}
/**
* Method to implement to combine two elements of the left and the right source.
* @param left element from the left source
* @param right element from the right source
* @return result of combination of the given elements
*/
abstract RESULT combine(
final LEFT left ,
final RIGHT right );
@Override
final public boolean hasNext()
{
return
this.hasLeft &&
this.rightIterator.hasNext();
}
@Override
final public RESULT next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final RIGHT right = this.rightIterator.next();
final RESULT result =
combine(
this.currentLeft ,
right );
if ( ! this.rightIterator.hasNext() )
{
if ( this.leftIterator.hasNext() )
{
this.currentLeft = this.leftIterator.next();
this.rightIterator = Objects.requireNonNull( this.rightIterable.iterator() );
}
else
{
this.hasLeft = false;
this.currentLeft = null; // free memory
}
}
return result;
}
}
[/CODE]
[CODE lang="java" title="ConcatIterator"]import java.util.Iterator;
import java.util.Objects;
/**
* Concatenation of two {@link Iterator}.
*/
public class ConcatIterator<E>
implements Iterator<E>
{
private final Iterator<E> first;
private final Iterator<E> second;
/**
* Constructor.
*
* @param first
* @param second
*/
public ConcatIterator(
final Iterator<E> first ,
final Iterator<E> second )
{
this.first = Objects.requireNonNull( first );
this.second = Objects.requireNonNull( second );
}
@Override
public boolean hasNext()
{
return
this.first.hasNext() ||
this.second.hasNext();
}
@Override
public E next()
{
if ( this.first.hasNext() )
{
return this.first.next();
}
return this.second.next();
}
}
[/CODE]
[CODE lang="java" title="ConcatIteratorWithIterable"]import java.util.Iterator;
import java.util.Objects;
public class ConcatIteratorWithIterable<E>
implements Iterator<E>
{
private final Iterator<E> firstIterator;
private final Iterable<E> secondIterable;
private Iterator<E> secondIterator;
/**
* Constructor.
*
* @param firstIterator
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterator<E> firstIterator ,
final Iterable<E> secondIterable )
{
this.firstIterator = Objects.requireNonNull( firstIterator );
this.secondIterable = Objects.requireNonNull( secondIterable );
}
/**
* Constructor.
*
* @param firstIterable
* @param secondIterable
*/
public ConcatIteratorWithIterable(
final Iterable<E> firstIterable ,
final Iterable<E> secondIterable )
{
this(
firstIterable.iterator() ,
secondIterable );
}
@Override
public boolean hasNext()
{
return
this.firstIterator.hasNext() ||
( this.secondIterator != null && this.secondIterator.hasNext() );
}
@Override
public E next()
{
if ( this.firstIterator.hasNext() )
{
final E next = this.firstIterator.next();
if ( ! this.firstIterator.hasNext() )
{
this.secondIterator = Objects.requireNonNull( this.secondIterable.iterator() );
}
return next;
}
return this.secondIterator.next();
}
}
[/CODE]
[CODE lang="java" title="Pair"]
public final class Pair<LEFT, RIGHT>
{
public final LEFT left;
public final RIGHT right;
/**
* Constructor.
*
* @param left
* @param right
*/
public Pair(
final LEFT left ,
final RIGHT right )
{
this.left = left;
this.right = right;
}
@Override
public String toString()
{
return "[" + this.left + ", " + this.right + "]";
}
}
[/CODE]
[CODE lang="java" title="LimitIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class LimitIterator<E>
implements Iterator<E>
{
public final int limit;
private final Iterator<E> iteratorToLimit;
private int count;
/**
* Constructor.
*
* @param iteratorToLimit
* @param limit
*/
public LimitIterator(
final Iterator<E> iteratorToLimit ,
final int limit )
{
this.iteratorToLimit = Objects.requireNonNull( iteratorToLimit );
this.limit = limit;
}
@Override
public boolean hasNext()
{
return
( this.count < this.limit ) &&
this.iteratorToLimit.hasNext();
}
@Override
public E next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
this.count++;
return this.iteratorToLimit.next();
}
}
[/CODE]
[CODE lang="java" title="LimitIterable"]import java.util.Iterator;
import java.util.Objects;
public class LimitIterable<E>
implements Iterable<E>
{
public final int limit;
private final Iterable<E> iterableToLimit;
/**
* Constructor.
*
* @param iterableToLimit
* @param limit
*/
public LimitIterable(
final Iterable<E> iterableToLimit ,
final int limit )
{
this.iterableToLimit = Objects.requireNonNull( iterableToLimit );
this.limit = limit;
}
@Override
public Iterator<E> iterator()
{
return new LimitIterator<>(
// iteratorToLimit
this.iterableToLimit.iterator() ,
this.limit );
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIterator"]import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class StringWrapFromZeroToCountIterator
implements Iterator<String>
{
public final int wrapCount;
public final String leftWrapStr;
public final String rightWrapStr;
private final Iterator<String> iteratorToWrap;
private int currentWrapCount;
private boolean hasNextStr = false;
private String nextStr;
/**
* Constructor.
*
* @param iteratorToWrap
* @param leftWrapStr
* @param rightWrapStr
* @param wrapCount
*/
public StringWrapFromZeroToCountIterator(
final Iterator<String> iteratorToWrap ,
final String leftWrapStr ,
final String rightWrapStr ,
final int wrapCount )
{
this.iteratorToWrap = Objects.requireNonNull( iteratorToWrap );
this.leftWrapStr = leftWrapStr;
this.rightWrapStr = rightWrapStr;
this.wrapCount = wrapCount;
if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
hasNextStr = true;
}
}
@Override
public boolean hasNext()
{
return hasNextStr;
}
@Override
public String next()
{
if ( ! hasNext() )
{
throw new NoSuchElementException();
}
final String result = nextStr;
skip();
return result;
}
private void skip()
{
if ( this.currentWrapCount < this.wrapCount )
{
this.nextStr =
this.leftWrapStr +
"" + // avoid NullPointerException
this.nextStr +
this.rightWrapStr;
this.currentWrapCount++;
}
else if ( this.iteratorToWrap.hasNext() )
{
nextStr = this.iteratorToWrap.next();
currentWrapCount = 0;
}
else
{
hasNextStr = false;
}
}
}
[/CODE]
[CODE lang="java" title="AbstractCartesianProductIteratorTest"]import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class AbstractCartesianProductIteratorTest
{
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.util.Iterator, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIteratorOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#AbstractCartesianProductIterator(java.lang.Iterable, java.lang.Iterable)}.
*/
@Ignore
@Test
public void testAbstractCartesianProductIteratorIterableOfLEFTIterableOfRIGHT() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#combine(java.lang.Object, java.lang.Object)}.
*/
@Test
public void testCombine()
{
final Iterable<String> leftIterable =
Arrays.asList(
"a" ,
"b" ,
"c" );
final Iterable<Integer> rightIterable =
Arrays.asList(
0 ,
1 ,
2 );
final AbstractCartesianProductIterator<String, String, Integer> cartesianProductIterator =
new AbstractCartesianProductIterator<String, String, Integer>(
leftIterable ,
rightIterable )
{
@Override
String combine(
final String left ,
final Integer right )
{
return left + right;
}
};
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"a2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"b2" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c0" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c1" ,
//actual
cartesianProductIterator.next() );
Assert.assertTrue( cartesianProductIterator.hasNext() );
Assert.assertEquals(
//expected
"c2" ,
//actual
cartesianProductIterator.next() );
Assert.assertFalse( cartesianProductIterator.hasNext() );
}
/**
* Test method for {@link AbstractCartesianProductIterator#hasNext()}.
*/
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
/**
* Test method for {@link AbstractCartesianProductIterator#next()}.
*/
@Ignore
@Test
public void testNext() {
fail("Not yet implemented");
}
}
[/CODE]
[CODE lang="java" title="StringWrapFromZeroToCountIteratorTest"]import static org.junit.Assert.fail;
import java.util.Arrays;
import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;
/**
* JUnit4 test.
*/
public class StringWrapFromZeroToCountIteratorTest
{
@Ignore
@Test
public void testStringWrapFromZeroToCountIterator() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testHasNext() {
fail("Not yet implemented");
}
@Ignore
@Test
public void testNext()
{
fail("Not yet implemented");
}
@Test
public void test()
{
final StringWrapFromZeroToCountIterator wrapIterator =
new StringWrapFromZeroToCountIterator(
//iteratorToWrap
Arrays.asList( "1" , "2" ).iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"b" ,
//wrapCount
2 );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"1" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a1b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa1bb" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"2" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"a2b" ,
//actual
wrapIterator.next() );
Assert.assertTrue( wrapIterator.hasNext() );
Assert.assertEquals(
//expected
"aa2bb" ,
//actual
wrapIterator.next() );
Assert.assertFalse( wrapIterator.hasNext() );
}
}
[/CODE]
[CODE lang="java" title="GenerateWords"]import java.util.Arrays;
import java.util.Iterator;
/*
https://www.java-forum.org/thema/beweisen-dass-eine-grammatik-eine-sprache-erzeugt.192150/#post-1254785
Sei G = ( {S, A, B, C}, {a, b, c, d}, P, S) mit {
S -> aSd,
S -> ABC,
A -> aAb,
B -> bBc,
C -> cCd,
A -> empty,
B -> empty
C -> empty}
a) Zeigen Sie L(G) = {a_hoch_i b_hoch_j c_hoch_k d_hoch_l | i + k = j + l}.
b) Wie lautet L(G) wenn die erste Produktionsregel weggelassen wird?
*/
/*
Sprache a)
i (count of a) := count of not_empty S + count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C + count of not_empty S
Sprache b)
i (count of a) := count of not_empty A
j (count of b) := count of not_empty A + count of not_empty B
k (count of c) := count of not_empty B + count of not_empty C
l (count of d) := count of not_empty C
*/
public class GenerateWords
{
static final int LIMIT = 4;
// A -> aBb
static class A_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public A_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "a" , "b" ) ) ,
//rightIterable
() -> new A_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// A -> empty, A -> aBb
static class A_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public A_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new A_Iterator_without_empty() );
}
}
// B -> bBc
static class B_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public B_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "b" , "c" ) ) ,
//rightIterable
() -> new B_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// B -> empty, B -> bBc
static class B_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public B_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new B_Iterator_without_empty() );
}
}
// C -> cCd
static class C_Iterator_without_empty
extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
{
/**
* Constructor.
*/
public C_Iterator_without_empty()
{
super(
//leftIterable
Arrays.asList( new Pair<>( "c" , "d" ) ) ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final Pair<String, String> left ,
final String right )
{
return left.left + right + left.right;
}
}
// C -> empty, C -> cCd
static class C_Iterator
extends ConcatIteratorWithIterable<String>
{
/**
* Constructor.
*/
public C_Iterator()
{
super(
//firstIterable
Arrays.asList( "" ) , // empty
//secondIterable
() -> new C_Iterator_without_empty() );
}
}
// BC
static class BC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new B_Iterator() , LIMIT ) ,
//rightIterable
new LimitIterable<>( () -> new C_Iterator() , LIMIT ) );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator()
{
super(
//leftIterable
new LimitIterable<>( () -> new A_Iterator() , LIMIT ) ,
//rightIterable
() -> new BC_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> aSd
//static class S_recursive_Iterator
//extends AbstractCartesianProductIterator<String, Pair<String, String>, String>
//{
// /**
// * Constructor.
// */
// public S_recursive_Iterator()
// {
// super(
// //leftIterable
// Arrays.asList( new Pair<>( "a" , "d" ) ) ,
// //rightIterable
// new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT ) );
// }
//
// @Override
// String combine(
// final Pair<String, String> left ,
// final String right )
// {
// return left.left + right + left.right;
// }
//}
static class S_Iterator
extends StringWrapFromZeroToCountIterator
{
/**
* Constructor.
*/
public S_Iterator()
{
super(
//iteratorToWrap
new ABC_Iterator() ,
//leftWrapStr
"a" ,
//rightWrapStr
"d" ,
//wrapCount
LIMIT );
}
}
public static void main(String[] args)
{
System.out.println( "A:" );
final Iterable<String> a_Iterable = new LimitIterable<>( () -> new A_Iterator() , LIMIT );
System.out.println( size( a_Iterable ) );
for ( final String aStr : a_Iterable )
{
System.out.println( aStr );
}
System.out.println( "============================================================================================" );
System.out.println( "B:" );
final Iterable<String> b_Iterable = new LimitIterable<>( () -> new B_Iterator() , LIMIT );
System.out.println( size( b_Iterable ) );
for ( final String bStr : b_Iterable )
{
System.out.println( bStr );
}
System.out.println( "============================================================================================" );
System.out.println( "C:" );
final Iterable<String> c_Iterable = new LimitIterable<>( () -> new C_Iterator() , LIMIT );
System.out.println( size( c_Iterable ) );
for ( final String cStr : c_Iterable )
{
System.out.println( cStr );
}
System.out.println( "============================================================================================" );
System.out.println( "BC:" );
final Iterable<String> bc_Iterable = () -> new BC_Iterator();
System.out.println( size( bc_Iterable ) );
for ( final String bcStr : bc_Iterable )
{
System.out.println( bcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "ABC:" );
final Iterable<String> abc_Iterable = () -> new ABC_Iterator();
System.out.println( size( abc_Iterable ) );
for ( final String abcStr : abc_Iterable )
{
System.out.println( abcStr );
checkCondition( abcStr );
}
System.out.println( "============================================================================================" );
System.out.println( "S:" );
//final Iterable<String> s_recursive_Iterable = new LimitIterable<>( () -> new S_recursive_Iterator() , LIMIT );
//
//for ( final String s_recursiveStr : s_recursive_Iterable )
//{
// System.out.println( s_recursiveStr );
//}
//
//System.out.println( "============================================================================================" );
final Iterable<String> s_Iterable = () -> new S_Iterator();
System.out.println( size( s_Iterable ) );
for ( final String sStr : s_Iterable )
{
System.out.println( sStr );
checkCondition( sStr );
// wenn dies in einer Endlosschleife hängen bleibt, sind die Sprechen a) und b) nicht äquivalent
//check_ABC_contains( sStr );
}
System.out.println( "============================================================================================" );
}
private static int size(
final Iterable<?> iterableToCount )
{
int size = 0;
for ( final Object obj : iterableToCount )
{
size++;
}
return size;
}
private static void checkCondition(
final String sStr )
{
final long i = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'a' ).count();
final long j = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'b' ).count();
final long k = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'c' ).count();
final long l = sStr.chars().filter( chrInt -> ( (char) chrInt ) == 'd' ).count();
if ( i + k != j + l )
{
throw new RuntimeException( i + " + " + k + " != " + j + " + " + l );
}
//if ( i + k - j - l != 0 )
//{
// throw new RuntimeException( i + " + " + k + " - " + j + " - " + l + " != 0" );
//}
//if ( ! isImplicatd( i == l , j == k ) )
if ( ( i == l ) != ( j == k ) )
{
throw new RuntimeException( i + " == " + l + " != " + j + " == " + k );
}
if ( ! isImplicatd( j == 0 , i == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( j + " == 0 =!=> " + i + " == 0" );
}
if ( ! isImplicatd( k == 0 , l == 0 ) ) // gilt nur für ABC, nicht für aSd
{
//throw new RuntimeException();
System.out.println( k + " == 0 =!=> " + l + " == 0" );
}
}
private static boolean isImplicatd(
final boolean left ,
final boolean right )
{
if ( left )
{
return right;
}
return true;
}
// BC
static class BC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public BC_Iterator_unlimited()
{
super(
//leftIterable
() -> new B_Iterator() ,
//rightIterable
() -> new C_Iterator() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
// S -> ABC
static class ABC_Iterator_unlimited
extends AbstractCartesianProductIterator<String, String, String>
{
public ABC_Iterator_unlimited()
{
super(
//leftIterator
new A_Iterator() ,
//rightIterable
() -> new BC_Iterator_unlimited() );
}
@Override
String combine(
final String left ,
final String right )
{
return left + right;
}
}
private static void check_ABC_contains(
final String sStr )
{
final Iterator<String> abc_Iterator_unlimited = new ABC_Iterator_unlimited();
while ( ! abc_Iterator_unlimited.next().equals( sStr ) );
// runs infinity when not satisfied
}
}
[/CODE]
Das habe ich mir auch gerade gedacht xD Holy Moly xD@Barista, das ist ja eine halbe Doktorarbeit
Da würde ich den Professoren keinen Vorwurf machen,
Hier hast du einfach das falsche Buch gekauft.
Das Buch ist keine Einführung in die Automatentheorie und ist auch keine Einführung in die Logik.
Es setzt vielmehr fundierte Kenntnisse in der Automatentheorie und in der Logik voraus
und zeigt dann auf, wie man Automatentherie mit Logik und umgekehrt Logik mit Autoamtentheorie beschreiebnen kann.
Oder kurz gesagt: Das Buch ist hilfreich, wenn du eine Masterarbeit über "Automaten und Logik" schreiben willst.
Naja, 4 Stunden Arbeit.
Ich habe im Moment Zeit und bei den Aufgaben, die ich eigentlich machen sollte bin ich fleißig am Prokrastinieren.
Ich musste nur ein bisschen Aufpassen auf Stackoverflows beim Zusammenstecken der Iteratoren.
Deshalb sind es an manchen Stellen Iterables, um lazy zu arbeiten.
Aha, danke.
Dazu noch die Limits, weil sonst die Iteratoren unendlich laufen.
Aktuelle Jobs
-
Wafios Softwareentwickler Cloud (JAVA/Spring) m/w/d - Reutlingen- Gestartet von Java_Jobs
- Antworten: 0
-
Inek Senior Java Softwareentwickler (m/w/d) - Siegburg
- Gestartet von Java_Jobs
- Antworten: 0
-
Atos Senior Java Architekt (m/w/d) - Fürth
- Gestartet von Java_Jobs
- Antworten: 0
-
-
FCA Bank Java-Entwickler (m/w/d) (Heilbronn)
- Gestartet von Java_Jobs
- Antworten: 0
Neue Themen
-
-
Code aus IntelliJ in "Textform" für Word-Paper?
- Gestartet von Miez
- Antworten: 3
-
-
"Hello World"-Programm läuft nicht
- Gestartet von Anfaengerin
- Antworten: 16
-
Java-Buch für erfahrenen Programmierer gesucht
- Gestartet von Apoyando
- Antworten: 5