Spleißen Regel

Michael Rascher Kann 13, 2016 S 6 0
FONT SIZE:
fontsize_dec
fontsize_inc

In Mathematik und Informatik, ist ein Spleißen der Regel eine Transformation auf formale Sprachen, die die Wirkung von Gen-Splicing in der Molekularbiologie formalisiert. Ein Spleißen Sprache ist eine durch iterierte Anwendung einer Regel Spleißen erzeugt die Sprache: Spleißen Sprachen bilden eine echte Teilmenge der regulären Sprachen.

Definition

Sei A ein Alphabet und L eine Sprache, das heißt, eine Untergruppe der freien Monoid A. Ein Spleißen der Regel ist ein Vierfach-r = der Elemente von A, und die Aktion der Regel r auf L sein soll, um die Sprache zu produzieren

Ist R ein Satz von Regeln, so ist R die Vereinigung der durch die Regeln des R. hergestellt Sprachen Wir sagen, dass R respektiert L, wenn R eine Teilmenge von L. Die R-Schließung von L ist die Vereinigung von L und allen iteriert von R auf L: klar wird es von R. respektiert A Spleißen Sprache ist die R-Schließung einer endlichen Sprache.

Ein Regelsatz R ist reflexiv, wenn in R bedeutet, dass und in R. A Spleißen Sprache ist reflexiv, wenn er durch eine reflexive Regelsatz definiert ist.

Beispiele

  • Sei A = {a, b, c}. Die auf die endliche Menge {CABB, cabab, cabaab} angewendet Regel generiert die reguläre Sprache cabab.

Immobilien

  • Alle Spleißen Sprachen sind regelmäßig.
  • Nicht alle regulären Sprachen sind Spleißen. Ein Beispiel ist mehr als {a, b}.
  • Wenn L eine reguläre Sprache über dem Alphabet A und z ist ein Buchstabe nicht in A, dann die Sprache {zw: w in L} ist ein Spleißen Sprache.
  • Es gibt einen Algorithmus, um zu bestimmen, ob eine gegebene reguläre Sprache ist eine reflexive Spleißen Sprache.
  • Der Satz von Splicing-Regeln, die eine reguläre Sprache respektieren kann von der syntaktische Monoid der Sprache bestimmt werden.
  Like 0   Dislike 0
Vorherige Artikel William Stevens Robinson
Nächster Artikel Sigebert von Gembloux
Bemerkungen (0)
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha