Akzeptierte und Formale Sprache?
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.
1 Antwort
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.
Eben das. Eine formale Sprache ist einfach irgendeine Menge von Wörtern. Die Sprache L(A) ist eine spezielle formale Sprache: Nämlich die, die vom Automaten A akzeptiert wird. Der Begriff "akzeptierte Sprache" existiert somit nicht unabhängig von einem Automaten - im Gegensatz zum Begriff "formale Sprache".
Jede akzeptierte Sprache ist auch eine formale Sprache. Aber umgekehrt muss das nicht so sein: Es gibt ja möglicherweise eine formale Sprache, die von keinem Automaten akzeptiert wird.
Es gibt nicht "die" formale Sprache oder "die" akzeptierte Sprache. Es gibt mehrere formale Sprachen und mehrere akzeptierte Sprachen.
Ob ein Wort Element einer Sprache ist, hängt eben von der Sprache ab. Z.B. ist das Wort 10110 ein Element der formalen Sprache {10110}, nicht aber ein Wort der formalen Sprache {0,1,01}.
Jedes Wort ist Element irgendeiner formalen Sprache, denn für ein Wort w kann ich ja einfach die formale Sprache {w} finden.
Tatsächlich ist auch jedes Wort Element irgendeiner akzeptierten Sprache, denn es gibt einen Automaten, der die Sprache {w} akzeptiert.
Also ist eine Eingabe, welche nur aus Elementen des Alphabets besteht, aber nicht auf einer Terminalen endet, ein Wort, welches in die formale, aber nicht akzeptierte Sprache passt?
Alles, was du über dieses Eingabewort weißt, ist dass es nicht in der von diesem Automaten akzeptierten Sprache liegt.
Also ist eine Eingabe, welche nur aus Elementen des Alphabets besteht, aber nicht auf einer Terminalen endet, ein Wort, welches in die formale, aber nicht akzeptierte Sprache passt?
Danke dir