Un alfabeto es un conjunto finito de símbolos. Nótese que \(\emptyset\) es un alfabeto. Si \(\Sigma\) es un alfabeto, entonces \(\Sigma^{\ast}\) denotará el conjunto de todas las palabras formadas con símbolos de \(\Sigma\). Las palabras de longitud \(1\) son exactamente los elementos de \(\Sigma\), en particular esto nos dice que \(\Sigma\subseteq\Sigma^{\ast}\). La única palabra de longitud \(0\) es denotada con \(\varepsilon\). Ya que en \(\varepsilon\) no ocurren símbolos, tenemos que \(\varepsilon\in\Sigma^{\ast}\), para cualquier alfabeto, mas aun nótese que \(\emptyset^{\ast}=\{\varepsilon\}\). Usaremos \(\left\vert \alpha\right\vert\) para denotar la longitud de la palabra \(\alpha\). Si \(\alpha\in\Sigma^{\ast}\) y \(\sigma\in\Sigma\), usaremos \(\left\vert \alpha\right\vert _{\sigma}\) para denotar la cantidad de ocurrencias del símbolo \(\sigma\) en \(\alpha\). Nótese que funciones, \(n\)-uplas y palabras son objetos de distinto tipo, por lo cual \(\emptyset\), \(\lozenge\) y \(\varepsilon\) son tres objetos matemáticos diferentes.
Si \(\alpha_{1},...,\alpha_{n}\in\Sigma^{\ast}\), con \(n\geq0\), usaremos \(\alpha_{1}...\alpha_{n}\) para denotar la concatenación de las palabras \(\alpha_{1},...,\alpha_{n}\) (nótese que cuando \(n=0\), resulta que \(\alpha_{1}...\alpha_{n}=\varepsilon\)). Si \(\alpha_{1}=...=\alpha_{n}=\alpha\), entonces escribiremos \(\alpha^{n}\) en lugar de \(\alpha_{1}...\alpha_{n}\). O sea que \(\alpha^{0}=\varepsilon\).
Un lenguaje sobre \(\Sigma\) será un subconjunto de \(\Sigma^{*}\). Si \(L\) es un lenguaje sobre \(\Sigma\), entonces denotaremos con \(L^{+}\) al conjunto formado por todas las concatenaciones de sucesiones finitas no nulas de elementos de \(L\). Es decir: \[L^{+}=\{\alpha_{1}...\alpha_{n}:\alpha_{1},...,\alpha_{n}\in L\text{ y }n\geq1\}\] Definamos también \[L^{*}=L^{+}\cup\{\varepsilon\}\] Nótese que en particular obtenemos que \(\Sigma^{+}=\Sigma^{\ast}-\{\varepsilon\}\).
Diremos que \(\alpha\) es subpalabra (propia) de \(\beta\) cuando (\(\alpha\notin\{\varepsilon,\beta\}\) y) existan palabras \(\delta,\gamma\) tales que \(\beta=\delta\alpha\gamma\). Diremos que \(\beta\) es un tramo inicial (propio) de \(\alpha\) si hay una palabra \(\gamma\) tal que \(\alpha=\beta\gamma\) (y \(\beta\notin\{\varepsilon,\alpha\}\)). En forma similar se define tramo final (propio).
Dados \(i\in\omega\) y \(\alpha\in\Sigma^{\ast}\) definamos \[\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-esimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.\] Dada \(\gamma\in\Sigma^{\ast}\), definamos \[\gamma^{R}=\left\{ \begin{array}{lll} [\gamma]_{\left\vert \gamma\right\vert }[\gamma]_{\left\vert \gamma\right\vert -1}...[\gamma]_{1} & & \text{si }\left\vert \gamma\right\vert \geq1\\ \varepsilon & & \text{caso contrario} \end{array}\right.\] La palabra \(\gamma^{R}\) es llamada la reciproca de \(\gamma\).
Dada \(\alpha\in\Sigma^{\ast}\), definamos \[^{\curvearrowright}\alpha=\left\{ \begin{array}{lll} \left[\alpha\right]_{2}...\left[\alpha\right]_{\left\vert \alpha\right\vert } & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha^{\curvearrowleft}=\left\{ \begin{array}{lll} \left[\alpha\right]_{1}...\left[\alpha\right]_{\left\vert \alpha\right\vert -1} & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\]
Dadas palabras \(\alpha,\beta\in\Sigma^{\ast}\), con \(\left\vert \alpha\right\vert ,\left\vert \beta\right\vert \geq1\), y un natural \(i\in\{1,...,\left\vert \beta\right\vert \}\), se dice que \(\alpha\) ocurre a partir de \(i\) en \(\beta\) cuando se de que existan palabras \(\delta,\gamma\) tales que \(\beta=\delta\alpha\gamma\) y \(\left\vert \delta\right\vert =i-1\). Intuitivamente hablando \(\alpha\) ocurre a partir de \(i\) en \(\beta\) cuando se de que si comenzamos a leer desde el lugar \(i\)-ésimo de \(\beta\) en adelante, leeremos la palabra \(\alpha\) completa y luego posiblemente seguirán otros símbolos.
Nótese que una palabra \(\alpha\) puede ocurrir en \(\beta\), a partir de \(i\), y también a partir de \(j\), con \(i\neq j\). En virtud de esto, hablaremos de las distintas ocurrencias de \(\alpha\) en \(\beta\). Por ejemplo hay dos ocurrencias de la palabra \(aba\) en la palabra \[cccccccabaccccabaccccc\] y también hay dos ocurrencias de la palabra \(aba\) en la palabra \[cccccccababacccccccccc\] En el primer caso diremos que dichas ocurrencias de \(aba\) son disjuntas ya que ocupan espacios disjuntos dentro de la palabra. En cambio en el segundo caso puede apreciarse que las dos ocurrencias se superponen en una posición. A veces diremos que una ocurrencia esta contenida o sucede dentro de otra. Por ejemplo la segunda ocurrencia de \(ab\) en \(babbbfabcccfabccc\) esta contenida en la primer ocurrencia de \(fabc\) en \(babbbfabcccfabccc\).
No definiremos en forma matemática precisa el concepto de ocurrencia pero el lector no tendrá problemas en comprenderlo y manejarlo en forma correcta.
También haremos reemplazos de ocurrencias por palabras. Por ejemplo el resultado de reemplazar la primer ocurrencia de \(abb\) en \(ccabbgfgabbgg\) por \(oolala\) es la palabra \(ccoolalagfgabbgg\). Cuando todas las ocurrencias de una palabra \(\alpha\) en una palabra \(\beta\) sean disjuntas entre si, podemos hablar del resultado de reemplazar simultáneamente cada ocurrencia de \(\alpha\) en \(\beta\) por \(\gamma\). Por ejemplo si tenemos \[\begin{aligned} \alpha & =yet\\ \beta & =ghsyetcjjjyetbcpyeteabc\\ \gamma & =\%\% \end{aligned}\] entonces \(ghs\%\%cjjj\%\%bcp\%\%eabc\) es el resultado de reemplazar simultáneamente cada ocurrencia de \(\alpha\) en \(\beta\) por \(\gamma\). Es importante notar que los reemplazos se hacen simultáneamente y no secuencialmente (i.e. reemplazando la primer ocurrencia de \(\alpha\) por \(\gamma\) y luego al resultado reemplazarle la primer ocurrencia de \(\alpha\) por \(\gamma\) y así sucesivamente). Obviamente el reemplazo secuencial puede dar un resultado distinto al simultaneo (que es el que usaremos en general) e incluso puede suceder que en el reemplazo secuencial el proceso se pueda iterar indefinidamente. Dejamos al lector armar ejemplos de estas situaciones.
También se pueden hacer reemplazos simultáneos de distintas palabras en una palabra dada. Supongamos tenemos palabras \(\alpha_{1},...,\alpha_{n},\beta\) tales que
adhocprefix-adhocsufix \(\alpha_{i}\neq\alpha_{j}\), para \(i\neq j\)
adhocprefix-adhocsufix Para cada \(i\), las distintas ocurrencias de \(\alpha_{i}\) en \(\beta\) son disjuntas
adhocprefix-adhocsufix Si \(\alpha_{i}\) ocurre en \(\beta\) y \(\alpha_{j}\) ocurre en \(\beta\), con \(i\neq j\), entonces dichas ocurrencias son disjuntas
entonces dadas palabras cualesquiera \(\gamma_{1},...,\gamma_{n}\) hablaremos del resultado de reemplazar simultáneamente:
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{1}\) en \(\beta\), por \(\gamma_{1}\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{2}\) en \(\beta\), por \(\gamma_{2}\)
adhocprefix adhocsufix \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{n}\) en \(\beta\), por \(\gamma_{n}\)
Por ejemplo si tomamos \[\begin{aligned} \alpha_{1} & =gh\\ \alpha_{2} & =yet\\ \alpha_{3} & =ana\\ \beta & =ghbbbyetbbgh\%\%ana\#\#ana!!!ana\\ \gamma_{1} & =AA\\ \gamma_{2} & =BBBB\\ \gamma_{3} & =CCC \end{aligned}\] entonces \(AAbbbBBBBbbAA\%\%CCC\#\#CCC!!!CCC\) es el resultado de reemplazar simultáneamente:
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{1}\) en \(\beta\), por \(\gamma_{1}\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{2}\) en \(\beta\), por \(\gamma_{2}\)
adhocprefix -adhocsufix cada ocurrencia de \(\alpha_{3}\) en \(\beta\), por \(\gamma_{3}\)