Warum ist es nicht einfach, die Anzahl der Wörter in einer regulären Sprache zu zählen?

8

Bei einem DFA A bezeichne L (A) die Anzahl der Wörter, die A akzeptiert. Ich denke, es ist einfach, L (A) zu berechnen: Übersetzen Sie die Codierung von A in einen regulären Ausdruck. Wenn der Kleene-Stern irgendwo im Ausdruck erscheint, ist die Sprache unendlich. Sonst: Gehen Sie alle Wortkombinationen durch, die mit dem Ausdruck möglich sind (wenn der Ausdruck einen + -Operator enthält, multiplizieren Sie die Anzahl der zulässigen Wörter mit der Anzahl der durch das + verbundenen Zeichenfolgen).

Ist das falsch? Danke im Voraus

regular-languages automata regular-expressions user67573
quelle

3

ε^{*}

$\varepsilon^*$ ist keine unendliche Sprache.

David Richerby

cstheory.stackexchange.com/q/8200/5038

DW

12

Ja, das ist falsch, wegen der Mehrdeutigkeit.

Betrachten Sie die folgende Sprache: $(a + aa) + a(a + \epsilon)$ .

Mit Ihrer Methode sehen wir 4 Wörter, . Aber wir haben Duplikate! Es gibt mehrere Möglichkeiten, dasselbe Wort innerhalb des angegebenen regulären Ausdrucks zu bilden. $a, aa, aa, a$

Eine bessere Methode ist die Verwendung der dynamischen Programmierung auf einem minimalen DFA für Ihre Sprache ohne "tote" Zustände. Wenn der minimale DFA zyklisch ist, ist die Sprache unendlich, sodass wir davon ausgehen können, dass es keine Zyklen gibt. Die Verwendung eines DFA ist der Schlüssel, da der Determinismus bedeutet, dass für jedes Wort genau ein Pfad durch den DFA vorhanden ist.

Sie erstellen eine Wiederholung für die Anzahl der Wörter, die in einem bestimmten Zustand enden:

1 Wort endet im Startzustand: $\epsilon$
Für jeden Zustand ist die Anzahl der Wörter, die dort enden, die Summe der Anzahl der Wörter, die an jedem Zustand mit einem Übergang in enden . $q$ $q$

Die Gesamtzahl der Wörter ist dann die Summe der Anzahl der Wörter, die an jedem Endzustand enden.

jmite
quelle

2

Es ist zu beachten, dass diese Wiederholungen immer durch Computeralgebra gelöst werden können, z. B. für die Erzeugungsfunktionen. Ja, normale Sprache ist eigentlich leicht zu zählen.

Raphael

9

Ergänzend zur Antwort von jmite ist es nicht allzu schwierig, die Anzahl der Wörter in einer regulären Sprache mit der Methode "Übertragungsmatrix" zu berechnen. Dies ist dasselbe wie die dynamische Programmierung von jmite, aber die Technik hat weitere Anwendungen wie die asymptotische Aufzählung.

Konstruieren Sie bei einem gegebenen DFA eine Matrix (wobei die Menge von Zuständen ist), in der die Anzahl der Buchstaben ist, die bewirken, dass sich der DFA von Zustand zu Zustand bewegt . Sei und die Indikatoren für den Anfangszustand bzw. für die akzeptierenden Zustände. Schließlich sei . $Q\times Q$ $M$ $Q$ $M(i,j)$ $j$ $i$ $1_{q_0}$ $1_F$ $n = |Q|$

Die Anzahl der Wörter der Länge beträgt . Berechnen Sie für . Wenn ist, ist die vom DFA akzeptierte Sprache unendlich. Andernfalls beträgt die Anzahl der Wörter in der Sprache . $m$ $c_m := 1_F M^m 1_{q_0}$ $c_m$ $0 \leq m < 2n$ $c_n + \cdots + c_{2n-1} > 0$ $c_0 + \cdots + c_{n-1}$

(Bei der Berechnung der Potenzen von muss auf die Größe der Einträge geachtet werden, die in exponentiell ist . Da ihre Größe nur polynomisch ist, wird der resultierende Algorithmus in Polynomzeit ausgeführt.) $M$ $m$

Yuval Filmus
quelle

2

Ich liebe diesen Ansatz. Ich habe auch festgestellt, dass die Berechnung der Eigenwerte von

tatsächlich den Wurzeln des Nenners im Ansatz der Erzeugungsfunktion entspricht und dass diese Eigenwerte, vielleicht nicht überraschend, für die DFA-Minimierung unveränderlich sind. Ich habe jedoch absolut keine Ahnung, wie ich das richtig interpretieren soll.

M

$M$

Lee

1

Dies ist nicht so überraschend, da die Erzeugungsfunktion

, die vereinfacht sich zu

. Sie können ein noch expliziteres Ergebnis erzielen, indem Sie diese Berechnung mit der Jordan-Form von

wiederholen , die die Eigenwerte enthält.

P (z) = \sum_{n = 0}^{\infty} 1_{F} M^{n} 1_{q_{0}} z^{n}

$P(z) = \sum_{n=0}^\infty 1_F M^n 1_{q_0} z^n$

P (z) = 1_{F} (I - z M)^{- 1} 1_{q_{0}}

$P(z) = 1_F (I-zM)^{-1} 1_{q_0}$

M

$M$

Yuval Filmus

7

Tatsächlich können Sie immer noch Zählformeln für eindeutige reguläre Ausdrücke mit Kleene-Sternen ableiten .

In Anbetracht der induktiven Definition eines regulären Ausdrucks als:

e \in R. e : = x \in Σ ∣ e_{0} e_{1} ∣ e_{0} + e_{1} ∣ e^{*}

$\begin{equation*} e \in \mathrm{Re} := x \in \Sigma \mid e_0 ~ e_1 \mid e_0 + e_1 \mid e^* \end{equation*}$

Betrachten Sie die folgende Übersetzung ,einen regulären Ausdruck übernimmt und sie in eine komplexwertige rationale Funktion übersetzt: $[\![\cdot]\!] : \mathrm{Re} \to \mathbb{C}(z)$

\begin{aligned} [[x \in Σ]]]] & = z \\ [[e_{0} e_{1}]]]] & = [[e_{0}]]]] \times [[e_{1}]]]] \\ [[e_{0} + e_{1}]]]] & = [[e_{0}]]]] + [[e_{1}]]]] \\ [[e^{*}]]]] & = \frac{1}{1 - - [[e]]]]} \end{aligned}

$\begin{align*} [\![x \in \Sigma]\!] &= z \\ [\![e_0 ~ e_1]\!] &= [\![e_0]\!] \times [\![e_1]\!]\\ [\![e_0 + e_1]\!] &= [\![e_0]\!] + [\![e_1]\!]\\ [\![e^*]\!] &= \frac{1}{1 - [\![e]\!]} \end{align*}$

Wir können zeigen, dass diese Übersetzung einen rationalen Ausdruck zurückgibt, indem wir eine strukturelle Induktion für und feststellen, dass alle auf der rechten Seite verwendeten Operationen die Rationalität bewahren. $e$

Angenommen, der reguläre Ausdruck , den wir eingeben, ist eindeutig, dann würden wir feststellen, dass die mit bezeichnete rationale Funktion $e$ ist tatsächlich die Erzeugungsfunktion für die Familie von Wörtern, die von der zugrunde liegenden Sprache akzeptiert werden, geordnet nach ihrer Länge. $[\![e]\!] \in \mathbb{C}(z)$ $e$

Betrachten Sie zum Beispiel die Sprache , die die Sprache der Läufe durch begrenzten Laufs definiert . Dieser reguläre Ausdruck ist eindeutig, sodass wir unseren Übersetzungstrick ausführen können: $(a^*b)^*$ $a$ $b$

\begin{aligned} [[(a^{*} b)^{*}]] & = \frac{1}{1 - [[a^{*} b]]} \\ = \frac{1}{1 - ([[a^{*}]] \times [[b]])} \\ = \frac{1}{1 - (\frac{1}{1 - [[a]]} \times z)} \\ = \frac{1}{1 - \frac{z}{1 - z}} \\ = \frac{1}{2} + \frac{1}{2 - 4 z} \end{aligned}

$\begin{align*} [\![(a^*b)^*]\!] &= \frac{1}{1 - [\![a^*b]\!]} \\ &= \frac{1}{1 - ([\![a^*]\!] \times [\![b]\!])} \\ &= \frac{1}{1 - \left(\frac{1}{1 - [[a]]} \times z\right)} \\ &= \frac{1}{1 - \frac{z}{1 - z}} \\ &= \frac{1}{2} + \frac{1}{2 - 4 z} \end{align*}$

As it turns out, given the above generating function, its coefficient extraction will be

[z^{n}] [[(a^{*} b)^{*}]] = 2^{n - 1} + \frac{δ (n)}{2}

$[z^n][\![(a^*b)^*]\!] = 2^{n - 1} + \frac{\delta\left(n\right)}{2}$ where

δ (n) = {\begin{cases} 1 & if n = 0 \\ 0 & otherwise \end{cases}

$\delta(n) = \begin{cases} 1 & \text{if } n = 0 \\ 0 & \text{otherwise} \end{cases}$

In fact, since our translation $[\![\cdot]\!]$ generates rational functions, we can use a partial fraction decomposition to create an enumeration formula for any unambiguous regular expression.

Suppose you have a irreducible rational function

r (z) + \frac{p (z)}{q (z)}

$r(z) + \frac{p(z)}{q(z)}$ where

r, p, q

$r, p, q$ are polynomials, then you can decompose this into

r (z) + \frac{C_{0}}{z - q_{0}^{*}} + \dots + \frac{C_{n}}{z - q_{n}^{*}}

$r(z) + \frac{C_0}{z - q^*_0} + \dots + \frac{C_n}{z - q^*_n}$ where

q_{k}^{*}

$q^*_k$ are the roots of

q (z)

$q(z)$ . There's a bit of technical corner-cases (like multiplicity of roots, etc), but it's relatively easy to do coefficient extraction on the expression above:

[z^{n}] \frac{C}{z - q^{*}} = C \times {q^{*}}^{- n}

$[z^n] \frac{C}{z - q^*} = C \times {q^*}^{-n}$

In fact, the partial fraction decomposition generalize to multivariate rational functions, so you can actually construct counting formulas for queries such as "How many words are there where there are $n$ as and $m$ bs?"

Unfortunately, the extent to which this method will be useful ends when you have an ambiguous expression.

Lee
quelle

Warum ist es nicht einfach, die Anzahl der Wörter in einer regulären Sprache zu zählen?

Antworten: