Theoretische Informatik

Question	Answer
Ist die Konkatenation von Wörtern assoziativ, oder kommutativ?	Nur assoziativ, Beispiel: ab ≠ ba , aber a o (b o c) = (a o b) o c, jedoch: aλ = λa
Wird jede reguläre Sprache von einem endlichen Automaten erkannt?	Ja, da jede Sprache sich als endlichen Automaten darstellen lässt.
Wird jede reguläre Sprache von einem DEA erkannt?	Ja, weil man mithilfe des Potenzautomaten aus jeden NEA einen DEA erzegen kann.
Wird jede reguläre Sprache in linearer Zeit erkannt?	Ja, siehe Zustandsüberführung
Ist jede von einem endlichen Automaten erkannte Sprache regulär?	Ja, weil auch jede reguläre Sprache als endlicher Automat dargestellt werden kann.
Ist jede von einem endlichen Automaten erkannte Sprache kontextfrei?	Ja, da jede reguläre Sprache auch kontextfrei ist.
Ist die Sprache {w$trans(w) \| w ∈ {a,b}*} regulär?	Nein, da wir einen Kellerautomaten brauchen, um uns Symbole zu merken. Das heißt, dass dies eine kontextfreie Grammatik ist.
Ist die Sprache {a^n b^n \| n ∈ N } regulär?	Nein, diese Sprache ist kontextfrei, weil wir uns wieder Symbole merken müssen.
Ist die Sprache {a^n b^n c^n \| n ∈ N } kontextfrei?	Nein, aber kontextsensitiv, weil hierbei der Kontext wichtig ist.

Resource summary

	Created by Jan-Niclas “JD” about 9 years ago