Heim

Diskussion:Formale Sprache

Diese Diskussionsseite wurde aufgeräumt.
Abschnitte zu abgeschlossenen Themen, zu älteren Artikelversionen und/oder Absätze, die von ihrer Art her keine Diskussionsbeiträge sind, wurden entfernt, um die Übersichtlichkeit wieder herzustellen. Dies betrifft nur Abschnitte bis zum 3. November 2006. Sie sind hier auffindbar: [1].


Inhaltsverzeichnis

Vorschlag Ausarbeitung des Artikels zur Klärung der Redundanz

Eine Überabeitung des Kompletten Artikels im Hinblick auf die Theoretische Informatik wäre eine Möglichkeit, die Abgrenzung zu Formalen Systemen/ Formalen Systemen(Logik) in den Griff zu bekommen und würde gleichzeitig den "Wert" des Artikels nach meiner Meinung steigern.

Als Gliederung des Artikels wäre folgendes möglich:

* Einordnung Formale Sprachen als Themengebiet der Theoretische Informatik(analog zu Komplexitätstheorie)
* Definition Formale Sprache
* Beispiele 
* Problemstellungen
   - Generative Mächtigkeit von Formalen Sprachen
   - Beschreibungskomplexität von Sprachen bei verschiedenen Grammatiken
   - Beschreibungskomplexität von Sprachen im Hinblick auf Determinismus/Nichtdeterminismus
* Operationen auf Formalen Sprachen
* Wichtige Formale Sprachklassen
* Literaturangaben

Sollte der Vorschlag zur Überarbeitung anklang finden, kann ich einen Teil der Ausarbeitung übernehmen. --Peter Biela 19:37, 26. Apr. 2007 (CEST)

Ich unterstütze deinen Vorschlag, Peter, kann aber selber nur wenig dazu beitragen, da ich mich bisher nur mit den Grundlagen der theoretischen Informatik auseinandergesetzt habe. --El Torres 22:13, 26. Apr. 2007 (CEST)

Natürliche und formale Sprachen

Ich habe den folgenden Text erstetzt:

"Natürliche Sprachen sind keine formalen Sprachen. Jedoch befassen sich wissenschaftliche Fachrichtungen wie die Computerlinguistik damit, natürliche Sprachen als formale Sprachen darzustellen (beispielsweise um maschinelle Übersetzung zu ermöglichen). Wenn dies gelingt, dann folgt daraus, dass die menschlichen Sprachen eine Teilmenge der formalen Sprachen sind."

So wie die formalen Sprachen hier definiert wurden sind sie Teilmenge der formalen Sprachen, da menschliche Sprachen auf endlichen Alphabeten basieren und somit eine Teilmenge der Menge über allen Wörtern des Alphabets sind. Benutzer:FlorianMehm, 15:25, 19. Jul 2004 (CEST)

Hallo Florian,
Vielen Dank für Deine Korrektur, sie ist vollkommen richtig, so wie es jetzt ist, stand es auch mal im Artikel, hat nur anscheinend mal wieder jemand geändert.
mfg --zeno 21:58, 19. Jul 2004 (CEST)
Eine formale Sprache ist formal. Was das heißt, weiß ich nicht genau, aber mir fallen zwei mögliche Gründe ein:
1. Eine formale Sprache ist ein mathematisches Gebilde.
2. Eine formale Sprache berücksichtigt nur den syntaktischen Aspekt.
Beides scheint mir auf eine natürliche Sprache nicht zuzutreffen. Eine natürliche Sprache ist also m.E. keine formale Sprache. Man könnte aber vielleicht sagen, dass die Syntax einer natürlichen Sprache durch eine formale Sprache modelliert werden kann.
-- Blauwal 16:01, 3. Nov. 2006 (CET)

Grauenvoll

Was für ein schrecklich unverständlich mathematisches Zeug in diesem Artikel steht ist mir ein Rätsel. Ich kann dem hier gelesenen keinerlei konkrete und "auf den Punkt gebrachte" Definition entnehmen sondern nur Gebrabbel aus den Tiefen der Mathematik. Ich dachte, eine Ecyclopädie ist kein Speziallehrbuch, sondern ein Überblicks- und Einführungswerk.

Ich bin enttäuscht über diejenigen, die sich sich unter den Wissenden wägen, jedoch nicht mit Unwissenden komunizieren wollen oder können

Björn

Ich sehe das anders. Formale Sprachen sind nun mal ein formales Thema. Da ist eine exakte Ausdrucksweise essentiell und daher ist es sehr empfehlenswert, das Ganze mathematisch aufzuziehen. Gerade durch die mathematische Ausdrucksweise kann man die Sache „auf den Punkt bringen“ und der Versuch, eine exakte mathematische Darstellung zu vermeiden, würde möglicherweise in „philosophischem Gebrabbel“ enden. Außerdem ist eine formale Sprache nun einmal ein mathematisches Gebilde, weswegen eine Abhandlung über das Thema auf mathematische Begriffe Bezug nehmen muss. Wenn also eine formale Sprache eine Menge (im mathematischen Sinn) ist, dann muss die Definition das erwähnen.
Eine „normale“ Enzyklopädie setzt i.A. kein großes Mathematikwissen voraus, aber in einer solchen wirst du vielleicht auch nichts von formalen Sprachen lesen. Eine Informatik-Enzyklopädie würde vielleicht einen Artikel über formale Sprachen enthalten, würde aber vermutlich auch mehr Hintergrundwissen beim Leser voraus setzen, weshalb du dort auch auf mathematische Ausdrucksweise stoßen könntest.
Die Aussagen des Artikels sind nicht per se „schrecklich unverständlich“, sondern für jemanden mit dem entsprechenden mathematischen Grundwissen durchaus verständlich. Vielleicht hatten die Schreiber des Artikels ja einen gewissen Standesdünkel, vielleicht wollten sie aber auch nur einen Artikel in einer angemessenen und für sie ganz selbstverständlichen Sprache schreiben. Ich kann mir gut vorstellen, dass die Schreiber nicht einfach Unwissende ausschließen wollten, sondern dass sich die Unwissenden vielleicht einfach ein bisschen Grundlagenwissen aneignen sollten, bevor sie einen solchen Artikel lesen.
-- Blauwal 15:51, 3. Nov. 2006 (CET)

Definition

Eine formale Sprache ist nicht unbedingt durch eine formale Grammatik darstellbar. Formale Grammatiken können nur Typ-0-Sprachen darstellen, während eine formale Sprache eine beliebige Wortmenge sein darf. Für ein konkretes Alphabet Σ gibt es nur abzählbar viele Typ-0-Sprachen (weil es nur abzählbar viele Grammatiken gibt), jedoch überabzählbar viele formale Sprachen (weil Σ * unendlich und die Potenzmenge einer unendlichen Menge überabzählbar ist).

Aus diesem Grund haben wir die Definition des Begriffs der formalen Sprache am Anfang des Artikels verändert.

-- 141.43.203.162 19:02, 1. Nov. 2006 (CET)

Meiner Meinung nach ist das Vorstehende entweder Unsinn, oder wir sind über die Bedeutung von "Formale Grammatik" uneinig. Ich habe bei "Formale Grammatik" einen Satz (eine Menge) von Produktionen im Kopf, die die Herleitung von terminalen "Wörten" der Sprache aus eine Menge von Startsymbolen erlauben, und habe in Erinnerung, daß alle formalen Sprachen aller Typen und Klassen so zu beschreiben seien. Mit andern Worten, eine der allg. Automatentheorie nahestehende Beschreibung, daher ist auch der Isomorphismus zu den Touringmaschinen möglich. Ich bitte um Korrektur und Quellenhinweise, wenn ich falsch liegen sollte. -- Purodha Blissenbach 20:21, 29. Nov. 2007 (CET)
Irgendwie hat sich der Fehler mit der Grammatik wieder in die Einleitung eingeschlichen. Die IP 141.43.. hat ja schon erklärt was daran falsch ist: Mit Grammatiken können nur Typ-0 Sprachen - also die rekursiv aufzählbaren Sprachen - beschrieben werden (Beweise dazu findet man in allen gängigen Lehrbüchern, z.B. im Schöning oder Wegeners Theoretische Informatik). Formale Sprachen können aber beliebige Wortmengen über einem Alphabet sein. --89.247.99.223 12:44, 29. Dez. 2007 (CET)

