Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página4/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   2   3   4   5   6   7   8   9   ...   31


Lo mismo ocurre para los lenguajes recursivos, Ya que un lenguaje L sobre un alfabeto A, será recursivo si y solo si los lenguajes L y A* - L son ambos r.e.
Otra ambigüedad viene del hecho de que un lenguaje particular puede considerarse respecto a mas de un alfabeto. Sea, por ejemplo, Ā un alfabeto de n letras y /A un alfabeto de m letras que contiene a A (m > n). Un lenguaje ,L, sobre el alfabeto A, es simplemente un subconjunto de A* . De esta forma, L será también un lenguaje sobre el alfabeto Ā. De esta forma dependiendo del alfabeto que se considere veremos los elementos de L como cadenas representando números en base n o en base m. En cada caso, estaremos considerando distintos conjuntos de números. Podría entonces darse el caso de que el hecho de que un lenguaje L sea o no r.e. dependa del alfabeto considerado. Como un ejemplo, podemos tomar A={a} y Ā = {a,b}, y considerar el lenguaje L0 anterior. Tenemos

L0 A /A

En Ā vimos que este lenguaje es r.e. y que tenía asociado el conjunto Q1 ó Q2 de números dependiendo del orden de los símbolos del alfabeto. Como lenguaje sobre el alfabeto A, el conjunto de números es otro:



Q3 = { n N/ n > 0}

que resulta también recursivamente enumerable. De hecho esta coincidencia va a ocurrir siempre como demuestra el siguiente teorema.



Teorema. - Sea A Ā donde A y Ā son alfabetos y sea L A* . Entonces L es r.e. en el alfabeto A si y solo si L es r.e. en Ā

Demostración.-

Sea L r.e. en A y sea M una máquina de Turing en el alfabeto A que acepta el lenguaje L. Sin pérdida de generalidad, podemos suponer que M comienza moviéndose hacia la derecha hasta que encuentra un blanco y, entonces, vuelve a la posición original. Sea la máquina de Turing que se obtiene a partir de M añadiendo las cuadruplas de la forma

q s s q


para cada símbolo s Ā - A, y cada estado q de la máquina M.

En estas condiciones M entrará en un bucle infinito siempre


que en la cinta haya un símbolo que no esté en A. Y aceptará exactamente las mismas cadenas que m, es decir el lenguaje L.

Luego es un lenguaje r.e en Ā.


Recíprocamente, sea L un lenguaje r.e. en Ā, y sea M una máquina de Turing con alfabeto Ā que acepta el Lenguaje L. Sea g(x) la función A* que acepta el lenguaje L. Sea g(x) la función A* que calcula M. Como LA* , tenemos que
L= { x A· / g(x) } .
Como g(x) es calculable, se sigue que L es un lenguaje r.e. en A.
Corolario.- Sean A, Ā y L como en el teorema anterior. Entonces L es un lenguaje recursivo en A si y sólo sí es un lenguaje recursivo en Ā.

Demostración.-

Sea L un lenguaje recursivo en A. Entonces L y A· - L son r.e. en A, y por tanto en Ā. Además como

Ā* - L = ( Ā* - A* ) ( A* - L )
Y el conjunto (Ā* - A*) es r.e. (como fácilmente se puede demostrar), se sigue que Ā* - L es r.e y por tanto L es un lenguaje recursivo en Ā.

Recíprocamente, si L es un lenguaje recursivo en Ā, entonces L y Ā* son r.e. en Ā y, por tanto, L será también recursivamente enumerable en A. Por otra parte, como


Ā* - L = (Ā* - L) A*,
Y como A* es r.e. en Ā, resulta que A* - L es r.e. en Ā y, por tanto, en A. Por lo que L es un lenguaje recursivo en A.
Ejercicios


  1. Describir una máquina de Turing que acepte todas las palabras del alfabeto {a,b} de la forma a(1)ba(1).

  2. Demostrar que el conjunto Ā* - A* del corolario anterior es un lenguaje r.e.


1   2   3   4   5   6   7   8   9   ...   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal