Theoretische Informatik – die meistgelesenen Beiträge

Hallo

falls ihr das schon gemacht habt, ist das schwer? Bruacht man da viel aufwand?

Ich habe mal gehört dass sich da viele irgendwie die Zähne ausbeißen aber eigentlich ist das mit den Automaten ja ziemlich leicht.

Kann mih da wer aufklräen? Wie schwer ist das ca?

lg

Moin moin. Unszwar geht es darum, dass man die asymptotische Notation zeigen soll, also das log2 (n!) genau so schnell wächst wie (n log2 n), bei der Fakultätsfunktion n! = n* (n-1) * (n-2)...1.

Hierzu muss in Aufgabenteil a) gezeigt werden, dass log 2 (n!) höchstens so schnell wächst wie (n log2 n) und in Aufgabenteil b), dass es mindestens so schnell wächst

Mein Ansatz. Wenn man zwei Funktionen teilt und das Ergebnis gegen unendlich geht, gilt O (höchstens so schnell). Wenn das Ergebnis gegen 0 geht, gilt Ω. Wenn das Ergebnis der Division ein konstanter Faktor ist, gilt Θ. Man könnte also log 2n! durch (n log 2n) teilen und zeigen, dass ein konstanter Faktor rauskommt und daher Θ gilt.

Die Aufgabe zwingt einen jedoch dazu, sowohl O und dann Ω zu zeigen

Ich müsste also log2n! durch (n log2 n) teilen und zeigen, dass es gegen unendlich geht, um O zu zeigen. Aber dann müsste man auch zeigen, dass es gegen 0 geht. Der Ansatz funktioniert also nicht.

Eine andere Möglichkeit wäre

log2 n! <= c * (n log2 n) zu rechnen. Aber dann müsste man auch log 2 n! >= c * (n log 2n) zeigen. Und leider kann ich n! nicht wegkürzen. :(

Hallo Community,

wie ihr im Betreff schon sehen könnt komme ich bei einer Aufgabe nicht weiter. Ich soll einen DEA/DFA (Deterministischer Endlicher Automat) konstruieren, der die Binärdarstellung aller Zahlen "i" akzeptiert, wenn diese durch 5 teilbar sind (i%5=0). Eingabezeichen = binäres Alphabet.

Könnt ihr mit helfen?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Hallo an alle,

Ich habe mal eine Frage:

Wie lang braucht eigentlich eine Nachricht um die Erde über das Internet(theoretisch)? Kann mir bitte jemand diese Frage beantworten, wenn möglich bitte auch mit Quelle(außer Wikipedia). Danke schon mal im Voraus.

Fragen:

=> In welche Komplexitätsklasse fällt das Halteproblem?

Das Halteproblem ist unentscheidbar. Liegt es somit in NP-schwer oder in überhaupt einer Komplexitätsklasse?

Für Sprachen von Typ 3 und Typ 2 gilt, dass diese unter Vereinigung abgeschlossen sind. Was gilt dann für Typ 3 vereinigt mit Typ 2?

=> Ist diese Vereinigung dann auch abgeschlossen?

MFG

Hey Leute,

wie schon in der Überschrift erkennbar, verstehe ich diese zwei Arten von Algorithmen nicht ganz? Besonders was der Unterschied sein soll?

Vielen Dank,

Lyn

Hallo, evtl. kennt sich jemand mit der Pumping-Zahl aus.

Diese ist nämlich jene minimale Zahl p, sodass gilt:

Jedes Wort w aus der Sprache L mit einer Länge von mind. p (also |w| = p) kann in w = xyz aufgespalten werden, derart, dass

1. |xy| <= p
2. y =/= e (leeres Wort)
3. x(y^i)z ist in L

------------------------

Ich hätte mich jetzt gefragt, was die Pumping-Zahl von 0001*, 1011 und ((011) u (1*0*) ist.

-----------------------

Beim Ersten hätte ich p = 4 vermutet. Begründung: x = 000, y = 1, z = e

Dann |xy| <= p, y =/= e, und xy^iz ist in L (weil 000111...11 in L) für jedes i aus IN.

----------------------

Beim Zweiten bin ich mir nicht sicher, ob es da überhaupt eine Pumping-Zahl gibt, weil ich 1011 eigentlich nicht aufpumpen kann. Vielleicht weiß da jemand mehr.

----------------------

Beim Dritten hätte ich eine Pumping-Zahl von 1 vermutet. Begründung: Setze x = e, y = 1 und z = e

Dann |xy| <= p, y =/= e und xy^iz ist in L (weil 111...11 in L) für jedes i aus IN.

---------------------

Stimmen meine Vermutungen? Was mache ich mit dem endlichen Ausdruck 1011?

Ich wollte mal eure meine dazu wissen, ob dieser endliche Automat deterministisch ist oder nichtdeterministisch ist?

Meiner Meinung nach ist dieser Automat nichtdeterministisch, weil es kein eindeutigen Startzustand gibt, da man mit b oder c das Wort anfangen kann.

Lg

Liebes Community,

kann mir bitte jemand erklären, was semi entscheidbar ist? Ich habe den unterschied mit unentscheidbar leider nicht ganz begriffen. Vielen Dank!

Hey, Ich verstehe nicht wie ich folgende Aussagen durch ein Beweiser-Gegenspieler Argument begründen soll.

Hallo , habe ich folgende Aufgabe richtig gelöst ? oder habe ich einen Denkfehler:

Ich habe gesagt es gibt genau 3 Äquivalenzklassen nämlich :

[Epsilon] ,[a] und [z] wobei z elemt von Sigma stern ist aber ohne die Wörter die mit a beginnen.

Jetzt habe ich noch gezeigt das diese alle unterschiedlich sind und das die 3 wirklich alle sind. Hier bin ich mir aber nicht sicher.

Kann mir das eventuell jemand erklären ?

Sigma * ist ja in der Theoretischen Informatik die Kleenesche Hülle. Was ist dann Sigma+ ?

Hallo,
Ich würde gerne die Zahl - 21,25 im IEEE single Format darstellen. Dafür wird die Kommazahl ja erstmal in Binär umgewandelt. Jetzt weiß Ich jedoch nicht genau wie das geht. Ich weiß wie man negative ganze Zahlen im Einerkomplement, Zweierkomplement und Vorzeichendarstellung darstellt, Ich weiß auch wie man positive Kommazahlen darstellt, jedoch weiß Ich nicht wie man dies mit Kommazahlen macht. Mit Ek,Zk Vorzeichendarstellung?
Wäre super wenn mir jemand helfen könnte vielleicht auch mit einer beispielhaften Rechnung :)
Danke schonmal!

Hallo, ich verstehe die Konzept auf Reduktion, und auch Turing machine. aber ich weiss nich wie man mit so Aufgaben umgehen muss.

Meine Lösung:

NFA in DFA umgewandelt

Feedback bitte!

Hi,
kann uns jemand hier erklären, wie man bestimmt welche Flags zu welchen Signalen gehören?
Wir haben im Netz rechachiert, was die Flags machen, aber können es trotzdem nicht richtig zuteilen, weil wir nicht wissen, wie man richtig vorgeht..

LG und vielen Dank!

rechts sind die Möglichkeiten, die man in der Box hinzufügen kann

bei f bin ich mir nicht sicher.
hier sind meine Notizen, falls das hilft:

Vielen Dank im Vorraus!

Auch wenn Duolingo nicht die effizienteste Methode ist, zu lernen, so ist es durch die Gamifizierung schon verdammt effektiv.

Mein Problem ist, dass mein ADHS Hirn so ein System wie Duolingo braucht, um länger als 5 Minuten am Ball zu bleiben.

Gibt es sowas auch für Informatik?

(also für Analysis, Theoretische Informatik etc. auf Studiumniveau)

vielen dank im Voraus! : )

