computation-theory

3Hitze

2Antwort

Algorithmus für eine kontextfreie Grammatik

Ich versuche, einen Algorithmus zu entwerfen, der eine CFG G und ein Terminal-Symbol a als Eingabe nimmt und yes ausgibt, wenn S (die Startregel von G) eine zu startende Sentential-Form generieren kan

0Hitze

1Antwort

{<M> | M TM, die 3 Wörter akzeptieren} (| L (M) | = 3)

ich mit diesem Problem bin stecken {<M> | M ist ein TM, die 3 Wörter} Ich weiß übernimmt, wie |L(M)|>3 oder |L(M)|<3 zu lösen, aber wenn es um |L(M)|=3 kommt, weiß ich nicht, wie es weitergeht!

0Hitze

2Antwort

Wird L = {a * b *} als reguläre Sprache klassifiziert?

Wird L = {a * b *} als reguläre Sprache klassifiziert? Ich bin verwirrt, weil ich weiß, dass L = {a^n b^n} nicht regelmäßig ist. Welchen Unterschied macht der Kleene Stern?

0Hitze

2Antwort

Kann die Primzahlfunktion und das Produkt von aufeinanderfolgenden Primzahlen in Polynomialzeit berechnet werden?

In beiden Algorithmen Ich habe mit gearbeitet, verwende ich die zwei Funktionen: pi (n): = Anzahl der Primzahlen < = n und R (n): = r, wo prod (p_i, i = 1, r) = n < aber n < prod (p_i, i = 1, r + 1),

0Hitze

2Antwort

Grundlagen der CFG verstehen

Haben Sie gerade das Kapitel über CFL in Sipsers Buch begonnen und verstehen bereits die Grundlagen nicht. Dies seien die Grammatik einer Sprache sein: S -> A0A A -> 00A | 11A | 10A | 01A | e ich d

-1Hitze

1Antwort

DFA für erwartete Münzwürfe

Ich versuche dieses Problem zu konstruieren: Eine faire Münze wird geworfen, bis zwei Köpfe in einer Reihe erscheinen. Was ist die erwartete Anzahl von Münzwürfen? Entwerfen eines DFA für die Sprache

0Hitze

1Antwort

Konsequenzen des Rekursionssatzes

Ich hatte heute eine Prüfung über Computational Theory und eine Frage kam "Zustand zwei Folgen des Rekusionssatzes". Aus Neugier, was wäre die richtige Antwort darauf. Ich schrieb, dass es die Produkt

3Hitze

2Antwort

Gibt es rekursiv aufzählbare Probleme, die nicht RE-hart sind?

Die Berechenbarkeit Klasse, die ich nehme, erklärt mehrere Sprachen, die in RE sind - REC (rekursiv aufzählbar aber nicht rekursiv, das heißt auflösbar durch eine Turing-Maschine Nicht-Halten). Es zei

2Hitze

3Antwort

Wie können wir wissen, dass NP-vollständige Probleme am schwierigsten in NP sind?

Ich bekomme, dass, wenn Sie eine polynomische Zeitreduktion von "jedem" Problem machen können, dann beweist es, dass das Problem mindestens so schwer wie jedes Problem in NP ist. Außer, woher wissen w

0Hitze

2Antwort

Chomsky Normaler Formularkonvertierungsalgorithmus

Warum fügen wir einen neuen Startzustand S0 -> S hinzu, wenn wir eine Grammatik in Chomsky Normalform umwandeln wollen? Was läuft schief, wenn wir das nicht tun? Zuerst dachte ich, es ist wegen der Ep