Was ist eine normale Sprache?

Ich versuche, das Konzept der Sprachebenen zu verstehen (regulär, kontextfrei, kontextsensitiv usw.).

Ich kann das leicht nachschlagen, aber alle Erklärungen, die ich finde, sind eine Menge Symbole und sprechen über Mengen . Ich habe zwei Fragen:

1. Können Sie in Worten beschreiben, was eine reguläre Sprache ist und wie sich die Sprachen unterscheiden?

2. Wo lernen die Leute dieses Zeug zu verstehen? So wie ich es verstehe, ist es formale Mathematik? Ich hatte ein paar Kurse an der Uni, die es benutzten, und kaum jemand verstand es, da die Tutoren einfach davon ausgegangen waren, dass wir es wussten. Wo kann ich es lernen und warum wird von den Leuten "erwartet", dass sie es in so vielen Quellen wissen? Es ist, als gäbe es eine Bildungslücke.

Hier ist ein Beispiel :

Jede Sprache, die zu diesem Satz gehört, ist eine reguläre Sprache über dem Alphabet.

Wie kann eine Sprache "über" irgendetwas sein?

Im Kontext der Informatik ist ein Wort die Verkettung von Symbolen . Die verwendeten Symbole werden als Alphabet bezeichnet . Zum Beispiel, einige Worte des Alphabets gebildet aus {0,1,2,3,4,5,6,7,8,9}wären 1, 2, 12, 543, 1000, und 002.

Eine Sprache ist dann eine Teilmenge aller möglichen Wörter. Beispielsweise möchten wir möglicherweise eine Sprache definieren, die alle Elite-MI6-Agenten erfasst. Diejenigen , die alle mit Doppel 0 beginnen, so Worte in der Sprache wären 007, 001, 005, und 0012, aber nicht 07oder 15. Der Einfachheit halber sagen wir, eine Sprache sei " über einem Alphabet" anstelle von "einer Teilmenge von Wörtern, die durch Verkettung von Symbolen in einem Alphabet gebildet werden".

In der Informatik wollen wir jetzt Sprachen klassifizieren. Wir nennen eine Sprache regulär, wenn mit einem Algorithmus / einer Maschine mit konstantem (endlichem) Speicher entschieden werden kann, ob ein Wort in der Sprache ist, indem alle Symbole im Wort nacheinander untersucht werden. Die Sprache, die nur aus dem Wort 42besteht, ist regulär, da Sie entscheiden können, ob ein Wort darin enthalten ist, ohne dass beliebig viel Speicher erforderlich ist. Sie überprüfen nur, ob das erste Symbol 4 ist, ob das zweite 2 ist und ob weitere Zahlen folgen.

Alle Sprachen mit einer endlichen Anzahl von Wörtern sind regulär, da wir (theoretisch) nur einen Kontrollflussbaum konstanter Größe iferstellen können (Sie können ihn als eine Reihe verschachtelter Anweisungen visualisieren, die eine Ziffer nach der anderen untersuchen). Zum Beispiel können wir mit dem folgenden Konstrukt testen, ob ein Wort in der Sprache "Primzahlen zwischen 10 und 99" vorliegt, wobei nur der Speicher benötigt wird, um zu codieren, in welcher Codezeile wir uns gerade befinden:

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

Beachten Sie, dass alle endlichen Sprachen regulär sind, aber nicht alle regulären Sprachen endlich sind. unsere Doppel 0 Sprache eine unendliche Anzahl von Worten enthält ( 007, 008, sondern auch 004242und 0012345), kann aber mit konstantem Speicher getestet werden: Zur Prüfung , ob ein Wort in ihr gehört, überprüft , ob das erste Symbol ist 0, und ob das zweite Symbol ist 0. Wenn dies der Fall ist, akzeptieren Sie es. Wenn das Wort kürzer als drei ist oder nicht mit beginnt 00, handelt es sich nicht um einen MI6-Codenamen.

Formal wird das Konstrukt einer endlichen Zustandsmaschine oder einer regulären Grammatik verwendet, um zu beweisen, dass eine Sprache regulär ist. Diese ähneln den ifobigen Anweisungen, lassen jedoch beliebig lange Wörter zu. Wenn es eine endliche Zustandsmaschine gibt, gibt es auch eine reguläre Grammatik und umgekehrt, so dass es ausreicht, beides zu zeigen. Die endliche Zustandsmaschine für unsere Doppel-0-Sprache lautet beispielsweise:

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

Die äquivalente reguläre Grammatik lautet:

start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...

Der äquivalente reguläre Ausdruck lautet:

00[0-9]*

Einige Sprachen sind nicht regelmäßig. Zum Beispiel ist die Sprache einer beliebigen Anzahl von 1, gefolgt von der gleichen Anzahl von 2(oft als 1 ⁿ 2 ^{n geschrieben} , für ein beliebiges n ) nicht regulär - Sie benötigen mehr als eine konstante Speichermenge (= eine konstante Anzahl von Zuständen) ) um die Anzahl von 1s zu speichern , um zu entscheiden, ob ein Wort in der Sprache ist oder nicht.

Dies sollte normalerweise im theoretischen Informatikkurs erklärt werden. Glücklicherweise erklärt Wikipedia sowohl formale als auch reguläre Sprachen recht gut.

Hier sind einige der entsprechenden Definitionen aus Wikipedia :

[...] Eine reguläre Sprache ist eine formale Sprache (dh eine möglicherweise unendliche Menge endlicher Folgen von Symbolen aus einem endlichen Alphabet), die die folgenden äquivalenten Eigenschaften erfüllt:

• es kann von einer deterministischen endlichen Zustandsmaschine akzeptiert werden.
• es kann von einer nichtdeterministischen endlichen Zustandsmaschine akzeptiert werden

• es kann durch einen formalen regulären Ausdruck beschrieben werden.

  Beachten Sie, dass die mit vielen Programmiersprachen bereitgestellten Funktionen für "reguläre Ausdrücke" durch Funktionen ergänzt werden, mit denen sie Sprachen erkennen können, die nicht regulär sind und daher nicht unbedingt formalen regulären Ausdrücken entsprechen.

Das erste, was zu beachten ist, ist, dass eine reguläre Sprache eine formale Sprache ist , mit einigen Einschränkungen. Eine formale Sprache ist im Wesentlichen eine (möglicherweise unendliche) Sammlung von Zeichenfolgen. Beispielsweise ist die formale Sprache Java die Sammlung aller möglichen Java-Dateien, die eine Teilmenge der Sammlung aller möglichen Textdateien ist.

Eines der wichtigsten Merkmale ist, dass eine reguläre Sprache im Gegensatz zu den kontextfreien Sprachen keine willkürliche Verschachtelung / Rekursion unterstützt, Sie jedoch willkürliche Wiederholungen haben.

Einer Sprache liegt immer ein Alphabet zugrunde, das aus den zulässigen Symbolen besteht. Zum Beispiel wäre das Alphabet einer Programmiersprache normalerweise entweder ASCII oder Unicode, aber in der formalen Sprachtheorie ist es auch in Ordnung, über Sprachen über andere Alphabete zu sprechen, zum Beispiel über das binäre Alphabet, in dem die einzigen zulässigen Zeichen 0und sind 1.

An meiner Universität wurde uns in der Compiler-Klasse eine formale Sprachtheorie beigebracht, aber dies ist wahrscheinlich zwischen verschiedenen Schulen unterschiedlich.