Kann mir bitte Jemand weiterhelfen, diesen NFA/NEA zu konstruieren?

Mit "alle drei" Automaten sind jeweils der Automat von [0-9], [0-9]* und [0-9][0-9]* gemeint.

Für [0-9] habe ich den Automaten:

-->(q0)----[0-9]---->((q2))

Für die restlichen beiden habe ich auch eine Lösung, jedoch wurde mir gesagt, dass wir Epsilon bzw. Lambda nicht benutzen dürfen.

Ich verstehe jedoch nicht wie ich dann 5 Zustände und 6 Kanten erreichen soll beim finalen Automat.

Wir haben in Informatik momentan als Thema Sortierverfahren und jeder im Kurs soll eines vorstellen. Nun, ich habe den Quicksort zugeteilt bekommen und ich soll mich bei diesem ebenfalls mit der Laufzeit auseinandersetzen. Beim Quicksort beträgt die Laufzeit im worst-case O(n^2), was ich ja noch verstehe. Im average und im best-case beträgt diese aber O(n*log(n)) und ich weiß bei Leibe nicht was das heißen soll.

Ich hatte daraufhin mal auf Wikipedia nachgeschaut, aber da stand nur das es sich um ein super lineares Wachstum handelt und ich habe leider keine Ahnung, was das heißen soll...

Wäre nett, wenn das irgendwer zufällig wissen sollte. :)

Guten Abend

Ansatz:

Zunächst erst mal alle unnötig kompliziert gegebenen Funktionen so umschreiben, dass sie sich vergleichen lassen

a (n) = 13n³, kann man nicht mehr vereinfachen

b (n) = log_4 n³ ist nichts anderes als 1,5 log_2 n

c (n) = 9 log_3 n hätt ich jetzt auch nicht weiter vereinfachen können

d (n) = log_2 4 n^4/3 ist nichts anderes als log_2 (4) + log2 (n^3/4), also 2 + 3/4 log_2 n

e (n) = n^log_4 n^4 kann man umschreiben zu n^2 log_2 (n).

Ich hätte die Funktionen also sortiert (von langsam nach schnell):

c < d < b < a < e.

Problem: Mein Tutor meinte die richtige Reihenfolge wäre: d < b < c < e < a.

Ich versteh es nicht. c. hat ja log_3 (n) und das ist ja schon mal langsamer als alles mit log_2 (n). Bei d und b bin ich mir unsicher, weil die ja eigentlich asymptotisch gleich schnell wachsen sollten. b wächst vielleicht bissl schneller weil es mit 1,5 multipliziert wird, während d nur mit 3/4 multipliziert wird.

Großes Kopfzerbrechen bereitet mir die Tatsache, dass e langsamer wachen soll als a. Bei e (n) ist doch das "n" im Exponenten. Auch wenn man im TR z.B. für n = 17 die Funktion e (n) eingibt, also 17^log_4 (17)^4 ist das 2.9210^21, also eine tierisch hoche Zahl. Wärend n = 17 in die Funtkion a(n) eingesetzt, lediglich 1317³ = 63869 ergibt, also viel weniger wächst. Auf desmos kann man die Funktionen plotten, und dort ist e (n) [bzw. ich musste es hier f(n) nennen, weil das Programm den Buchstaben "e" direkt als Euler'sche Phi-Funktion interpretiert] auch viel stärker an der y-Achse dran, also müsste es doch eigentlich stärker wachsen, or?

ich hab da paar Komplexitätsklassen also O Notationen ,die sind bissle komplexer ,kennt ihr einen rechner der die mir sortieren kann nach größe?

Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.

Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:

Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).

In dieser Aufgabe sollte ich den DEA zu einem Automaten zeichnen, der nur Wörter akzeptiert, die nicht "00" enthalten, wobei Σ = {0;1}. Wäre dieser Automat zulässig, bzw. was müsste ich verbessern ?

Ich habe gerade gelernt, dass man jedes Entscheidungsproblem L1 über Σ in P auf jedes andere Problem L2 über Σ aus P reduzieren kann. Mit hat es hier "die Kette rausgehauen":

Eine Reduktion ist ja eine berechenbare Abbildung



jetzt könnte ich festlegen Σ = Natürliche Zahlen von 1 bis 1 Million

L1 = {w ∈ Σ | w ist prim)

L2 = {w ∈ Σ | w ist gerade)

und definieren:

f(w) = 6 wenn w prim

f(w) = 7 wenn w nicht prim

Dies erfüllt genau die obige Definition einer Reduktion.

Nur welchen Sinn macht es, hier von einer "Reduktion" zu sprechen, denn ich habe ja den Primtest auf eine Zahl nicht auf den Test auf Geradheit einer Zahl zurückgeführt.

Ich hätte intuitiv etwas als Reduktion bezeichnet, wenn ich durch die Entscheidung L2 auch L1 entscheiden kann. Hier liegt aber aus meiner Laiensicht ein "fauler Zauber" vor, denn in der Abbildungsvorschrift f ist eigentlich schon enthalten, dass ich dafür schon die Entscheidung auf Prim durchführen, also L1 lösen muss. Es "hört sich aber so an", als könnte man nun einen Primtest (der ja, obwohl in P liegend, relativ komplex ist) auf etwas "reduzieren", wo man nur auf Geradheit prüft (was ja von der Komplexität nicht vergleichbar ist). Jedenfalls ist das nicht im Sinne der Erfindung eines "funktionierenden" Algorithmus für L1, den ich zu lösen vermag, indem ich L2 löse.

Ich hoffe, ich habe mich in meiner Notation verständlich ausgedrückt und man weiß, was ich meine...(bin kein Informatiker, daher bitte Milde walten lassen ;-)

Habe ich eine falsche Vorstellung von einer Reduktion oder ist das einfach so?

Hallo,

ein paar kurze Fragen die ich nicht richtig verstehe:

wie viele terminale und nichtterminale dürfen bei den Formalen übergangsfunktionen auf der rechten Seite vom Pfeil stehen?(links darf immer nur eine nichtterminale stehen?)

reguläre Ausdrücke sind einfach nur eine andere Form von regulären Sprachen? (Wenn nicht, worin unterscheiden sie sich?)

müssen formale Sprachen jedes akzeptierte Wort berücksichtigen oder kann eine sprache auch einfach eine teilmenge aller akzeptierter Wörter sein?

danke für alle hilfreichen Antworten

Wie gibt man die Sprache von der grammatik an , ich komme irgendwie nicht weiter und kann mir jemand sagen wie das geht ?

Die Kontextfreie Grammatik, die erzeugt werden soll ist: "zwischen zwei a´s liegt immer eine gerade Anzahl von b´s"

Jetzt weiß ich aber nicht, wie das funktionieren soll, denn auch ab oder abbabbaaaa wäre in der Sprache enthalten, wie kann ich a´s spammen aber so, dass zwischen zwei a´s nur gerade Mengen von b. enthalten sind. Ebenso für ba, bbba uns.?

falls das eine dumme frage ist, entschuldige ich mich im voraus!

Ich schreibe bald eine Klausur in Digitaltechnik und weiß nicht genau, was in der Lösung gemacht wurde.

Was ich verstehe:

• Ich verstehe den Sachverhalt und:
• Zum Automaten wurde ein endlicher Automat erstellt.
• Es gibt drei Zustände und zwei Ausgänge. Anschließend wurde eine Wahrheitstabelle erstellt.

Was ich nicht verstehe:

• Wie die Eingänge im Automaten zustande kommen
• Wie man die Wahrheitstabelle erstellt hat
• Was bedeutet ,,alt" und ,,neu" in dem Kontext?
• Wie kommt die Anordnung der 0en und 1en in der Tabelle zustande?
• Wieso wurden nur die MIN-Terme der ,,neuen" Zustände hergeleitet?

Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?

Hallo, ich hänge an der Aufgabe 9, ich weiß nicht wie ich weiter kommen soll. Hat jemand eine Idee oder einen Lösungsvorschlag?

danke im Voraus!

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

m >= 1, d. h. das kürzeste Wort in der Sprache hat die Länge 3m bzw.

|z| = 3n > = n

D. h. wenn mein n = 1 ist, dann hat mein Wort die Länge 3.

Jetzt muss ich eine Aufteilung von |vwx| wählen, dass gilt |vwx| <= n

und dann beim pumpen das Wort Teil meiner Sprache bleibt.

|vwx| <= 1 geht nicht. Macht keinen Sinn, ich muss ja a und b und c einzeln pumpen. a,b,c hat mindestens die Länge 3. Somit macht n = 1 keinen Sinn. n = 2 geht auch nicht. Ich muss mindestens n = 3 wählen. Also z = aaabbbccc nun muss ich |vwx| <= 3 wählen, d. h. ich kann nur 2 von den 3 Symbolen (einzeln) pumpen. ab und c oder a und bc , das macht keinen Sinn.

Fazit:

Man müsste a b c separat (einzeln) pumpen, damit das erzeugte Wort Teil meiner Sprache bleibt, dies ist hier aber nicht möglich egal wie man v und x wählt.

Langt dies als Begründung, oder wie argumentiert man hier am besten?

|z| = 2n >=n das kürzeste Wort hat die Länge 2 somit hat auch mein n mindestens die Länge 2.

Wieder muss ich |vwx| so wählen, dass gilt |vwx| <n und beim pumpen dann das Wort Teil meiner Sprache bleibt.

Wie wähle ich nun hier u, v, w, x, y?

Hey, ich habe folgende Aufgabe:

Aufgabe a habe ich hinbekommen, aber bei Aufgabe b bin ich planlos.

Kann mir da jemand helfen?

Hi, also ich verstehe bei dieser Aufgabe in der Lösung den letzten Schritt im Induktions Schritt nicht so ganz:

Gruß

Hey :)

ich hab hier eine Aufgabe zu endlichen Automaten und einen Lösungsansatz.

Aufgabe:
Es soll ein endlicher Automat gezeichnet werden, der eine gerade Anzahl an Nullen akzeptiert.

A = {0,1}

Meine Lösung:

Ich komme leider nicht weiter beim Beweisen. Wie kann ich beweisen dass RoS nicht dasselbe ist wie SoR. Vorgegeben ist es mittels Prädikatenlogik zu lösen. Ich hab leider keine Vorstellung davon wie ich RoS so umformen kann dass ich beweise dass es ungleich SoR ist. Jede Antwort würde helfen!!

Danke im Voraus

Checke irgendwie nicht, wie ich überprüfen soll, mit dem pumping-Lemma, ob eine Sprache regulär ist oder nicht.

Hallo alle zusammen,

ist es egal, wo was n und m steht? Also bei welchem Attribut?

Beispielsweise habe ich die Attribute Mitarbeiter und Projekt... steht das n oder das m bei Projekt und was bei Mitarbeiter?

Dankeschön!!

Das Marienkäfer namens Kara soll verschiedene Baumstämme mit Kleeblättern ausfüllen. Hierfür soll ich einen Algorithmus entwickeln aber ich habe keine Idee wie. Hat jemand vielleicht einen Plan? Die Aufgabe ist aus der 10. Klasse Informatik Grundkurs

Guten Abend,

ich bin bei meiner Klausurvorbereitung auf folgende Aufgabe gestoßen:

Gegeben ist die Sprache 𝐿, die durch den regulären Ausdruck 𝑝(𝑖|𝑎) (𝑝(𝑖|𝑎))∗𝑝𝑜 erzeugt wird.

Geben Sie den Übergangsgraphen eines deterministischen endlichen Automaten (DEA) an, der die Sprache 𝐿 akzeptiert. 

Dafür habe ich folgendes entworfen.

Meine Frage ist nun, was ich an den roten Fragezeichen hinschreiben kann. Es kann kein p sein, da es kein DEA mehr wäre. Wie würdet ihr es lösen?

Danke

Gibt es vielleicht hier Mathematiker die beides belegt haben, wenn ja was empfindet Ihr als entspannter?

Hi,

Im Unterricht haben wir mit theoretischer Informatik und endlichen Automaten begonnen. Mein Lehrer hat uns ein Beispiel mit einem Lachautomaten gezeigt, bei dem aber nur ha/haha/hahaha/... ausgegeben werden kann. Dann hat er uns die Aufgabe gegeben, dass wir diesen Automaten so umgestalten/ erweitern sollen, damit er zusätzlich auch hi/hihi/hihihi/... und ho/hoho/hohoho/... ausgeben kann. Wir hatten keine Zeit mehr und nur einer hat es oberflächlich an die Tafel gemalt... als ich dann nachgefragt habe, konnte es mir selbst der Lehrer nicht erklären. Um es zu verstehen möchte ich die Aufgabe aber lösen, habe aber noch nicht mal einen Ansatz. Kann mir jemand helfen? Und geht das überhaupt? Es soll doch ein endlicher Automat sein. es ist auch ein Bild von der Lachmaschine bei der Aufgabe soll das Ausrufezeichen aber nicht Teil des Eingabealphabets sein.

Schonmal Danke, wenn mir jemand helfen kann!!!

PS das ist KEINE (!) Hausaufgabe

Ich habe große Probleme bei der Chomsky Normalform.

Im ersten Schritt soll man ja die ε-Übergänge entfernen. Ich bin mir in dem Beispiel nicht sicher wie ich das machen soll und wie ich mit D verfahren soll. Aus D kann man ja nur ε ableiten und es kommt ja nur bei A zum Einsatz, bei welchem man 01 ableiten kann. Das ε ist ja dabei total irrelevant. Daher die Frage ob man das D nicht eigentlich ganz entfernen könnte.

Mit L1, L2 und L3 seien drei beliebige Sprachen.

Warum ist die folgende Aussage falsch? Siehe das Gegenbeispiel. Bitte es so erklären, dass es auch jemand versteht der nicht Mathematik studiert hat.

Warum kommt links im ersten Bsp. das leere Wort raus und Rechts nicht das leere Wort?

Bitte es so erklären, dass es auch jemand versteht der nicht Mathematik studiert hat.

Gibt es eine maximale Speichergröße die in einem System vorhanden sein kann und hängt die damit zusammen wie viele bit ein System hat ? Die Frage ist nur theoretisch und hat für mich keinen praktischen Nutzen.

Meine Überlegung:

