% Clase 2: Lenguajes formales. Lenguajes decidibles.

Apunte

Apuntes

• ‘Computabilidad, Complejidad y Verificación de Programas’, Rosenfeld e Irazábal, 2013
  • Clase 2. Jerarquía de la computabilidad
  • ejercicios interesantes: 2, 3
• Artículo “La Máquina de Turing” de Manuel Alfonseca

Lenguajes formales

Definición

• Dado un alfabeto (conjunto de símbolos), se pueden formar palabras (secuencias de símbolos del alfabeto dado).
• Un lenguaje formal es un conjunto de palabras finitas sobre un alfabeto dado.

Ejemplo

alfabeto: {a,b}

lenguaje: conjunto de las palabras que tienen el mismo número de símbolos a que b

ejemplos de palabras del lenguaje: ab ba abaabb bbbaaa…

Otro ejemplo

alfabeto: {0,1}

lenguaje: conjunto de las palabras que representan enteros en base 2, que sean primos

ejemplos: 10 11 101 111 1001 1011 …

Aclaración

• Se dice lenguaje formal para insistir sobre la definición precisa, sin ambiguedades,
• Un forma de definir es usando una descripción en lenguaje natural
• Otra forma es usar algun “mecanismo” bien definido, que pueda “testear” cualquier palabra y decir si sí o no pertenece al lenguaje
• Uno de esos mecanismos es la máquina de Turing
• Otro es el autómata finito

MT que deciden un lenguaje

Una MT M decide un lenguaje $L$ si para toda $x$ dada como entrada de M, M siempre termina, y acepta $x$ si, y solamente si, $x\in L$.

Un lenguaje es decidible si existe una MT que lo decide.

Proposiciones

• Si $L$ es decidible entonces su complemento $\bar{L}$ lo es.
• Si $L_1$ y $L_2$ son decidibles, entonces también lo son:
  • $L_1 \cup L_2$
  • $L_1 \cap L_2$
  • $L_1 \setminus L_2$