Siguiente: Homomorfismos Un nivel arriba: Relaciones de orden Anterior: Orden de prefijo

Orden lexicográfico

Sea $\Sigma$ un alfabeto dotado de un orden ``$\leq$'', por ejemplo, para el alfabeto ASCII consideramos el orden usual. Extendemos el orden ``$\leq$'' de $\Sigma$ a un orden `` $\leq_{\mbox{\scriptsize\it lg}}$'' de $\Sigma^*$ mediante la definición siguiente:

$$\begin{eqnarray*}\forall\sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1\leq_{\mbox{\scri... ...y}\right\}\Rightarrow s_1<s_2\end{displaymath} \end{minipage}} \end{eqnarray*}$$

La siguiente proposición resume las propiedades más elementales de este orden, llamado lexicográfico. Su demostración es más tediosa que instructiva y por esa razón la omitimos.

Proposición 2.7   El orden lexicográfico satisface las propiedades siguientes:

1.

Es, en efecto, un orden, es decir, cualesquiera que sean las palabras $\sigma, \tau, \upsilon$,

$$\begin{eqnarray*}&& \sigma \leq_{\mbox{\scriptsize\it lg}} \sigma \\ (\sigma \... ..._{\mbox{\scriptsize\it lg}} \sigma) &\Rightarrow& \sigma = \tau \end{eqnarray*}$$

2.

Es lineal, es decir, $\forall \sigma, \tau$: $\left(\sigma \leq_{\mbox{\scriptsize\it lg}} \tau\right)\lor \left(\sigma = \tau\right)\lor \left(\tau \leq_{\mbox{\scriptsize\it lg}} \sigma\right).$

3.

Es congruente por la izquierda, es decir, $\forall \sigma, \tau: \upsilon$, $\left(\sigma \leq_{\mbox{\scriptsize\it lg}} \tau\ \Rightarrow \ \upsilon\sigma \leq_{\mbox{\scriptsize\it lg}} \upsilon\tau\right)$. Mas no lo es por la derecha.