Wenn eine Speicheradresse maximal 64bit lang sein kann dann kann es doch auch nur nur begrenzte bit im ganzen System geben die korrekt angesteuert werden können ?

Bsp: Für 64bit binär gibt es dezimal 2^64 Möglichkeiten also doch auch 2^64 verschiedene Adressen. Aufgrund dessen das jede Speicheradresse 64bit enthält kommt ich auch ein ganzes von (2^64)*64bit womit ich auf ein totales von

(2^64)*8*(0,1^15) petabyte = 147.573 petabyte

Oder

147.573.952 GB

Das sind natürlich utopische Mengen, jedoch bei einem 32bit system wären es dann nur

17,18 GB

Also wo liegt mein Denkfehler ?

Meine Kenntnisse vom Aufbau eines Computers sind nicht überweltigend, jedoch will ich ja was lernen also wenn die Antwort mit Google-recherche zu verstehen ist bin ich zufrieden.

Vielen Dank schonmal vorab

Aufgabe:

Mein Problem hierbei ist, ich verstehe nicht, warum die zyklische Wartebedingung aufgehoben wurde. Es gibt ja immer noch Prozesse die die gleiche Gabel wollen und warten müssen, wenn einer die zuerst erhalten hat? Dadurch habe ich doch zyklisches warten?

Kann mir bitte jemand bei meinen Hausaufgaben helfen? Ich kann das alleine nicht :(

"Negieren Sie folgende Aussage formal (De Morgansche Regeln):

((x>14 ^ x<20) v (x>21 ^ x ≤34))

In Ihrem Ergebnis sollen nur mehr die logischen Operatoren UND (^) & OR (v) vorkommen (keine Negation!)"

Guten Abend,

ich würde gerne Informatik studieren an einer Hochschule, da der Matheanteil dort geringer ist und mehr Wert auf Programmieren gelegt wird.

Hier sind alle Module der Hochschule, ist der Matheanteil an dieser HS wirklich gering? Ich sehe nur drei Mathe-Module und der Rest scheint hauptsächlich IT zu sein. Ich habe im Mathe LK immer zwischen 10-13 Punkten bekommen aber Analysis, Algebra und Stochastik haben mir relativ viel Spaß gemacht.

Zudem frage ich mich was mit "Grundlagen der Informatik" oder "Theoretische Informatik" gemeint ist, könnte mir das jemand erläutern?

Ich habe bis :

hA(n) ist Turing Berechenbar genau dann wenn , eine Turing Maschine existiert die auf Input n eine 1 schreibt falls n element A und ansonsten unendlich läuft. Was Äquivalant dazu ist, dass A semi entscheidbar ist.

also ist die Menge ja gleichmächtig wie die Menge der semi entscheidbaren Sprachen ? oder nicht?

sind die Semi entscheidbaren Sprachen denn abzählbar unendlich ? wenn ja wie beweise ich das wenn nein wo ist mein Fehler ?

Ich wäre sehr dankbar, wenn mir jemand behilflich sein könnte. Außerdem weiß ich nicht wie ich m ungleich n graphisch darstellen kann..

Lg

Hallo,

ich habe vor kurzen über die O Notation eines Algorithmus gelernt und da gibt es die O Notation O(log(n)) und da habe ich mich gefragt welche Sortieralgorythmen haben diese O Notation. Nach Recherche habe ich leider nichts gefunden. Kann mir da wer weiterhelfen?

Grammatik für Uhrzeit (HH:MM:SS) aufstellen und welcher Typ

Ich weiß die Stunden können von 00 bis 24 gehen, die Minuten von 00 bis 59 und die Sekunden von 00 bis 59

S -> A

A -> ...

Wie krieg ich das als Grammatik einer formalen Sprache hin?

Hallo, es geht um theoretische Informatik.

Meine Frage ist, wo liegt der Unterschied zwischen formaler und akzeptierter Sprache? Formale Sprache ist eine Menge von Wörtern, welche sich aus den, im Alphabet befindenden Zeichen zusammensetzen lassen. Akzeptierte Sprache, bzw. L(A) ist eine Menge der akzeptierten Wörter, welche vom Startzustand aus auf einem akzeptierten Zustand enden.

Keine der beiden Mengen muss alle Wörter beinhalten.

Wenn ich eines oder vielleicht sogar beide der Begriffe falsch verstanden habe, dann klärt mich bitte auf und sagt mir, ob es sich bei den beiden Begriffen, um das Gleiche handelt, oder ob eine Grundlegend anders ist als das andere.

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

1. Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
2. Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

1. Ist die Analyse korrekt?
2. Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
3. Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

Hallo,

ich würde gerne ack(3,3) und ack(4,4) berechnen, nur sind die Zahlen so groß bzw die Rekursionstiefe so groß, dass keins meiner Programme dies berechnen kann.

Gibt es eine Möglichkeit die Zahlen herauszubekommen?

Wie viele Äquivalenzklassen dieser regulären Sprache gibt es, die Lösung ist nachfolgend angegeben.

Lösung:

Wie man sieht gibt es hier genau 3 Äquivalenzklassen.

Was mich verwundert ist, warum man hier epsilon selbst als Äquivalenzklasse berücksichtigt? epsi mit Präfix ac steht doch nicht in Relation zu epsi mit präfix abc oder epsi mit Präfix abbc ...?

Anderes Bsp. Sprache ist wieder regulär

....

Es gibt unendlich viele Äquivalenzklassen. Soweit klar!

Warum berücksichtig man jetzt hier in dem Bsp. nicht epsilon selbst als Äquivalenzklasse, wie in dem Bsp. zuvor

epsi + Präfix ab oder epsi + Präfix aabb oder epsi + Präfix aaabbb...

Kann mir dies bitte jemand erklären. Danke!

Hi, kann mir wer erklären wie genau der Diagonalisierungsbeweis funktioniert, verstehe diesen noch nicht ganz:

Also, ich verstehe nicht ganz warum dies am Ende ein Widerspruch ist dann. Ist es so gemeint, dass wir ja anfangs mit der Turingmaschine R die Diagonale definiert haben und dann mit D die R nutzt , grad das Gegenteil auf dieser Diagonalen stehen muss, was ja nicht gehen kann?

Gruß

Ich soll einen Keller Automaten zur folgenden Sprache erstellen

L={a^3nb^2n | n>=0}

Ich weiß ehrlich gesagt nicht, wie dieser Automat aufgebaut ist. Ich soll ein Diagramm erstellen. Ich weiß allerdings nicht wie das für ein Kellerautomat für dieses Sprache geht

Hallo, ist die Kleenesche Hülle eine Menge, oder nicht?

Oder, ist sie nur ein Operator, der auf irgend eine Menge L (von mir aus) angewendet wird, und daraus die neue Menge L* entsteht ?

Ich verstehe die Rechnung aber was wenn das Codewert mit 1 endet anstatt mit 0, am Ende wird ja dann eine 1 runtergezogen anstatt die 0. Hieße das das der Codewort falsch ist?

Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.

Bzgl. der Komplexität ist es NP-schwierig.

O(k^n) Komplexität

Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.

Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.

1 Reihe, die Wörter sind alle Elemente der Sprache, man würde als Präfix epsi dranhängen. Klar soweit

2 Reihe hier fehlt jeweils ein b, damit die Wörter Elemente der Sprache sind

3 Reihe: alle anderen Wörter. Dies verstehe ich nicht:

{a } hier fehlt ein einzelnes b. Oder ist dieses {a} eigentl. schon in der 2 Reihe dabei?

{ epsi} hier fehlt ab , dies müsste die 3 Reihe darstellen, auch wenn hier steht alle anderen Wörter
Warum gibt es hier "genau" drei Äquivalenzklassen?

Pumping Lema für kontextfreie Sprachen Typ 2.

Das Wort z lässt sich in uvwxy zerlegen und |z| >= n

Untere Grafik:

=> Eine Variable muss doppelt vorkommen. Klar!

=> Unteres A wird vom oberen A abgeleitet. Klar!

|vx| darf nicht leer sein => Vorgegeben. A -> AB über ok.

Fragen:

=> Warum teilt sich A immer "genau" in vwx auf? Warum nicht in uvw oder wxy?

Wenn ich pumpe wächst mein v und mein x. d. h.

uv^iwx^iy

Nehmen wir ich habe das Wort z = abababab d. h. n = 8

=> Wie soll man jetzt hier uvwxy wählen um zu zeigen, dass das Wort das PL erfüllt oder nicht. Wie geht man hier am besten vor. Mir ist dies ehrlich gesagt nicht verständlich, wie ich hier vorgehen soll.

Hallo leute,

weiß jemand wie man das darstellt?

Man muss die Laufzeit in 0-Notation bestimmen von dem Algorithmus ggT (größten gemeinsamen Teilers). Also Schritt für Schritt z.B:

0(1)

0(1) => T(0) = 0(1)

......

wäre super wenn das jemand könnte. :)

