mibeon
/ Compilerbau & Formale Sprachen

Regulärer Ausdruck Zeichenanzahl

Anzahl der über einem Alphabet möglichen Zeichenketten fester Länge: Möglichkeiten = Alphabet^Länge.

Regulärer Ausdruck Zeichenanzahl
01 · Eingabe

Regulärer Ausdruck Zeichenanzahl berechnen

Anzahl der über einem Alphabet möglichen Zeichenketten fester Länge: Möglichkeiten = Alphabet^Länge.

Lösen für
Möglichkeiten = Alphabet^Länge

Worum geht es?

Eine reguläre Sprache über einem Alphabet Σ enthält endlich viele Wörter fester Länge. Bei einer Stringlänge L und Alphabetgröße |Σ| gibt es genau |Σ|^L verschiedene Zeichenketten — die naive obere Schranke für jeden regulären Ausdruck, der Wörter dieser Länge beschreibt.

Diese Abzählung erscheint im Pumping-Lemma, in Brute-Force-Suchräumen (Passwörter, MAC-Adressen) und in der Worst-Case-Analyse von Akzeptanzläufen.

Die Formel

Formel Mächtigkeit über Σ^L 
Möglichkeiten = Alphabet^Länge

Umstellung:
    Länge = log(Möglichkeiten) / log(Alphabet)

Die Variablen

SymbolBedeutungEinheitErklärung
AlphabetAlphabetgröße—Anzahl Symbole im Alphabet |Σ|.
LängeStringlänge—Länge der zu zählenden Zeichenketten.
MöglichkeitenWörter—Anzahl unterscheidbarer Wörter über Σ^L.

Minimal-Beispiel

Binärwörter (|Σ| = 2) der Länge 8:

Rechnung Binärwörter 
Möglichkeiten = 2^8
              = 256

Praxis-Beispiele

Beispiel 1 — Hex-Token im Lexer

Ein Token akzeptiert genau 6 Hex-Ziffern (Σ = {0…9, a…f}, |Σ| = 16):

Rechnung Hex-Token 
Möglichkeiten = 16^6
              = 16 777 216

Beispiel 2 — Mindestlänge für 1 Mio. Bezeichner

Mit |Σ| = 26 Kleinbuchstaben: ab welcher Länge entstehen mindestens 10⁶ Wörter?

Rechnung Mindestlänge 
Länge = log(10⁶) / log(26)
      = 6 / 1,415
      ≈ 4,24

→ ab Länge 5 (26^5 = 11 881 376)

Beispiel 3 — DNA-Strings

Σ = {A, C, G, T} (|Σ| = 4), L = 20:

Rechnung DNA-Strings 
Möglichkeiten = 4^20
              = 1 099 511 627 776 ≈ 1,1 · 10¹²