Was ist in der Informatik NICHT eine formale Sprache?

Question

auf der Wikipedia-https://www.wikiwand.com/en/Formal_language, fand ich die Definition einer formalen Sprache:

In Mathematik, Informatik und Linguistik, eine formale Sprache ist ein Satz von Zeichenketten, die durch Regeln eingeschränkt werden kann, dass sind spezifisch für sie.

Das sieht ziemlich abstrakt für mich. Und ich kann mir keine Sprache vorstellen, die nicht zu dieser Definition passt. Hat jemand Ideen darüber, was eine informelle Sprache aussieht und wie es nicht die Definition passt?

Answer 1

Lassen Sie mich zuerst auf Ihre Frage kommen. Ein gutes Nicht-Beispiel für eine formale Sprache sind die natürlichen Sprachen. Englisch und Slowenisch sind Beispiele. So sind Tagalog und Tarifit Berber. Unglücklicherweise scheinen Linguisten keine Definition der natürlichen Sprache zu haben, über die sich alle einig wären.

Noam Chomsky versuchte in seiner 1956er Arbeit Three Models for the Description of Language bekanntermaßen, natürliche Sprache mit kontextfreien Gammaren zu modellieren. Er erfand (oder entdeckte, wenn Sie es vorzogen) sie in dieser Zeitung; obwohl er sie nicht so nannte; Während sie nicht nützlich waren, um die englische Sprache zu modellieren, revolutionierten sie die Informatik.

Formal ist eine formale Sprache nur eine Reihe von Strings über ein endliches Alphabet. Das ist es.

Beispiele hierfür sind alle gültigen C-Programme, alle gültigen HTML-Dateien, die alle gültigen XML-Dateien, alle Saiten der „balanced“ Klammern (zB (),()(), ((()))()(()), ...), den Satz (Codes unter einer Codierung) alle deterministischen Turing-Maschinen, die immer halt, die Menge aller einfachen Graphen, die mit k -Farben (tatsächlich ihre Codes unter irgendeiner Kodierung) gefärbt werden können, die Menge aller binären Zeichenketten, die enden und mit einer 1 beginnen, usw.

Einige sind leicht zu erkennen mit Regex (oder, gleichwertig, DFA); einige sind unter Verwendung von DFAs nicht zu erkennen, können jedoch mit PDA erkannt werden (oder können äquivalent mit einer kontextfreien Grammatik beschrieben werden); Andere geben eine solche Beschreibung nicht zu, können aber von einer Turing-Maschine erkannt werden; manche sind selbst mit einer Turing-Maschine (uncomputable) nicht zu erkennen.

Deshalb ist die Definition so nützlich. Viele Dinge, die uns in CS evey day begegnen, können in formale Sprachen übersetzt werden.

Für eine gute Einführung in das Thema, empfehle ich das hervorragende Buch Einführung in Automatentheorie, Sprachen und Berechnung von Hopcroft et al.

Answer 2

Englisch ist keine formale Sprache. Es ist nicht nur eine Reihe von Strings; es hat eine gesprochene Form und Evolution über die Zeit und Dialekte und alle möglichen anderen Dinge, die eine formale Sprache nicht hat. Eine formale Sprache konnte von einem Jahrzehnt zum nächsten nicht das Wort "E-Mail" erhalten.

Answer 3

Eine Sprache ist eine Menge von Sequenzen, die aus gegebenen Symbolen bestehen. Es kann entweder endlich oder unendlich sein (die Menge der englischen Sätze ist unendlich, obwohl es Sätze gibt, zB übermäßig lang, die selbst von einem Muttersprachler nicht verstanden werden können). Wenn es endlich ist, dann ist jede Beschreibung davon eine formale Definition.

Wenn die Sprache unendlich ist, sagen wir die Sprache arithmetischer Ausdrücke mit Zahlen, zwei binären Operatoren '+', '*' und Variablen, dann können Sie möglicherweise nicht alle Zeichenfolgen auflisten, die zur Sprache gehören, aber manchmal (siehe Blazs Kommentar unten) Sie können eine endliche Beschreibung als eine Reihe von Regeln geben.

E: = NUM ​​| v | E '+' E | E '*' E

(wobei NUM eine Ziffernfolge ist, v ist eine Variable) ist eine endliche Beschreibung einer unendlichen Menge. Das macht es förmlich.

Die verschiedenen anderen Aspekte wie Sprache oder die Entwicklung der Sprache sind verschiedene Probleme. Diese können auch formalisiert werden.