Lg

Es geht um Modul: Theoretische Informatik. Ich lerne gerade für die Klausur. Ist es so richtig? Leider habe ich keine Lösung dazu, deswegen bin ich mir unsicher.. Danke im voraus ❤

Hallo,

wir hatten folgende Klausuraufgabe:

Wie sieht der Bildschirmausdruck

short x;
char c;
System.out.println("x: "+x); 
System.out.println("c: "+c);

aus, wenn die Variablen im Speicher auf folgende binäre Werte gesetzt sind:

x: 1011 0000 1110 1010
c: 0000 0000 0101 1001

Meine herangehensweise wäre für den Char C

0101 1001b -> 59h -> 'Y' (ASCII)

Für den short Wert x ist mir allerdings nicht ganz klar wie das funktioniert. Kann mir hier zufällig jemand helfen?

Ich hab mal so eine Frage bzgl. Algorithmen und Datenstrukturen. In unserer Übung sollen wir beurteilen, ob ein Kochbuch ein Algorithmus wäre und dabei bin ich während einer Recherche ins grübeln gekommen.

Erstmal ist natürlich klar, dass ein Algorithmus eine endliche Abfolge von genau definierten Anweisungen zur Behebung eines Problems ist. Nun muss man bei einem Kochbuch bedenken, dass Anweisungen wie "Eine Prise Salz" nicht genau definiert sind und auch bei der Durchführung es unterschiedliche Resultate geben würde, z.B auf Grund verschiedener Backöfen, Kochtöpfe etc. was der Definition eines Algorithmus widersprechen würde. Wenn man wiederum die Umgebung digital simulieren würde, wäre das Resultat immer identisch.

Daher wollte ich euch mal fragen, wie ihr darüber denkt und ob ein Kochbuch ein Algorithmus wäre oder nicht

Hier ist mein Ansatz. Ich bilde eine Typ-2 Grammatik zu dieser Sprache. Es gilt, dass zu jeder Typ-2 Grammatik eine Typ-2 Grammatik in CNF existiert. Wäre das ein Ansatz um zu zeigen, dass eine Sprache vom Typ-2 ist?

Gibt es noch andere Möglichkeiten? Ich könnte theoretisch auch einen PDA aufzeichnen oder?

Hallo, ich bin auf eine schwierige Aufgabe bezüglich des Pumping Lemmas für reguläre Sprachen gestoßen und ich komme nicht weiter bei der Zerlegung eines Wortes s in xyz. Es handelt sich um die Sprache L = {a^n b^m c b^m a | n, m aus den natürlichen Zahlen}.

Ich hatte als s ursprünglich a b^p c b^p a gewählt, aber ich verstehe nicht, wie man hieraus einen Widerspruch formen kann, denn wenn sich y bloß aus a's zusammensetzt, wird das Pumping Lemma hier ja erfüllt.

Danke im Voraus!

Die folgende Grammatik einer Programmiersprache ist in EBNF gegeben:

Übertragen Sie diese Grammatik in die klassische Grammatiknotation. Nehmen Sie verständliche Namen für die Nonterminalsymbole.

Hey Leute, könnt ihr mir bei diesem Übungsbeispiel helfen?

a* a|b ab sind reguläre Ausdrücke. Hier die Aufgabe:

Wie geht man bei a) sowie b) am besten vor? Um den regulären Ausdruck zu erzeugen?

In der Regel geht man so vor, das man aus einer Sprache L(G) mit einer Grammatik einen NFA(Nichtdeterministischen Automaten) konstruiert. Dann aus dem NFA eine DFA (Deterministischen Automaten) und daraus wieder die Sprache mit Ihrer Grammatik ableitet L(G).

L(G) zu NFA zu DFA zu LG?

Was ich mich jetzt Frage ist, kann man auch anders herum vorgehen, d. h. man aus einer L(G) einen DFA und aus diesem dann einen NFA und daraus leitet man wieder seine Grammatik ab?

Oder ist diese Vorgangsweise um einiges komplizierter als von

LG zu DFA zu NFA zu LG

Alphabet sigma = {0, 1}

Für d) L4 beinhaltet doch alle Wörter über sigma oder?

Für c) Die Wörter in L2 werden ja aus dreier Blöcke gebildet (sigma^3)

Wenn L3= sigma* \ L2 gilt sollte doch Wörter der Länge != 3n , die 101 als Teilwort enthalten, auch in L3 liegen. Dann gilt aber L3 = L2^c. Welcher ist richtig?

Hey könnte mir bitte jemand bei den Aufgaben helfen?

Entwerfen Sie einen DFA, der die Sprache L erkennt, wobei L wie folgt definiert ist:

L = {w ϵ {0,1}* | w endet mit 010 oder mit 01}

a) Geben Sie 3 möglichst unterschiedliche Worte aus L an.

b) Geben Sie 3 möglichst unterschiedliche Worte an, die nicht zu L gehören.

c) Geben Sie den DFA sowohl durch einen Zustandsgraph als auch seine Transitionstabelle an.

Vielen Dank im voraus!

Hier sei eine angeblich "einfache" Aufgabe, einen NEA zu erstellen, doch ich verzweifle:

Ich verstehe das Konzept von Automaten nicht bzw ihren Sinn. Was genau sind Automaten in der Informatik? Für was gibt es sie? Und sind sie wichtig im beruflichen Leben als Informatiker?

ich soll mit Pumping-Lemma beweisen, dass die folgende Sprache nicht regulär ist: L={0^m1^n|n!=m}

ist mein ansatz richtig so? :

sei n element N,

sei k >= 1 und setze w = 0^n1^(n-k) mit w element L und |w|>=n,

zerlegung w = xyz mit |xy|<=n und y nicht leer,

dann xy= 0^p mit p<=n, y=0^k mit k>=1,

setze i=0 --> xy^0z=0^(n-k)1^(n-k)

somit ist xy^0z nicht in L und L nicht regulär

0 und 1 wird kodiert zu

000 und 111

Das sind unsere Codewörter. Die Hamming Distanz ist 3.

Jedem dieser Codewörter wird nun ein Fehlercodewort zugeordnet, das sich in einem Bit unterscheidet, also 001, 010, 100 gehören zu 000 und kann korrigiert werden. Bei 111 analog vorgehen.

Da die Hamming Distanz 3 ist, kann 1 Bit Fehler korrigiert werden. Aber anscheinend können 2 Bit Fehler erkannt werden, warum?

000 wird zu 011 (zwei Bit Fehler) und das wird korrigiert zu 111 (ist dem eben am ähnlichsten)... Damit ist die Korrektur falsch und Hamming, liefert meiner Meinung Schwachsinn...

Dieser Algorithmus läuft ja immer linear, warum insertionsort nicht, der ja auch eigentlich nur Vergleiche vollzieht?:

Lösung n-1 vergleiche überall,

Könnte mir vielleicht jemand helfen. Ich komme bei einer Aufgabe gar nicht klar.

4) Schreiben Sie reguläre Ausdrücke für folgende Sprachen über dem Alphabet Σ = {a,b,c}.

a) Die Menge aller Wörter über Σ, die nicht mit c starten.

b) Die Menge aller Wörter über Σ, die höchstens ein b besitzen.

c) Die Menge aller Wörter über Σ, die mit einem anderen Zeichen enden als sie starten. Beispielsweise befinden sich babc in der Sprache, während sich bacb nicht in der Sprache befindet. Hinweis: Die Wörter haben mindestens die Länge 2.

Danke für die Hilfe

1. Ist eine platzbeschränkte Turing-Maschine immer zeitbeschränkt?
2. Ist eine zeitbeschränkte Turing-Maschine immer platzbeschränkt?

