Mi motivación para esta pregunta es de la siguiente juguete ejemplo; definir la (no determinista) máquina de estados finitos generado por el polinomio $f(x_0 , ... , x_n) \in \mathbb{Z} [x_0 , x_1 , ... , x_n]$, denotado $\text{NFA}(f)$, a la $5$-tupla $$\text{NFA}(f) = (\partial f, \Sigma, f, \delta \equiv0),$$ donde
- $\partial f = \{ \text{all partial derivatives of } f \} \text{ is the set of states,}$
- $\text{alphabet } \Sigma = \Bigg \{ \frac{\partial}{\partial x_0}, \frac{\partial}{\partial x_1}, ... , \frac{\partial}{\partial x_n} \Bigg \},$
- $f = f(x_0 , x_1 , ... , x_n ) \text{ is the unique start state},$
- $\text{transition (partial (no pun intended)) function } \delta : \Sigma \times \partial f \longrightarrow \partial f, \bigg( \frac{ \partial}{\partial x_i} , p \bigg) \mapsto \frac{\partial p}{\partial x_i}, \text{ where we only keep those elements } \bigg( \frac{\partial}{\partial x_i} , p \bigg) \text{ that satisfy } \frac{\partial p}{\partial x_i} \neq 0 \text {, or } \frac{\partial p }{\partial x_i} = 0 \text{ for all } i,$
- $\text{and } \equiv0, \text{ the zero polynomial, is the unique accept state.}$
La cardinalidad de a $\partial f$ es el título de la pregunta.
La restricción de la "plena" transición de la función para la transición parcial de la función de $\delta$ definido anteriormente se hace para asegurarse de que la expresión regular que representa el idioma $\text{NFA}(f)$ acepta, $\doteq \mathscr{L} (f)$, no es siempre trivial.
Por ejemplo: en Primer lugar, cambiar la notación a través de $\Bigg \{ \frac{\partial}{\partial x_0}, \frac{\partial}{\partial x_1}, ... , \frac{\partial}{\partial x_n} \Bigg \} \longleftrightarrow \{0,1, ... , n \}$ en la forma obvia. A continuación, en $\mathbb{Z} [x,y]$ hemos
$$\mathscr{L}(x) = (00+01)(0+1)^{*} = 0(0+1)(0+1)^{*}$$ $$\mathscr{L}(y) = (10 + 11)(0+1)^{*} = 1(0+1)(0+1)^{*}$$ $$\mathscr{L}(x+y) = (00 + 01 + 10 + 11)(0+1)^{*} = (0+1)(0+1)(0+1)^{*}$$ $$\mathscr{L}(xy) = (010 + 011 + 100 + 101)(0+1)^{*} = (01 + 10)(0+1)(0+1)^{*}$$ $$\mathscr{L}(x^2 y) = (0010 +0011 + 0100 + 0101 + 1000 + 1001)(0+1)^{*} = (001 + 010 + 100)(0+1)(0+1)^{*}$$ $$\text{etc.},$$
o después de que abusando de la notación (todas esas expresiones regulares terminará en $(0+1)(0+1)^{*}$), llegamos a la
$$\mathscr{L}(x) = 0,$$ $$\mathscr{L}(y) = 1,$$ $$\mathscr{L}(x+y) = 0 + 1,$$ $$\mathscr{L}(xy) = 01 + 10,$$ $$\mathscr{L}(x^2 y) = 001 + 010 + 100$$ $$\text{etc.}$$
y $|\partial x| = |\partial y| = |\partial (x+y)| = 3, |\partial xy| = 5, |\partial x^2 y| = 7,$ etc.
