Regulären Ausdruck zu DFA finden mittels Algorithmus (Kleene)?

Das ist eigentlich eine Informatikeraufgabe aber da bekomme ich keine Antwort, weshalb ich mit großer hoffnung hier meinen Versuch wage

Ich soll in der Aufgabe (siehe Bild) mittels Algorithmus einen regulären Ausdruck für den Automaten finden, indem ich die Rekursion bis k=0 ausführe.

Bild zum Beitrag

Aufgabe

Bild zum Beitrag

Formel

Bild zum Beitrag

Meine Lösung

Bis zum letzten Schritt hat alles gut geklappt, jedoch habe ich gemerkt, dass man von q2 zu q3 mit b gar nicht kommen kann, weshalb mein letztes Ergebnis ( r ^1 _[2, 3] = a | b ) falsch sein muss, aber ich finde meinen Fehler nicht.

0 Antworten

Hi, ich lerne zurzeit den Algorithmus, um einen NFA zu einem DFA umzuwwandeln. Was ich hierbei nicht verstehe, z. B. beim markierten Puntk. Ich befinde mich bei {q0,q1}. Warum befinde ich mich bei {q0,q2}, wenn ich von dort aus eine 0 habe?

Wenn wir uns den NFA anschauen, so ist ja bei q1, wenn ich dort eine 0 oder eine 1 habe nur die Möglichkeit, dass ich zu q2 gehe und nicht bei q1 bleibe?

...zur Frage

NFA in DFA überführen Potenzmenge sehr groß?

Hallo,

ich wäre sehr dankbar, wenn mir jemand im Teil b) der Aufgabe weiterhelfen könnte:

Meine Lösung a)

0(1)*(101|01(0)*0)(0*1*)* als regulärer Ausdruck

b) Die Nichtdeterminus Stellen habe ich markiert im NFA

Jetzt soll man noch den NFA in einen DFA überführen. Normal bildet man doch jetzt die PotzenMenge, dies wären 2^7 = 128 Zustände (und arbeitet dort die Verbindungen ab...)

=> Dies kann man doch sicherlich einfacher lösen.

Bitte es so erläutern, dass es auch jemand versteht der nicht Profi in den Formalen Sprachen ist. Danke!

=> Wie sähe der DFA am Ende aus?

...zur Frage

Was muss ich bei der Bewerbung bzw. Lebenslauf angeben?

Hey,

ich habe das Gymnasium mit einem Realschulabschluss bzw. mittlerer Reife verlassen. Dazu sei noch gesagt, ich habe die Q1 bis zur Q3 gemacht, für die Q4 hat es nicht gereicht, habe also die Q2 wiederholt. Ich hätte nach der Q3 mit der Fachhochschulreife abgehen können, habe aber wiederholt und die Q2 nicht mehr geschafft. Nun habe ich die mittlere Reife, die ich ja schon nach der 10. Stufe hatte und möchte mich für eine Ausbildung bewerben.

Was gebe ich dann an? Welche Zeugnisse muss ich vorzeigen? Die drei letzten Zeignisse wären ja die neue Q2, Q3 und die vorherige Q2.

Außerdem möchte ich nach der Ausbildung die Möglichkeit haben zu studieren, weshalb ich eine Fachhochschulreife bzw. einen Abschluss der Fachoberschule bräuchte. Wie kann man das erwähnen?

Ich weiß, es ist bisschen kompliziert, ich hoffe, ihr könnt mir helfen. Es ist leider echt dringend, morgen früh müsste ich die Bewerbungen alle abschicken.

Ich hoffe, ihr könnt mir helfen.

Danke euch und viele Grüße

Sophie 😘

...zur Frage

Quadratpflanze?

Ich brauche Hilfe bei den folgenden Aufgabe.

Die Seitenlänge des ersten Quadrates ist 1m. Täglich kommt eine Generation kleinerer Quadrate dazu, deren Seitenlänge nur noch ein Drittel der vorherigen Quadrate beträgt.

A) Berechne den Umfang der Pflanze Q1 Q2, Q3, Qn.

B) Berechne den Flächeninhalt der Pflanzen Q1, Q2, Q3, Qn.

ich weiß nicht, wie ich vorgehen soll.

Danke im Voraus :)

...zur Frage

Umkehrung der LinkedList in Java? Rekursion/Iteration?

Guten Tag zusammen,

Bin lange an der Aufgabe gesessen eine Umkehrung für eine LinkedList in Java zu schreiben und habe schlussendlich eine etwas umständliche Lösung gefunden (die aber immerhin funktioniert :):