Auch wer keine Ahnung von Informatik hat sollte sehen, dass hier was falsch ist, oder peile ich gerade einfach was nicht?

Kurz zur Erklärung:

Terminal = la oder le oder lu

Nicht-Terminal (quasi ne Variable) = S, A, B...

Erst steht im Buch folgender Satz:

Dann das auf der nächsten Seite (beachtet nur die rechte Blase):

Dort steht nun es könnte ein Nicht-Terminal alleine stehen. Darunter sieht man aber ganz klar ein Terminal (das lu) alleine! Dass ich hier eig. nichts verwechsle beweist doch der Satz im 1. Bild, oder was verstehe ich nicht?

P.S. Hier werden gerade reguläre Sprachen bzw. Grammatiken definiert.

A --> Ba (linksreguläre Grammatik)

A --> aB (rechtsreguläre Grammatik)

Wieso ist " a " nichtterminal?
Wieso ist das Erste links- und das Zweite rechtsregulär?

also eine 90% Chance auf ein positives Ergebnis

Hallo, kann mir jemand bei der Aufgabe helfen? Ich verstehe gar nichts.

Die Aufgabe b)

Vielen Dank schonmal in vorraus.

Also für alle, die nicht wissen, was es ist, es ist eines der Millenium Probleme, welches noch nicht gelöst wurde.

Kurze Zusammenfassung der Frage des P-NP Problems:

Bedeutet die Fähigkeit, korrekte Antworten schnell zu erkennen (NP) auch, dass es eine schnelle Möglichkeit gibt, diese Antworten zu finden (P)?

Beispiel:

Man hate einen Zauberwürfel mit auf jeder Seite hunderten Feldern, sobald er "gelöst" wird, kann man schnell erkennen, ob er richtig oder falsch gelöst wurde, allerdings würde man (nach dem heutigen Wissensstand) nahezu ewig brauchen, um ihn überhaupt lösen zu können, die Frage ist da halt: gibt es eine Möglichkeit, ihn schnell lösen zu können, da man ja auch schnell sehen kann, ob er richtig oder falsch gelöst ist.

Meine "Lösung" (als Gedankenexperiment; noch nicht rechnerisch nachgewiesen):

Man will ein Passwort hacken, weshalb man einen Algorithmus schreibt, welcher die Passwörter einzeln durchgeht (Problem in NP). Da wird ja schnell erkannt, ob ein Passwort richtig oder falsch ist (dadurch, dass man dann eingeloggt ist oder eben nicht), allerdings gibt es keine Möglichkeit, es anders herauszufinden, da es eben einfach keinen anderen Lösungsweg gibt. Also gibt es auch keinen schnelleren Lösungsweg, weshalb nur an diesem Beispiel theoretisch nachgewiesen wäre, dass P≠NP ist oder?

Ich würde mich über sachliche Antworten sehr freuen, mir ist bewusst, dass meine Antwort vermutlich viel zu einfach ist, damit sie als Lösung gesehen werden könnte und das andere Leute diese Idee vermutlich auch schon hatten. Mich würden nur eure Gedanken dazu interessieren!

for i := 0; i < len(n); i++ { // O(n)

  for j := 0; j < len(n); j++ { // O(n)

    if x >= 30 { // O(1)

      for k := 0; k < len(n); k++ { // O(n)

        value = value + 10 // O(1)

      }

    } else {

      value = value + 2 // O(1)

    }

  }

}

ich hab den code und soll die Komplexitätsfunktion angeben ansich komm ich klar nur hab ein ein problem bzw ich stimme nicht mit chat gpt ein er sagt nähmlich=

O(n)(O(n)(O(1)+O(n)O(1)+O(1)))+O(1)

ich verstehe aber das erste + net ich hätte jetzt mal gesagt

also: O(n)(O(n)(O(1)*(O(n)O(1))+O(1)))+O(1)

Moin, ich wüsste gerne, ob das hier richtig ist und wenn nein, was könnte ich besser machen?

Hallo weiß jemand wie man hier das Pumping Lemma anwedet ?

Zeigen Sie mithilfe des Pumping-Lemmas, dass die Sprache

L={w∈Σ∗: |w| ist eine Primzahl } über dem Alphabet Σ = {”Frohe“,”Adventszeit“} nicht regular ist.

Ist nicht jede Sprache eine reguläre Sprache?

Man kann doch einfach folgenden DFA konstruieren:

Startzustand gleichzeitig akzeptierter Zustand, Übergangsfunktion verweist für jede Eingabe auf den Startzustand. Ist das denn nicht etwas witzlos?

Meine Frage besteht darin, ob sich das Kellersymbol, welches zu Beginn im Keller ist, nennen wir es #, entfernen lässt.

Hallo,

Ich habe Probleme diese Aufgabe zu lösen und weiß nicht, wie ich das am besten machen kann. Kann das jemand lösen? Es reicht, wenn nur das Zeichen pro Nummer mit Begründung geschrieben wird.

Meine Antwort dazu wäre:

1. x (A C B)

2. x (A C B)

3. x (A C B)

4. x (B C A)

5. x (B C A)

6. =

Folgender selbst selbst erdachter NEA akzeptiert die Sprache die aus den Wörtern die mit 01 oder 11 beginnen.

Wenn ich den in ein DEA umwandeln möchte, bin ich mir nicht sicher, wie ich mit nicht definierten Übergängen (In dem Fall 0 bei q1) umgehen soll.

kann man bei der programmierung mit mehreren threads, aus auf einem system ausgefürt werden soll, welches eine nebenläufiige ausführung unterstützt deterministische ausführung gewährleisten? wenn ja wie, wenn nein warum