Σ+ ist eine kontextfreie und reguläre Sprache.
Wahr,
=> Erklärung fehlt noch
P ⊆ NP
P (= Klasse der Entscheidungsprobleme, die in polynomialer Zeit lösbar sind)
NP (= Klasse der Entscheidungsprobleme, die in polynomialer Zeit mit einem NEA lösbar sind)
P ⊆ NP bedeutet, dass alle Probleme die in P gelöst werden können auch in NP gelöst werden können.
ABER es gibt Probleme die in NP gelöst werden können, aber nicht in P.
Es gibt einen Minimalautomaten mit genau einem Zustand.
aber dieser Automat kann nur dazu verwendet werden, um das leere und das nicht-leere Wort zu erkennen.
Jede Mehrband-Turingmachine kann mit linearem Zeit-Overhead durch eine Einband-Maschine simuliert werden.
Falsch,
Eine Mehrband-Turingmaschine kann schneller und effizienter arbeiten, da sie mehrer Bänder hat und parallel arbeiten kann.
=> die Zeitkomplexität würde bei einer solchen Simulation exponentiell steigen.
∀x ∈ NP ∶ Sat ≤p x
Sat (= Klasse der sog. “Satisfiability”-Probleme, die bestimmen, ob es eine Lösung für eine gegebene Formel in der propositionalen Logik gibt.
Es gibt Probleme die in NP gelöst werden können, aber nicht in P, daher kann nicht garantiert werden, dass für alle x aus NP gilt Sat ≤p x
∀x ∈ NP ∶x≤p Sat
jedes Entscheidungsproblem der Klasse NP kann durch ein polynomiell lösbares Sat-Problem verkörpert werden.
Wichtig: Bedeutet nicht das alles Probleme in NP polynomiell lösbar sind oder dass alle Probleme in P sind.
Die Dyck-Sprache D1 ist kontextfrei.
=> Erklärung fehlt
Eine Gödelisierung c(M) ist surjektiv.
Gödelisierung c(M) ist ein Verfahren, bei dem man eine Formel c(M) erhält, die die Existenz einer Turing-Maschine M beschreibt.
surjektiv = jeder Wert des Zielbereiches mind. einmal durch den Wert des Ausgangbereichs abgedeckt wird.
Gödelisierung beschreibt jedoch nur Existenz und nicht alle möglichen Turing-Maschinen.
(injektiv)
Die charakteristische Funktion einer TM, die eine Sprache M entscheidet, ist berechenbar.
Funktion ist berechenbar, da eine Turing-Maschine in der Lage ist, ein Wort als Eingabe zu akzeptieren und eine Entscheidung darüber zu treffen, ob es Teil der Sprache M ist oder nicht.
Mit welchen Tupel ist ein NEA definiert
M = (Q,∑,δ,E,F)
Q = alle Zustände
∑ = Eingabealphabet
δ = Übergangrelation
E = Startzustand
F = alle akzeptierenden Zustände
Mit welchen Tupel ist ein DEA definiert
M = (Q,∑,δ,q0,F)
q0 = Startzustand
Was ist der 1 Schritt bei Pumping Lemma
Annahme: Lx sei Element der L3 (regulären Sprache) mit Pumping Konstante n
Was ist der 2 Schritt bei Pumping Lemma
Wortauswahl: kreativer Teil, das Wort muss nur:
|w| >= n sein
Was ist der 3 Schritt bei Pumping Lemma
w = xyz muss die 3 Pumping Lemma Bedingungen erfüllen
|xy| <= n
y >= 1
Für alle 1 Element auf N0: xy^iz muss Element der Sprach sein
Eine Turing-Maschine, die eine Sprache M akzeptiert, kann in eine Endlos-schleife geraten.
wenn die Turing-Maschine auf ein Wort der Sprache M trifft, das nicht die Endbedingungen erfüllt, die die Turing-Maschine verwendet, um zu bestimmen, ob sie ein Wort akzeptiert oder nicht.
{ε}\{1, 2, 3} ist eine reguläre Sprache?
ε ist Element der regulären Sprache
Ein Automat mit genau einem Zustand ist immer ein Minimalautomat?
es existiert kein Automat mit weniger als einem Zustand.
Es ist sicher bekannt das P ⊂ NP?
Ein Kellerautomat kann nicht in eine Endlosschleife geraten.
auch ein Kellerautomat kann in eine Endlosschleife geraten.
Für eine Gödelisierung c(M) gilt |c(M)| < ∞
Gödelisierung beschreibt jedoch nur Existenz und nicht alle möglichen Turing-Maschinen, deshalb ist auch die Anzahl der Gödelisierungen kleiner als unendlich.
Die regulären Ausdrücke (a*b) und (a*b)* sind äquivalent?
Ein endlicher Automat erkennt nur endliche Sprachen.
endlicher Automat erkennt reguläre Sprachen, die auch unendlich sein können.
Für eine reguläre Sprache L über dem Alphabet gilt L vereinigt mit Gegenteil von L = Alphabet+ verereinigt mit {Epselon}
Wahr
Ein Myhill und Nerode konstruierter Minimalautomat kann unendlich viele Zustände besitzen
Falsch
Ein nicht deterministischer Kellerautomat kann durch eine Turing-Maschine simuliert werden
Es gibt eine Sprache L mit L* = {Epsylon}
Es gibt einen regulären Ausdruck, der sich selbst erkennt.
Der CYK Algorithmus kann reguläre Sprachen entscheiden.
der CYK Algorithmus kann kontextfreie Sprachen entscheiden ( regulär in Kontext frei)
Linear beschränkte nicht deterministische Automaten können das Wortproblem für L1 entscheiden.
Das Halteproblem für DEAs ist unentscheidbar.
Wenn der Index der Nerode-Relation RL entdlich ist, ist die Sprache L immer endlich.
endlicher Index = reguläre Sprache, die auch unendlich sein kann.
Die Sprache L = {a^i b^i | i Element von N} ist regulär.
es ist eine kontextfreie Sprache (Dyck-Sprache).
Für ein endliches Alphabet ist Alphabet * kontextfrei.
kontextfreie Sprachen sind unter dem Kleene-Stern abgeschlossen.
Ein DEA kann mit endlicher Eingabe in eine Endlosschleife geraten
Für G=(V, Alphabet, P, S) aus L2 gilt |L(G)| = |P| wenn für alle (l->r) element von P : l = S und r Element von Alphabet+
rechts stehen nur Wörter, links steht nur S
Für jede formale Sprache L gilt L echte Teilmenge von Alphabet*.
es muss heißen L Teilmenge von Alphabet*
Für einen DEA M = (Q, Alphabet, Übergangsfuktion, q0, F) mit F = {} gilt L(m) = {}
der DEA terminiert nicht => leere Menge
Für einen DEA M = (Q, Alphabet, Übergangsfuktion, q0, F) mit F != {} gilt L(m) != {}
der Endzustand kann auch nicht erreichbar sein.
Die Regel A-> a A ist linkslinear.
rechtslinear.
Chomsky und Greibach Normalform einer Grammatik unterscheiden sich immer.
S->a
Endliche Automaten können unendliche Sprachen entscheiden.
reguläre Sprachen können unendlich sein.
Das Pumping-Lemma gibt notwendige Bedingungen für die Regularität einer Sprache.
Kellerautomaten können Phrasenstruktursprachen entscheiden
Kellerautomaten können genau kontextfreie Sprachen entscheiden.
Eine zeitbeschränkte Turing-Maschine ist immer platzbeschränkt.
Eine platzbeschränkte Turing-Maschine ist immer zeitbeschränkt.
Endlosschleifen sind auch auf beschränktem Platz möglich
Das Halteproblem kann auf nichtdeterministischen Automaten gelöst werden.
Für jeden regulären Ausdruck gibt es eine äquivalente reguläre Grammatik.
Die Sprache L = {w | w= a^i b^i c^i} ist kontextfrei.
Eine Sprache, für die das reguläre Pumping-Lemma gilt hat einen endlichen Index bzgl. der Nerode-Relation RL
endlicher Index bedeutet reguläre Sprache, das Pumping-Lemma kann aber auch für nicht-reguläre Sprachen gelten.
Für jeden NEA gilt |Q| +|Alphabet| < unendlich
Zustände und Alphabet müssen endlich sein
Für einen NEA gilt |Q| < unendlich
Jede beliebige Sprache kann durch eine Turingmaschine entschieden werden
Es gibt unentscheidbare Sprachen
Zu jeder Turing-Maschine gibt es ein äquivalentes C-Program
da C die While-Sprache enthält
Eine Gödelisierung muss bijektiv sein
Es gilt n = Kringel(log(n))
Es gilt log(n) = Kringel(n)
Für die Zeitkomplexität Tm einer Turing-Maschine M kann Tm(->x) > Tm(->y) für
|->x | <= |->y| gelten.
Epsylon ist eine reguläre Sprache.
{Epsylon} wäre eine reguläre Sprache
Jede Gödelisierung ist berechenbar.
Ek Kellerautomat kann reguläre Sprachen entscheiden
Ein NEA und ein dazu äquivalenter DEA besitzen die gleiche Zeitkomplexität für das Wortproblem.
Laufzeit ist n = Anzahl der Zustände
Alphabet* ist eine reguläre Sprache
Ein Kellerautomat kann in eine Endlosschleife geraten.
Für eine reguläre Sprache L über dem Alphabet gilt L vereinig Lc = Alphabet+
Die Dyck-Spache D1 ist regulär.
Probleme in NP sind mit linearem Aufwand auf einer nicht-deterministischen Turing-Maschine entscheidbar.
richtig wäre polynomialer Aufwand
Der CYK Algoritmus entscheidet jede kontextsensitive Grammatik.
nur kontextfreie Grammatik im CNF
Die Regel A -> A a ist in Greibach-Normalform
Zwei Kellerautomaten, die die gleiche Sprache erkennen haben immer gleich viel zustände
Tupel einer Grammatik G
G=({alle Übergänge},{Alphabet}, P, S)
S =Startzeichen
P= Übergangs Funktionen der Zeichen
Last changeda year ago