Lenguaje de empalme

En matemáticas y ciencias de la computación teórica, un lenguaje de empalme es un lenguaje formal que formaliza la acción de empalme de genes en biología molecular . Los lenguajes de empalme tienen diversas definiciones basadas en la forma de las reglas de empalme permitidas, que describen cómo se pueden "cortar" y "pegar" cadenas del lenguaje para obtener nuevas cadenas. En todos ellos, dado un lenguaje inicial${\displaystyle I}$sobre un alfabeto finito${\displaystyle \Sigma }$y un conjunto de reglas de empalme${\displaystyle R}$, un lenguaje de empalme es el lenguaje más pequeño que contiene${\displaystyle I}$que se cierra aplicando cualquier regla de empalme${\displaystyle r\in R}$.

La definición original de un lenguaje de empalme fue dada por Head en 1987. ^{[ 1 ]} Posteriormente, Păun ^{[ 2 ]} y Pixton ^{[ 3 ]} proporcionaron definiciones alternativas y no equivalentes. La clase de lenguajes generados por el empalme de Head está estrictamente contenida en la de los generados por el empalme de Păun, que a su vez está estrictamente contenida en la de los generados por el empalme de Pixton. ^{[ 4 ]}

La siguiente definición es la de un sistema de empalme Păun, ^{[ 5 ]} que es el más común:

Dejar${\displaystyle \Sigma }$ser un alfabeto finito y${\displaystyle I\subseteq \Sigma ^{*}}$un idioma. Una regla de empalme es una cuádruple${\displaystyle r=(u_{1},v_{1},u_{2},v_{2})\in (\Sigma ^{*})^{4}}$(a menudo escrito)${\ Displaystyle r = (u_ {1}, v_ {1}; u_ {2}, v_ {2})}$). Para${\displaystyle w_{1},w_{2}\in \Sigma ^{*}}$y una regla de empalme${\displaystyle r=(u_{1},v_{1};u_{2},v_{2})\in (\Sigma ^{*})^{4}}$, escribimos${\displaystyle (w_{1},w_{2})\vdash _{r}z}$si${\ Displaystyle w_ {1} = x_ {1} u_ {1} v_ {1} y_ {1}}$,${\ Displaystyle w_ {2} = x_ {2} u_ {2} v_ {2} y_ {2}}$, y${\displaystyle z=x_{1}u_{1}v_{2}y_{2}}$. Si${\displaystyle R}$es un conjunto de reglas de empalme sobre${\displaystyle \Sigma }$, decimos que${\displaystyle \sigma =(\Sigma ,R)}$es un esquema H y define la acción de${\displaystyle \sigma }$en${\displaystyle I}$ser${\displaystyle \sigma (I)=\{z\in \Sigma ^{*}:\exists w_{1},w_{2}\in I{\text{ st }}(w_{1},w_{2})\vdash _{r}z{\text{ }}\forall r\in R\}}$Ahora, inductivamente, dejemos que${\displaystyle \sigma ^{0}(I)=I}$y${\displaystyle \sigma ^{i+1}(I)=\sigma (\sigma ^{i}(I))}$.${\displaystyle \sigma ^{*}(I)=\bigcup _{i\in \mathbb {Z} _{0}^{+}}\sigma ^{i}(I)}$es el lenguaje de empalme generado por el sistema H${\displaystyle H=(\Sigma ,I,R)}$. Es decir, el lenguaje más pequeño que contiene${\displaystyle I}$y cerrado bajo solicitudes de cualquier${\displaystyle r\in R}$.

Un conjunto de reglas${\displaystyle R}$es reflexivo si${\displaystyle (u_{1},v_{1};u_{2},v_{2})\in R}$implica que${\displaystyle (u_{1},v_{1};u_{1},v_{1}),(u_{2},v_{2};u_{2},v_{2})\in R}$Un conjunto de reglas ${\displaystyle R}$es simétrico si${\displaystyle (u_{1},v_{1};u_{2},v_{2})\in R}$implica que${\displaystyle (u_{2},v_{2};u_{1},v_{1})\in R}$. Un lenguaje de empalme se denomina reflexivo (o simétrico) si es generado por un sistema H reflexivo (o simétrico).

Un ejemplo contrario de un lenguaje de empalme es${\displaystyle (aa)^{*}}$, mientras${\displaystyle b(aa)^{*}}$es un lenguaje de empalme. De hecho, si${\displaystyle L}$es un lenguaje regular en el alfabeto${\displaystyle \Sigma }$, y${\displaystyle b}$es una carta que no está${\displaystyle \Sigma }$, entonces el idioma${\displaystyle bL=\{bw:w\in L\}}$es un lenguaje de empalme. ^{[ 6 ]}

Todos los lenguajes de empalme generados por un lenguaje inicial finito y un conjunto de reglas finito son regulares . ^{[ 5 ]}

Es decidible si un lenguaje regular es o no un lenguaje de empalme ^{[ 7 ]} y si es o no reflexivo. ^{[ 8 ]} Ambos algoritmos utilizan la decidibilidad de si una regla de empalme respeta o no un lenguaje regular, lo que significa que el lenguaje es cerrado bajo empalme por esa regla.

Cada lenguaje de empalme regular contiene una constante , que es una palabra.${\displaystyle c\in \Sigma ^{*}}$de tal manera que${\displaystyle u_{1}cv_{1},u_{2}cv_{2}\in L}$implica que${\displaystyle u_{1}cv_{2},u_{2}cv_{1}\in L}$para cualquier${\displaystyle u_{1},v_{1},u_{2},v_{2}\in \Sigma ^{*}}$. ^{[ 9 ]}

${\displaystyle b(aa)^{*}\cup (aa)^{*}b\cup (aa)^{*}}$es un lenguaje de empalme reflexivo que no es simétrico. También es generado por un sistema de empalme finito. ^{[ 10 ]}

${\displaystyle a^{*}ba^{*}ba^{*}\cup a^{*}ba^{*}\cup a^{*}}$es un lenguaje de empalme generado por un sistema de empalme finito que no es ni reflexivo ni simétrico. ^{[ 10 ]}