El concepto de símbolo es un concepto primitivo, es decir no definiremos que es un símbolo. Tampoco definiremos matemáticamente el concepto de palabra solo diremos en forma intuitiva que una palabra es una yuxtaposición de símbolos. Asumiremos que el lector tiene una intuición clara acerca de este tipo de objetos y de sus propiedades básicas. Las palabras de longitud \(1\) son exactamente los símbolos. Usaremos \(\left\vert \alpha\right\vert\) para denotar la longitud de la palabra \(\alpha\). Si \(\alpha\) es una palabra y \(\sigma\) es un símbolo, usaremos \(\left\vert \alpha\right\vert _{\sigma}\) para denotar la cantidad de ocurrencias de \(\sigma\) en \(\alpha\). Si \(\alpha,\beta\) son palabras, entonces \(\alpha\beta\) denotará la concatenación de las palabras \(\alpha\text{ y }\beta\). La única palabra de longitud \(0\) es denotada con \(\varepsilon\). Nótese que \(\alpha\varepsilon=\varepsilon\alpha\), para cualquier palabra \(\alpha\). También concatenaremos una sucesión de palabras, es decir si \(\alpha_{1},...,\alpha_{n}\), son palabras, 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 con \(\alpha^{n}\) denotaremos la palabra \(\alpha_{1}...\alpha_{n}\). O sea que \(\alpha^{0}=\varepsilon\).
Si \(\alpha,\beta\) son palabras, entonces 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).
Dada una palabra \(\alpha\) y \(i\in\omega\), definamos \[\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-ésimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.\] Dada una palabra \(\gamma\), 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 una palabra \(\alpha\), 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\), 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}\)
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\). En particular esto nos dice que \(\Sigma\subseteq\Sigma^{\ast}\). Ya que en \(\varepsilon\) no ocurren símbolos, tenemos que \(\varepsilon\in\Sigma^{\ast}\), para cualquier alfabeto \(\Sigma\). Más aún nótese que \(\emptyset^{\ast}=\{\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\}\).
Llamaremos numerales a los siguientes símbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Nótese que \(Num\cap\omega=\emptyset\). Es decir, no debemos confundir los símbolos que usualmente denotan los primeros diez elementos de \(\omega\) con los números que ellos denotan. De hecho en china o japón los primeros diez elementos de \(\omega\) se denotan con otros símbolos. Similarmente las palabras pertenecientes a \(Num^{\ast}\) denotan (notación decimal) a los números de \(\omega\) pero debemos tener en cuenta que \(Num^{\ast}\cap\omega=\emptyset\). Cuando tratamos con palabras de \(Num^{\ast}\), debemos ser cuidadosos ya que muchas veces en nuestro discurso matemático (es decir las guías, y este apunte, lo que escriben los profesores en el pizarrón, etc) representamos dos objetos diferentes de la misma forma. Por ejemplo \(45\) puede estar denotando al número entero cuarenta y cinco o también \(45\) puede estar denotando la palabra de longitud \(2\) cuyo primer símbolo es el numeral \(4\) y cuyo segundo símbolo es el numeral \(5\), es decir en este segundo caso \(45\) se esta denotando a si misma. Por dar otro ejemplo, el símbolo \(1\) en nuestro discurso algunas veces se denotará a si mismo y otras veces denotará al número uno. Resumiendo, hay muchas palabras que algunas veces en nuestro discurso se representan a si mismas y otras veces representan a otro objeto matemático y es tarea del lector saber que corresponde en cada caso.
Los numerales bold son los numerales en modo negrita, es decir \[\mathbf{0}\mathbf{\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}\] Cabe aclarar que estos numerales bold son distintos a los numerales antes introducidos. También usaremos los numerales itálicos \[\mathit{0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}\] que obviamente son símbolos distintos a los numerales clásicos y a los bold.