Un alfabeto es un conjunto finito de simbolos. Notese que \(\emptyset\) es un alfabeto. Si \(\Sigma\) es un alfabeto, entonces \(\Sigma^{\ast}\) denotara el conjunto de todas las palabras formadas con simbolos de \(\Sigma\). Las palabras de longitud \(1\) son exactamente los elementos de \(\Sigma\), en particular esto nos dice que \(\Sigma\subseteq\Sigma^{\ast}\). La unica palabra de longitud \(0\) es denotada con \(\varepsilon\). Ya que en \(\varepsilon\) no ocurren simbolos, tenemos que \(\varepsilon\in\Sigma^{\ast}\), para cualquier alfabeto, mas aun notese 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 simbolo \(\sigma\) en \(\alpha\). Notese que funciones, \(n\)-uplas y palabras son objetos de distinto tipo, por lo cual \(\emptyset\), \(\Diamond\) y \(\varepsilon\) son tres objetos matematicos diferentes.
Si \(\alpha_{1},...,\alpha_{n}\in\Sigma^{\ast}\), con \(n\geq0\), usaremos \(\alpha_{1}...\alpha_{n}\) para denotar la concatenacion de las palabras \(\alpha_{1},...,\alpha_{n}\) (notese 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\) sera 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 lementos de \(L\). Es decir: \[L^{+}=\{\alpha_{1}...\alpha_{n}:\alpha_{1},...,\alpha_{n}\in L\text{ y }n\geq1\}\] Notese 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 resiproca de \(\gamma\).
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 comensamos a leer desde el lugar \(i\)-esimo de \(\beta\) en adelante, leeremos la palabra \(\alpha\) completa y luego posiblemente seguiran otros simbolos.
Notese que una palabra \(\alpha\) puede ocurrir en \(\beta\), a partir de \(i\), y tambien 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 tambien 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 posicion. 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 matematica precisa el concepto de ocurrencia pero el lector no tendra problemas en comprenderlo y manejarlo en forma correcta.
Tambien 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 reeplazar simultaneamente 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 simultaneamente cada ocurrencia de \(\alpha\) en \(\beta\) por \(\gamma\). Es importante notar que los reemplazos se hacen simultaneamente 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 asi 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 cituaciones.
Tambien se pueden hacer reemplazos simultaneos 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 simultaneamente:
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 simultaneamente:
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}\)