Verwendung des Begriffs "Formale Sprache" in der Wikipedia

Als ich neulich in der 2. Auflage des Buchs Theoretische Informatik: eine umfassende Einführung von Katrin Erk und Lutz Priese (ISBN 3-540-42624-8) mich zum Thema Grammatiken informiert habe, fand ich eine andere Definition des Begriffs formale Sprache als die, die im Artikel Formale Sprache, aber auch in anderen Artikeln in der Wikipedia verwendet wird. Hier heißt es nämlich auf der Seite 54, dass formale Sprachen „diejenigen Sprachen [sind], die sich über eine Grammatik beschreiben lassen“, wobei in diesem Buch Sprache als eine Teilmenge der Kleeneschen Hülle eines gegebenen Alphabets definiert wurde. Man erkennt, dass die Begriffe Sprache, wie er im genannten Buch definiert ist, und formale Sprache, wie er in vielen Artikeln der Wikipedia verwendet wird, synonym sind. Wie aber dem obigen Diskussionsbeitrag zur Definition formaler Sprachen zu entnehmen ist, bilden die durch Grammatiken beschreibbare Sprachen, die Typ-0 Sprachen, nur eine echte Teilmenge der Sprachen, die aus einem gegebenen Alphabet gebildet werden können. Demnach stellt sich die Frage, ob die Begriffe Sprache und formale Sprache Synonyme sind, oder ob formale Sprachen nur eine Untermenge der Sprachen im allgemeinen beschreiben. Hier eine Liste von Quellen, in denen beide Begriffe synonym verwendet werden bzw. die formale Sprache als Teilmenge der Kleeneschen Hülle definiert wurde:

Quellen, in denen entweder zwischen beiden Begriffen unterschieden oder nur der Begriff Sprache verwendet wird:

Welche Definitionen der Begriffe Sprache und formale Sprache habt ihr kennen gelernt und wie sollen diese beiden Begriffe in der Wikipedia verwendet werden? Grüße --El Torres 21:18, 12. Apr. 2008 (CEST)

Die Begriffe "formale Sprache" und "Sprache" werden in der Theoretischen Informatik idR synonym verwendet. Für die Wikipedia zu definieren, dass mit "formaler Sprache" nur die durch eine Grammatik erzeugbaren Sprachen gemeint sein sollen, halte ich nicht für sinnvoll, denn die Wikipedia soll Begriffsbildungen nicht herbeiführen, sondern nur den aktuell üblichen Sprachgebrauch widergeben.
Die oben vorgetragene Argumentation, dass die Menge der durch Grammatiken erzeugbaren Sprachen eine Teilmenge aller Sprachen ist, ist völlig korrekt. Man kann sich das leicht vor Augen führen, indem man die Fragestellung aus der Sicht der Automatentheorie betrachtet. Zu jeder von einer Typ-0-Grammatik erzeugten Sprache lässt sich eine Turingmaschine konstruieren, welche diese Sprache entscheiden kann. Ließen sich alle Sprachen durch Grammatiken erzeugen, so würde dies schlichtweg bedeuten, dass beliebige Sprachen entscheidbar wären. Wie jeder Informatiker weiß, ist dies leider nicht der Fall, andernfalls gäbe es das Halteproblem nicht, und die Prädikatenlogik wäre entscheidbar. In der gegenwärtigen Fassung ist der Artikel daher nicht korrekt. -- Mkleine 19:31, 8. Jun. 2008 (CEST)