Ich vermute, dass es ganz simple Lösungen (ohne Umweg über Array) mittels Rekursion oder Iteration gibt, bin aber einfach nicht drauf gekommen. Weiss jemand wie man eine Lösung schreiben könnte? Vielen lieben Dank für eure Hilfe.

Als Ergänzung der Source Code zum Node und der LinkedList:

...zur Frage

Deterministischer endlicher Automat aus regulärem Ausdruck?

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

...zur Frage

Rekursiver Algorithmus für Fakultät - mathematisch?

Hallo,

ich habe ein Problem mit einer bestimmten Informatik Aufgabe und finde dazu ebenfalls keine (verständliche) Hilfe im Internet.

Wir haben das Thema Rekursion bzw. die Mathematische Definition dieser und ich steig da nicht wirklich durch...

Würde mich über eine Erklärung oder eine Weiterleitung z.B. zu einem hilfreichem Video freuen.

Danke im voraus
Lg

PS: Im Anhang habe ich die Aufgabe, welche ich nicht verstehe.

...zur Frage

Sortieralgorithmus Flussdiagramm?

Hallo,

ich habe versucht folgende Aufgabe mittels einem Flussdiagramm darzustellen und wollte mal nachfragen ob das so funktioniert:

"Nach Eingabe einer Liste[n], welche n Zahlen enthält, soll das Programm die Zahlen der Liste von Position 1 bis Position n aufsteigend sortieren und anschließend die sortierte Liste wieder ausgeben."

Ich habe den Bubble-Sort Algorithmus verwendet.

MMN kommt die Liste korrekt sortiert heraus. Liege ich da richtig oder ist mir bei zeichnen des Diagramms ein Fehler unterlaufen?

MFG

...zur Frage

Mathematische Reihe zusammenfassen (mit Summenzeichen?)?

Wie kann man diesen Ausdruck zusammenfassen?

In einer Aufgabe davor waren die Exponenten 0,1,2,3,... weshalb man es mit einem Summenzeichen k=0 bis i von 1/2^k zusammenfassen konnte.

Aber wie funktioniert es hier jetzt?

...zur Frage

Formale Grammatik Grundregeln?

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

...zur Frage

Zeigen Sie anhand der Summengleichung der Fotosynthese, weshalb die CO2-Aufnahme ein geeignetes Maß für die Messung der Fotosyntheseintensität darstellt?

Kann mir jemand bei dieser Aufgabe in Bio (Q2) weiterhelfen? Komme echt nicht auf die Antwort... 🥺

...zur Frage

Java Rekursion mit Potenzzahlen?

public static void main(String[] args) {
		System.out.println(potenzRechner(4,3));
	}

	public static int potenzRechner(int potenzzahl1, int potenzzahl2) {
		
		if (potenzzahl2 == 0) {
			return 1;
		} else if (potenzzahl2 == 1) {
			return potenzzahl1;
		} else {
			return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);
		}
	}

Ich habe den Code oben mit einer Rekursiven Methode, der die Potenz der mitgegebenen Zahlen (in dem Fall 4 und 3) errechnet. Jedoch kann ich nicht 100% nachvollziehen was im letzten else Zweig passiert.

(return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);)

Wird Potenzzahl1 (4) nicht mit sich selbst (4) mal genommen, und das Potenzzahl2 (2) mal? Also 4 * 4 * 4 = 64? Und das solange bis Potenzzahl2 bei 1 ankommt. Also (4^3) 4 * 4 * 4 = 64, (4^2) 4 * 4 = 16, (4^1) 4 = 4. Oder verstehe ich was falsch? Dann sollte doch theoretisch das Ergebnis (64) beim ersten durchlauf schon rauskommen, für was dann eine Aufgabe bei der man das Rekursiv machen soll?

Zusammengefasst: Kann mir jemand auf gut Deutsch diesen Ausdruck, in der die Rekursion sattfindet, erklären?

...zur Frage

Reguläre Sprache Theoretische Informatik?

Wahr oder Falsch: Sei Σ = {0, 1} und sei L ⊆ Σ∗ regulär. Sei L′ die Sprache, die man aus L erhält, indem man in jedem Wort aus L jedes zweite Vorkommen von 0 durch 10, und jedes dritte Vorkommen von 1 durch 01 ersetzt. Dann ist L′ regulär. Begründen Sie Ihre Antwort.

...zur Frage

Regulärer Ausdruck zu NFA/NEA?

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.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen