8
$\begingroup$

Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the expression - the language is infinite. Else: Go through and count all the combinations of words that are possible to make using the expression (basically if there is a + operator on the expression, multiply the amount of legal words by the amount of strings connected by the +..)

Is this wrong? Thanks in advance

$\endgroup$
12
$\begingroup$

Yep, this is wrong, because of ambiguity.

Consider the following language: $(a + aa) + a(a + \epsilon)$.

With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.

A better method is to use dynamic programming on an minimal DFA for your language, with no "dead" states. If the minimal DFA is cyclic, the language is infinte, so we can assume there's no cycles. Using a DFA is key, because the determinism means there's exactly one path through the DFA for each word.

What you do is build up a recurrence for the number of words that end at a given state:

  • 1 words ends at the start state: $\epsilon$
  • For each state $q$, the number of words ending there is the sum of the number of words ending at each state with a transition into $q$.

The total number of words is then the sum of the number of words ending at each final state.

$\endgroup$
  • 2
    $\begingroup$ It bears noting that these recurrences can always be solved by computer algebra, e.g. for the generating functions. So yea, regular language are actually easy to count. $\endgroup$ – Raphael Mar 10 '17 at 19:54
9
$\begingroup$

Complementing jmite's answer, it is not too difficult to compute the number of words in a regular language, using the "transfer matrix" method. This is the same as jmite's dynamic programming, but the technique has further applications such as asymptotic enumeration.

Given a DFA, construct a $Q\times Q$ matrix $M$ (where $Q$ is the set of states) in which $M(i,j)$ is the number of letters that cause the DFA to move from state $j$ to state $i$. Let $1_{q_0}$ and $1_F$ be the indicators for the initial state and for the accepting states, respectively. Finally, let $n = |Q|$.

The number of words of length $m$ is $c_m := 1_F M^m 1_{q_0}$. Compute $c_m$ for $0 \leq m < 2n$. If $c_n + \cdots + c_{2n-1} > 0$ then the language accepted by the DFA is infinite. Otherwise, the number of words in the language is $c_0 + \cdots + c_{n-1}$.

(When computing powers of $M$, care must be taken regarding the magnitude of the entries, which is exponential in $m$. Since their size is only polynomial, the resulting algorithm runs in polynomial time.)

$\endgroup$
  • 2
    $\begingroup$ I love this approach. I've also found that computing the eigenvalues of $M$ actually correspond to the roots of the denominator in the generating function approach, and that, perhaps unsurprisingly, these eigenvalues are invariant to DFA minimization. However, I have absolutely no idea how to correctly interpret this. $\endgroup$ – Lee Mar 10 '17 at 19:01
  • 1
    $\begingroup$ This is not so surprising, given that the generating function is $P(z) = \sum_{n=0}^\infty 1_F M^n 1_{q_0} z^n$, which simplifies to $P(z) = 1_F (I-zM)^{-1} 1_{q_0}$. You can get an even more explicit result by redoing this calculation using the Jordan form of $M$, which features the eigenvalues. $\endgroup$ – Yuval Filmus Mar 10 '17 at 19:04
7
$\begingroup$

Actually, you can still derive counting formulas for unambiguous regular expressions with Kleene stars within.

Given the inductive definition of a regular expression as: $$ \begin{equation*} e \in \mathrm{Re} := x \in \Sigma \mid e_0 ~ e_1 \mid e_0 + e_1 \mid e^* \end{equation*} $$

Consider the following translation $[\![\cdot]\!] : \mathrm{Re} \to \mathbb{C}(z)$ that takes a regular expression and translates it into a complex-valued rational function:

$$ \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*} $$

We can show that this translation returns a rational expression by doing structural induction on $e$, and noting that all of the operations used on the right-hand side preserves rational-ness.

Suppose that the regular expression $e$ that we put in is unambiguous, then we would find that the rational function denoted by $[\![e]\!] \in \mathbb{C}(z)$ is actually the generating function for the family of words that are accepted by the language underlying $e$, ranked by their length.

For example, consider the language $(a^*b)^*$, which defines the language of runs of $a$ delimited by $b$. Now, this regular expression is unambiguous, so we can run our translation trick:

$$ \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{\delta\left(n\right)}{2} $$ where $$ \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)} $$ where $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} $$ where $q^*_k$ are the roots of $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} $$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.