• Author / Uploaded
• Pablo Cabrera Camposeco

Citation preview

Curso Informática III – 2016

EJERCICIOS RESUELTOS UNIDAD I 1) Utilizando el Principio de Inducción Matemática (PIM), demuestre que la suma de los cubos de los “n” primeros números naturales es igual al cuadrado de la suma de ellos. Solución: Se vuelve a enunciar el problema de la siguiente manera: Demuestre que

 n  nN;  i    i  i 0  i 0  n

2

3

En el presente capítulo se demostró por PIM que: nN;

n

i  i 0

n(n  1) , 2

entonces, al utilizar esto para rescribir el enunciado: nN;

2

n 2 (n  1) 2  n(n  1)  3 , i      4  2  i 0 n

y ahora se procede a demostrar por inducción matemática: I.

Caso Base: para n = 0, se verifica:

0 2 (0  1) 2 0 i 0 0  4 i 0 Por lo tanto, la fórmula se cumple en el caso base. 0

3

II.

3

y

Se define la hipótesis inductiva y la tesis: k 2 (k  1) 2 4 i 0 2 2 K 1 Tesis:  i 3  (k  1) (k  2) 4 i 0 K

H.I.:

i

3



Al utilizar la H.I. y propiedades de sumatorias: K 1

K

i  i 3

i 0

i 0

3



K 1

i

i  K 1

3



k 2 (k  1) 2 k 2 (k  1) 2  4(k  1) 3  (k  1) 3  4 4

1

Curso Informática III – 2016

(k  1) 2 (k 2  4(k  1)) (k  1) 2 (k 2  4k  4) (k  1) 2 (k  2)    4 4 4

2

se cumple también la tesis y, por el PIM, la fórmula es válida para todos los números naturales 2) Usando PIM demuestre que n  N: n

 i(i  2)  1* 3  2 * 4  3 * 5  ...  n(n  2)  i 0

n(n  1)(2n  7) 6

Solución: i. Se verifica para n = 0 (caso base): 0



i (i + 2) = 0 (0 + 2) = 0 =

i 0

0(0  1)(2(0)  7) =0 6

ii. Se formula la H.I. y la tesis: Para algún k  N,

H.I.:

k



i (i + 2) =

i 0

k 1

Tesis:



i (i + 2) =

i 0

k 1



k

i (i + 2) =

i 0

 i(i  2)  i 0

k (k  1)(2k  7) 6

(k  1)((k  1)  1)(2(k  1)  7) 6 k 1

 i(i  2)

por propiedad de sumatorias

i  k 1

k

=



i (i + 2) + (k+1)((k+1)+2)

i 0

k (k  1)(2k  7)  6(k  1)((k  1)  2) por H.I. 6 (k  1)[k (2k  7)  6((k  1)  2)] = 6 2 (k  1)(2k  7k  6k  6  2) = 6 2 (k  1)(2k  13k  8) = 6

=

2

Curso Informática III – 2016 (k  1)(k  2)(2k  9) 6 (k  1)((k  1)  1)(2(k  1)  7) = 6

=

Q.E.D. 3) Demuestre por PIM que n ≥ 1; n

 i(i!)  (n  1)!1 i 1

Solución: Se procede a demostrar por inducción matemática: i.

Caso base: para n = 1, se verifica que: 1

 i(i!)  1.(1)! 1 i 1

, y por otra parte, (1+1)! – 1 = 2! – 1 = 1

Por lo que la fórmula se cumple para el caso base. ii.

Caso inductivo: Se plantea la hipótesis inductiva para el número k N, y se asume verdadera: k

H.I. :

 i(i!)  (k  1)!1 i 1

Se probará para el caso k + 1, es decir, se demostrará la tesis: k 1

Tesis:

 i(i!)  ((k  1)  1)!1 i 1

Prueba: k 1

k

k 1

i 1

i 1

i  k 1

 i(i!)   i(i!)   i(i!)

; por propiedad de sumatorias,

3

Curso Informática III – 2016 k

  i(i!)  (k  1)(k  1)! i 1

 (k  1)!1  (k  1)(k  1)! ; por sustitución de la H.I.  (k  1)!1  (k  1)  1 ; al factorizar (k+1)!

 (k  2)(k  1)!1  (k  2)!1

; por la definición recursiva de un

número factorial, n! = n x (n-1)!  (k  2)!1  ((k  1)  1)!1 Se cumple también la tesis y, por el PIM, la fórmula es válida n ≥ 1. 4) Demuestre por PIM que n  N; n

2

i

 2 n 1  1

i 0

Solución: Se procede a demostrar por inducción matemática: i.

Caso base: para n = 0, se verifica que: 0

2

i

 20  1

i 0

01 , y por otra parte, 2  1  1

Por lo que la fórmula se cumple para el caso base. iii.

Caso inductivo: Se plantea la hipótesis inductiva para el número k N, y se asume verdadera: k

H.I. :

2

i

 2 k 1  1

i 0

Se probará el caso para k + 1, es decir, deberá demostrarse la tesis: k 1

Tesis:

2

i

 2 ( k 1)1  1

i 0

4

Curso Informática III – 2016

Prueba: k 1

k

2  2 i

i 0

i

i 0



k 1

2

i

i  k 1

 2 ( k 1)  1  2 ( k 1)

; por propiedad de sumatorias

; por sustitución de H.I.

 2(2 ( k 1) )  1  2 ( k 2)  1  2 ( k 1)1  1 Se cumple también la tesis y, por el PIM, la fórmula es válida n  N. 5) Demuestre por PIM que  n ≥ 1, 6n es un número que acaba en 6. Puede utilizar lo siguiente: Un número que termine en el dígito 6 puede escribirse como 10a + 6 donde a  N. Solución: Se procede a demostrar por inducción matemática: i.

Caso base: Obviamente el caso para n = 1 es cierto porque 61 = 6.

ii.

Caso inductivo: Se plantea la hipótesis inductiva para el número n N, y se asume verdadera: H.I.: 6n = 10a + 6, donde a  N, y deberá probarse para el caso n + 1, es decir, deberá demostrarse la tesis: n Entonces: 6n+1 = 6 x6 = 6(10a + 6)

; por sustitución de la H.I.

= 60a + 36 = 60a + 30 + 6 = 10(6a + 3) + 6 = 10c + 6

; con c=6a + 3 entero

Por lo que 6n+1 termina en 6, es decir que la tesis queda comprobada, y luego se afirma por PIM que la proposición es válida  n ≥ 1.

5

Curso Informática III – 2016

6) Se define el producto de matrices reales 2×2 de la siguiente manera:  a b  e    c d  g

f   ae  bg  h   ce  dg

af  bh   ; a, b, c, d  R. cf  dh 

Sea Fk el k-ésimo número de Fibonacci, al usar el PIM demuestre que: k

F 1 1      k 1 1 0   Fk

Fk   Fk 1 

Por el P.I.M. i. Se verifica para k=1, es decir, para el caso base: 1

F1   F0 

1 1  1 1   F2   =   =  1 0 1 0      F1

ii. Se formulan la H.I. y la tesis: k

H.I.

F 1 1    =  k 1 1 0   Fk

1 1   Tesis  1 0 

k 1

Fk   Fk 1 

 F( k 1)1 =   F( k 1) k

F( k 1)   F( k 1)1  1

1 1   1 1   usando la H.I.   =  1 0   1 0  1

 Fk 1 Fk  1 1     =   Fk Fk 1  1 0   Fk 1  FK Fk 1   de la definición de números de Fibonacci =   F F F K 1 K   k  F( k 1)1 =   F( k 1)

F( k 1)    Q.E.D. F( k 1)1 

6

Curso Informática III – 2016

7) Definamos un número triangular de la siguiente manera: Tn =

n(n  1) ;  n  N. Demuestre las siguientes proposiciones: 2

i) Tn+1 = Tn + n + 1 ii) 2Tn – n = n2 Solución: i)

Tn+1 = Tn + n + 1

De la formula demostrada en el tema 1. Tn =

n(n  1) = 2 n 1

Tn+1 =

k = k 0

n

 k , se obtiene, k 0

n

k

+ (n+1),

k 0

= Tn + n + 1

Q.E.D.

ii) ii.1) 2Tn – n = n2 Por PIM, se verifica para n=0 ( caso Base) 2T0 – 0 = 2(o) – 0 = 0 = 02 Se formula la H.I. y la tesis: H.I.

Para algún k   ; 2Tk – k = k2

Tesis:

2Tk+1 – (k+1) = (k+1) 2

 2(T + k + 1) – (K + 1) = k2 + 2k + 1 que se obtiene al k sustituir Tk+1 = Tk + k + 1  2T + k + 1 = k2 + 2k + 1  2T – k = k2 k k

7

Curso Informática III – 2016

Usando la H.I. se demuestra la proposición, y por lo tanto Q.E.D. ii.2) 2Tn – n = n2 De la H.I. 2Tk – k = k2 Sumando 2k + 1 a ambos lados, se tiene que: 2Tk + k + 1 = k2 + 2k + 1 = (k+1) 2 2Tk + k + 1 = 2Tk + 2k – k + 1 que se obtiene al sustituir k por: 2k – k = 2Tk + 2k – k + 2 – 1 que se obtiene al sustituir 1 por: 2 - 1 = 2(Tk + k + 1) – (k + 1) = (k + 1) 2 Usando la H.I. se demuestra la proposición, y por lo tanto Q.E.D.

8) Escriba un programa en lenguaje Pascal que implemente la función de Ackerman, definida anteriormente. Solución: public class Mayle{ public longint a(int n, int m){ if (n == 0) { return m+1; } if (m == 0) { return a(n-1,1); } if ((n != 0) && (m != 0)) { return (n-1,a(n,m-1)); } } public static void main (String args[]) { System.out.println(“Sumar números”); System.out.println(“Ackerman de números”); int resultado = a(x,y); System.out.println(“El Ackerman es: ” + resultado); } } 9) Utilizando el PIM, demuestre que para todo número natural n: A(3,n) = 2 n+3 – 3, en donde A (n,m) es la función de Ackerman Solución: 8

Curso Informática III – 2016

Para resolver este ejercicio, se utilizarán los resultados, ya demostrados en el presente capítulo, relacionados con la función de Ackerman, que fueron desarrollados al utilizar el PIM:   I.

yN, A(1,y) = y + 2 yN, A(2,y) = 2y + 3

Caso Base: se verifica para el caso y = 0: A(3,0) = A(2,1) = 2(1) + 3 =5

por el caso 2 de la definición suposición ii

2 0+3 – 3 = 2 3 – 3 = 8 – 3 = 5 II.

 la fórmula es válida para y=0

Se construye la hipótesis inductiva y la tesis: H.I:

A(3, k )  2 k 3  3

Tesis:

A(3, k  1)  2 ( k 1)3  3

Se calcula: A (3,k+1) = A (2, A(3,k)) por el caso 3 de la definición A (2, A(3,k)) = 2 A(3,k) + 3 suposición ii = 2 ( 2k+3 – 3) + 3 = 2k+4 – 6 + 3 = 2k+4 – 3 = 2(k+1) + 3 - 3  La tesis se cumple también al asumir la H.I., por lo que el PIM nos permite afirmar que se verifica para todos los números naturales. 10) Utilizando el principio de reducción al absurdo, demuestre que el conjunto de números primos es infinito. Solución: Suponga que el conjunto de números primos es finito, es decir, supóngase que existe únicamente un número n de números primos: P = {pjj : 1….n}. Formamos, entonces, un número entero positivo, llamado B, tal que: B = p1p2…pk…pn + 1 producto de todos los primos de P más 1. 9

Curso Informática III – 2016

De esta construcción se sabe que B> p1p2….pn y, con mayor razón, B>pn, es decir, según nuestra hipótesis, B es mayor que el mayor número primo y, por lo tanto, B no podría ser un número primo. Del teorema fundamental de la aritmética1 se sabe que si B no es primo, entonces debe existir un primo pk  P, tal que pk divide a B, por definición de divisibilidad se sabe que existe un m  N tal que: B  p1 p2 ... pk ... pn  1  pk m .

Al restar p1p2…pk…pn de ambos lados tenemos que: 1  p k m - p1p 2 ...p k ...p n  p k (m  p1p 2 ...p k-1p k 1 ...p n )

Sabemos que si pk es primo, entonces pk > 1, por lo tanto: p k (m  p1p 2 ...p k-1p k 1 ...p n )  1 ;

pero esto es imposible, lo que conlleva a una contradicción, de manera que B es número primo y esto implica que p n no es el mayor número primo, por lo tanto, los números primos no son finitos. Entonces se ha demostrado por Reducción al Absurdo que el conjunto de números primos no puede ser finito y por lo tanto es infinito. 11) Demuestre por el método de Reducción al Absurdo que 2 es un número irracional, es decir, que no es racional pues no puede ser expresado como una fracción de números enteros. Solución:

2 es un número racional. Sin pérdida de Suponga que generalidad, se puede suponer que existen enteros m, n primos relativos2, tales que: 2 1

m . n

El teorema fundamental de la aritmética establece que todo número entero positivo es primo o producto de primos. 2 Con primos relativos se implica que no tienen ningún divisor común. Además, es un hecho conocido que todo número racional puede ser expresado como una fracción en la que el numerador y el denominador son números primos relativos.

10

Curso Informática III – 2016

Al elevar al cuadrado ambos lados de la igualdad anterior se obtiene:

 2

2

2

m2 m 2   2 . n n

Al multiplicar ambos lados de la ecuación por n2 se tiene que: 2n 2  m 2

Por lo tanto, 2 divide a m2 y es, por lo tanto, un número par. Sin embargo, esto implica que m también debe ser un número par (la multiplicación de dos números impares es impar). Así, 2 divide también a m. De esto se concluye que existe un entero k, tal que: 4k2 = m2 Al sustituir esto en la igualdad anterior, se deduce que: 2n2 = 4k2 O lo que es equivalente: n2 = 2k2 Por lo anterior, n2 es par, pero, como se había señalado anteriormente, esto implica que n también es par. Esto resultaría en que tanto n como m son pares lo cual contradice la hipótesis planteada al principio en la que se establecía que n y m eran números primos relativos. Se produjo un absurdo, lo cual nos obliga a aceptar que la hipótesis planteada no puede ser verdadera. Por lo tanto 2 no puede ser racional. A estos números se les denomina irracionales. 12) La suma de números naturales puede ser definida en forma recursiva de modo que para cualesquiera enteros n y m: a. b.

sum (n,0) = n sum (n, suc(m)) = suc(sum(n, m))

(Base) (Inducción)

donde suc(n) es el número natural más pequeño mayor que n (su “sucesor”). Al basarse en la definición anterior: 11

Curso Informática III – 2016

a. Dé una definición recursiva de la multiplicación de números enteros: Solución: Defina la multiplicación de esta manera: mult (n, 0) = 0 (Base) mult (n, suc(m)) = sum (n, mult (n, m)) (Inducción) Note que la base comienza desde cero porque estamos trabajando con multiplicación entre números naturales. Además, esta es una de las formas en que se puede definir, pero no la única. b. Utilizando las definiciones recursivas anteriores, demuestre que: i. 3 + 4 = 7 Solución: sum (3, 4) = suc (sum(3,3)) = suc (suc (sum (3,2))) = suc (suc (suc (sum (3,1)))) = suc (suc (suc (suc (sum (3,0))))) = suc (suc (suc (suc (3)))) = suc (suc (suc (4))) = suc (suc (5)) = suc (6) =7

ii. 2 * 3 = 6 Solución: mult (2, 3)

 mult (2, suc(2)) = sum (2, mult (2, 2)) = sum(2, sum(2,mult(2, 1))) = sum(2, sum(2, sum(2,mult(2, 0)))) = sum(2, sum(2, sum(2,0))) = sum(2, sum(2, 2)) = sum(2, suc(sum(2,1)) = sum(2, suc(suc(sum(2,0)))) = sum(2, suc(suc(2))) = sum(2, suc(3)) 12

Curso Informática III – 2016 = sum(2, 4) = suc(sum(2, 3)) = suc(suc(sum(2, 2))) = suc(suc(suc(sum(2, 1)))) = suc(suc(suc(suc(sum(2, 0))))) = suc(suc(suc(suc(2)))) = suc(suc(suc(3))) = suc(suc(4)) = suc(5) =6 c. Escriba un programa en lenguaje Pascal, que implemente las tres operaciones: sucesor, suma y multiplicación. Solución: public class Mayle{ int suc(int m){ return m+1; } int sum(int n, int m){ if (m == 0) { return n; } else { return (suc(sum(n,m-1))); } } int mult(int n, int m){ if (m== 0) { return 0; } else { return (sum(n,sum(n,m-1))); } } void main (String args[]) { System.out.println(“Sumar numeros: “); int result = sum(x,y); System.out.println(“La suma de numeros es :” + result); result = mult(x,y); System.out.println(“La mult de numeros es: “ + result); } }

13) Dé una definición recursiva de las siguientes fórmulas: a. Cn = 7n (1) Solución:   

C0 = 0; Cn+1 = 7(n+1) = 7n + 7 (3) Al utilizar la ecuación (1) y sustituir en la ecuación (3), obtenemos: 13

Curso Informática III – 2016 Cn+1 = Cn + 7. Por lo tanto la definición recursiva será: i. ii.

C0 = 0; Cn+1 = Cn + 7

b. Cn = 3n + 7 (1) Solución:   

C0 = 7; Cn+1 = 3(n+1) + 7= (3n + 7) + 3 (3) Al utilizar la ecuación (1) y sustituir en la ecuación (3), obtenemos: Cn+1 = Cn + 3.

Por lo tanto la definición recursiva será: i. C0 = 7; ii. Cn+1 = Cn + 3 c. Cn = 11n - 8 (1) Solución:   

C0 = –8; Cn+1 = 11(n+1) – 8 = (11n - 8) + 11 (3) Al utilizar la ecuación (1) y sustituir en la ecuación (3), obtenemos: Cn+1 = Cn + 11.

Por lo tanto la definición recursiva será: i. C0 = – 8; ii. Cn+1 = Cn + 11

14

Inducción y recursión UNIDAD I

Agenda 1. 2. 3. 4. 5. 6.

Matemática discreta vs Matemática continua. Principio de inducción matemática (PIM). Definiciones recursivas. Ejemplo 1, Números de Fibonacci. Ejemplo 2, función de Ackerman. Reducción al absurdo.

Parte 1

Matemática Discreta versus Matemática Continua

Matemática Discreta

Algunos temas que abarca la matemática discreta: 1. Teoría de conjuntos. 2. Lógica matemática. 3. Relaciones y clases de equivalencia. 4. Teoría de grafos. 5. Teoría de números. 6. Estructuras lógicas.

Matemática Continua La matemática continua comprende temas como: 1. 2. 3.

Continuidad y límites de funciones. Cálculo diferencial e integral. Ecuaciones diferenciales.

Herramientas para el curso Dada la naturaleza de los temas que serán tratados durante el curso, estas herramientas serán de gran utilidad: 1. 2.

Principio de Inducción Matemática (PIM). Funciones Recursivas.

Parte 2

Principio de Inducción Matemática (PIM)

Ilustración intuitiva sobre el PIM

¿De qué color es la bola en cada una de las urnas?

Principio de inducción matemática (PIM) El PIM se basa en dos ideas subyacentes: 1. 2.

Una afirmación de tipo inductivo. Una comprobación de tipo llamado caso “base”.

Ejemplo: PIM Utilizar PIM para demostrar que la fórmula utilizada para calcular la suma de todos los números naturales iguales o menores a un número dado n, se cumple para todos los números naturales.

n

n(n + 1) Sn = ∑ i = 2 i =0

Ejemplo: PIM Caso Base

Ejemplo: PIM Caso Base Probaremos que la fórmula se cumple para el caso en el que n = 0.

Ejemplo: PIM Caso Base Probaremos que la fórmula se cumple para el caso en el que n = 0. 0

S0 = ∑ i i =0

Ejemplo: PIM Caso Base Probaremos que la fórmula se cumple para el caso en el que n = 0. 0

S0 = ∑ i = 0 i =0

Ejemplo: PIM Caso Base Probaremos que la fórmula se cumple para el caso en el que n = 0. 0

0(0 + 1) S0 = ∑ i = 0 = 2 i =0

Ejemplo: PIM Caso Base Probaremos que la fórmula se cumple para el caso en el que n = 0. 0

S0 = ∑ i = 0 = i =0

0(0 + 1) 2

Por lo tanto la fórmula se cumple para el caso base, cuando n = 0.

Ejemplo: PIM Hipótesis inductiva

Ejemplo: PIM Hipótesis inductiva Para esto asumimos que la fórmula es valida para el caso n. n

n(n + 1) Sn = ∑i = 2 i =0

Ejemplo: PIM Hipótesis inductiva Para esto asumimos que la fórmula es valida para el caso n. n

Tesis

n(n + 1) Sn = ∑ i = 2 i =0

Ahora debemos demostrar que la fórmula anterior conserva el mismo “patrón” en el caso n+1

n +1

¿ S n +1 = ∑ i = i =0

(n + 1)((n + 1) + 1) ? 2

Ejemplo: PIM Demostración

Ejemplo: PIM

n +1

S n +1 = ∑ i i =0

Explicación: Tesis

Ejemplo: PIM n +1

n

i =0

i =0

S n +1 = ∑ i = ∑ i + (n + 1)

Explicación: Propiedad de las sumatorias

Ejemplo: PIM n(n + 1) S n +1 = ∑ i = ∑ i + (n + 1) = + (n + 1) 2 i =0 i =0 n +1

n

Explicación: Por hipótesis inductiva.

Ejemplo: PIM n(n + 1) + (n + 1) 2

Explicación: Ahora desarrollemos el término anterior

Ejemplo: PIM n(n + 1) n(n + 1) + 2(n + 1) + (n + 1) = 2 2

Explicación: Factorización

Ejemplo: PIM ( n(n + 1) n + 1)(n + 2) + (n + 1) = 2 2 Explicación: Mediante factorización

Ejemplo: PIM ( n(n + 1) n + 1)(n + 2 ) (n + 1)(n + 1 + 1) + (n + 1) = = 2 2 2 Explicación: Se puede escribir de esta manera

Ejemplo: PIM ( n(n + 1) n + 1)(n + 2 ) (n + 1)(n + 1 + 1) + (n + 1) = = 2 2 2 Que es lo queríamos demostrar!!

Ejemplo: PIM Por lo tanto mediante PIM hemos demostrado que: n

n(n + 1) Sn = ∑ i = 2 i =0 Para todo número n que pertenezca a los números naturales.

Ejemplo: PIM Por lo tanto mediante PIM hemos demostrado que: n

n(n + 1) Sn = ∑ i = 2 i =0 Para todo número n que pertenezca a los números naturales.

Q Q.E.D.

Parte 3 Definiciones Recursivas

Definiciones Recursivas Para definir recursivamente necesitamos dos casos: 1. Un caso base. 2. Un caso inductivo.

Factorial Un ejemplo simple de recursión, factorial de un número n. Base: 0! = 1 Inducción: n! = n*(n-1)!, para n ≥ 1

Ejemplo de factorial Utilizando al definición recursiva anterior, calculemos el factorial de 4 (4!).

Ejemplo de factorial

Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=?

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=? Explicación: Usamos la definición, caso inductivo.

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=4*(3)! Explicación: Usamos la definición, caso inductivo.

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=4*(3)! Explicación: Aplicamos nuevamente el caso inductivo

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=4*(3)!=4*(3*(2)!) Explicación: Aplicamos nuevamente el caso inductivo

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

4!=4*(3)!=4*(3*(2)!) Explicación: Aplicamos nuevamente el caso inductivo

-> Base -> Inducción

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!)) Explicación: Aplicamos nuevamente el caso inductivo

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!)) Explicación: Continuamos aplicando el caso inductivo.

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*(0)!))

Explicación: Continuamos aplicando el caso inductivo.

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*(0)!))

Explicación: Ahora aplicamos el caso base.

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))

Explicación: Ahora aplicamos el caso base.

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))

4*3*2*1 Explicación: Ahora solo debemos operar.

Ejemplo de factorial Definición recursiva de factorial

0! = 1 n! = n*(n-1)!

-> Base -> Inducción

4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))

4*3*2*1 = 24 Explicación: Ahora solo debemos operar.

Parte 4 Números de Fibonacci

Ejemplo: Números de Fibonacci 1. 2. 3.

F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2

-> Base, parte 1 -> Base, parte 2 -> Inducción

Ejemplo: Números de Fibonacci Veamos algunos ejemplos de la función de Fibonacci: F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13

Ejemplo: Números de Fibonacci Fórmula para calcular fibonacci:

En donde:

Fn =

φ n − φˆ n 5

1+ 5 1− 5 ˆ φ= ; φ= 2 2

Ejemplo: Números de Fibonacci Demostración por medio de PIM: 1. 2. 3.

Caso Base. Hipótesis Inductiva Tesis

Ejemplo: Números de Fibonacci Casos Base

F0 =

φ 0 − φˆ 0 5

Para n = 0

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

Para n = 0 Por definición: F0 = 0

Ejemplo: Números de Fibonacci Casos Base 0

0 ˆ φ −φ 1 −1 F0 = = 5 5

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

1 −1 = =0 5

Ejemplo: Números de Fibonacci Casos Base F0 =

F1 =

φ 0 − φˆ 0 5

φ 1 − φˆ1 5

1−1 = =0 5 Para n = 1

Ejemplo: Números de Fibonacci Casos Base F0 =

F1 =

φ 0 − φˆ 0 5

φ 1 − φˆ1 5

1−1 = =0 5 Para n = 1 Por definición: F1 = 1

Ejemplo: Números de Fibonacci Casos Base F0 =

F1 =

φ 0 − φˆ 0 5

φ 1 − φˆ1 5

1−1 = =0 5

=

φ − φˆ 5

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

1−1 = =0 5

1+ 5 1− 5 − φ 1 − φˆ1 φ − φˆ 2 F1 = = = 2 5 5 5

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

1−1 = =0 5

1+ 5 1− 5 − 1 1 ˆ ˆ 1+ 5 − 1− 5 φ −φ φ −φ 2 2 F1 = = = = 5 5 5 2 5

(

) (

)

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

1−1 = =0 5

1+ 5 1− 5 − 1 1 ˆ ˆ 1+ 5 − 1− 5 2 5 φ −φ φ −φ 2 2 F1 = = = = = 5 5 5 2 5 2 5

(

) (

)

Ejemplo: Números de Fibonacci Casos Base F0 =

φ 0 − φˆ 0 5

1−1 = =0 5

1+ 5 1− 5 − φ 1 − φˆ1 φ − φˆ 1+ 5 − 1− 5 2 2 F1 = = = = =1 5 5 5 2 5

(

) (

)

Ejemplo: Números de Fibonacci Hipótesis Inductivas

Fn =

φ n − φˆ n 5

Fn −1 =

φ n −1 − φˆ n −1 5

Ejemplo: Números de Fibonacci Hipótesis Inductivas

Fn = Tesis:

φ n − φˆ n 5 ¿ Fn +1 =

Fn −1 =

φ n +1 − φˆ n +1 5

φ n −1 − φˆ n −1 5 ?

Ejemplo: Números de Fibonacci Por definición

Fn +1 = Fn + Fn −1

Ejemplo: Números de Fibonacci φ n − φˆ n φ n −1 − φˆ n −1 Fn +1 = + 5 5

Explicación: Por hipótesis inductivas

Ejemplo: Números de Fibonacci φ n − φˆ n + φ n −1 − φˆ n −1 Fn +1 = 5

Explicación: Por común denominador.

Ejemplo: Números de Fibonacci φ n − φ n −1 − (φˆ n + φˆ n −1 ) Fn +1 = 5

Explicación: Reordenando y agrupando.

Ejemplo: Números de Fibonacci φ n −1 (φ + 1) − φˆ n −1 (φˆ + 1) Fn +1 = 5

Explicación: Por factorización.

Ejemplo: Números de Fibonacci φ n −1 (φ + 1) − φˆ n −1 (φˆ + 1) Fn +1 = 5 OJO! 2

1+ 5  1+ 2 5 + 5 3 5 1+ 5  = φ =  = + = +1 = φ +1 4 2 2 2  2  2

Ejemplo: Números de Fibonacci φ n −1 (φ + 1) − φˆ n −1 (φˆ + 1) Fn +1 = 5 OJO! 2

1+ 5  1+ 2 5 + 5 3 5 1+ 5  = φ =  = + = +1 = φ +1 4 2 2 2  2  2

2

1− 5  1− 2 5 + 5 3 5 1− 5 2 ˆ  = φ =  = − = + 1 = φˆ + 1 4 2 2 2  2 

Ejemplo: Números de Fibonacci φ n −1φ 2 − φˆ n −1φˆ 2 Fn +1 = 5

Explicación: Por resultados anteriores

Ejemplo: Números de Fibonacci φ n +1 − φˆ n +1 Fn +1 = 5

Explicación: Por suma de exponentes

Ejemplo: Números de Fibonacci φ n +1 − φˆ n +1 Fn +1 = 5

Q Q.E.D.

Parte 5 Función de Ackerman

Ejemplo: Función de Ackerman 1.

A(0,y) = y+1

2.

A(x,0) = A(x-1,1) -> Inducción, parte 1 A(x,y) = A(x-1,A(x,y-1)) -> Inducción, parte 2

3.

-> Base

Para todo x, y ∈ N

Ejemplo: Función de Ackerman A(2,1)=?

Ejemplo: Función de Ackerman A(2,1)=?

Caso 3: A(x,y) = A(x-1,A(x,y-1))

Ejemplo: Función de Ackerman A(2,1)=?

Caso 3: A(x,y) = A(x-1,A(x,y-1)) x=2 -> x-1 = 1 y=1 -> y = 0

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0))

Caso 3: A(x,y) = A(x-1,A(x,y-1)) x=2 -> x-1 = 1 y=1 -> y = 0

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) = ?

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) = ?

Caso 2: A(x,0) = A(x-1,1)

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) = ?

Caso 2: A(x,0) = A(x-1,1) x=2 -> x-1 = 1

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1)

Caso 2: A(x,0) = A(x-1,1) x=2 -> x-1 = 1

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = ?

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = ?

Caso 3 A(x,y) = A(x-1,A(x,y-1))

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = ?

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = ?

Caso 2: A(x,0) = A(x-1,1)

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = A(0,1)

Caso 2: A(x,0) = A(x-1,1)

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = A(0,1) A(0,1) = ?

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = A(0,1) A(0,1) = ?

Caso 1: A(0,y) = y+1

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = A(0,1) A(0,1) = ?

Caso 1: A(0,y) = y+1 y=1 -> y+1 = 2

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = A(0,1) A(0,1) = 2

Caso 1: A(0,y) = y+1 y=1 -> y+1 = 2

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,A(1,0)) – A(1,0) = 2

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,2)

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,2) – A(0,2) = ?

Caso 1: A(0,y) = y+1

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,2) – A(0,2) = ?

Caso 1: A(0,y) = y+1 y=2 -> y+1 = 2

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = A(0,2) – A(0,2) = 3

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) =A(1,1) A(1,1) = 3

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,A(2,0)) – A(2,0) = 3 Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = ?

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = ?

Caso 3 A(x,y) = A(x-1,A(x,y-1))

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2))

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = ?

Caso 3 A(x,y) = A(x-1,A(x,y-1))

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = A(0,A(1,1))

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = A(0,A(1,1)) – A(1,1) = 3

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = A(0,3)

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = A(0,3) – A(0,3) = ?

Caso 1: A(0,y) = y+1

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = A(0,3) – A(0,3) = 4

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,A(1,2)) A(1,2) = 4

Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,4) Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,4) A(0,4) = ?

Caso 1: A(0,y) = y+1

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = A(0,4) A(0,4) = 5

Ejemplo: Función de Ackerman A(2,1)=A(1,3) – A(1,3) = 5 Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=5 Por resultado anterior

Ejemplo: Función de Ackerman A(2,1)=5

Que es el resultado final…

Función de Ackerman: propiedades Primera Propiedad

Demostración por medio de PIM.

A(1, y ) = y + 2;

para todo entero " y".

Función de Ackerman: propiedades Caso Base

A(1,0) = A(0,1);

por caso 2 : A(x,0 ) = A(x − 1,1)

Función de Ackerman: propiedades Caso Base

A(1,0) = A(0,1); A(0,1) = 1 + 1 = 2;

por caso 2 : A(x,0 ) = A(x − 1,1) por caso 1 : A( 0,y) = y + 1

Función de Ackerman: propiedades Caso Base

A(1,0) = A(0,1); por caso 2 : A(x,0 ) = A(x − 1,1) A(0,1) = 1 + 1 = 2; por caso 1 : A( 0 ,y) = y + 1 Por lo que se cumple el caso base

Función de Ackerman: propiedades Hipótesis Inductiva

A(1, y ) = y + 2 Tesis

¿ A(1, y + 1) = ( y + 1) + 2 ?

Función de Ackerman: propiedades Demostración

Función de Ackerman: propiedades Demostración A(1, y + 1) = A(0, A(1, y ))

caso 3 : A( x,y ) = A(x − 1,A(x,y − 1 ))

Función de Ackerman: propiedades Demostración A(1, y + 1) = A(0, A(1, y )) caso 3 : A(x,y) = A(x − 1,A(x,y − 1 )) A(0, A(1, y )) = A(0, y + 2)) H.I.

Función de Ackerman: propiedades Demostración A(1, y + 1) = A(0, A(1, y ))

caso 3 : A(x,y) = A(x − 1,A(x,y − 1 ))

A(0, A(1, y )) = A(0, y + 2)) H.I. A( 0 ,y + 2 ) = (y + 1 ) + 2 álgebra y caso 1 : A( 0 ,y) = y + 1

Función de Ackerman: propiedades Demostración A(1, y + 1) = A(0, A(1, y ))

caso 3 : A(x,y) = A(x − 1,A(x,y − 1 ))

A(0, A(1, y )) = A(0, y + 2)) H.I.

A( 0 ,y + 2 ) = (y + 1 ) + 2

álgebra y caso 1 : A( 0 ,y) = y + 1

Q Q.E.D.

Función de Ackerman: propiedades Segunda Propiedad

Demostración por medio de PIM.

A(2, y ) = 2 y + 3;

para todo entero " y".

Función de Ackerman: propiedades Caso Base

A(2,0) = A(1,1);

por caso 2 : A(x,0 ) = A(x − 1,1)

Función de Ackerman: propiedades Caso Base

A(2,0) = A(1,1); A(1,1) = 1 + 2 = 3;

por caso 2 : A(x,0 ) = A(x − 1,1) por propiedad 1 : A( 1,y) = y + 2

Por lo que se cumple el caso base

Función de Ackerman: propiedades Hipótesis Inductiva

A(2, y ) = 2 y + 3 Tesis

¿ A(2, y + 1) = 2( y + 1) + 3 ?

Función de Ackerman: propiedades Demostración

Función de Ackerman: propiedades Demostración A(2, y + 1) = A(1, A(2, y ))

caso 3 : A( x,y ) = A(x − 1,A(x,y − 1 ))

Función de Ackerman: propiedades Demostración A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x − 1,A(x,y − 1 )) A(1, A(2, y )) = A(1,2 y + 3)) H.I.

Función de Ackerman: propiedades Demostración A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x − 1,A(x,y − 1 )) A(1, A(2, y )) = A(1,2 y + 3)) H.I.

A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2

por propiedad 1 : A( 1,y) = y + 2

Función de Ackerman: propiedades Demostración A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x − 1,A(x,y − 1 )) A(1, A(2, y )) = A(1,2 y + 3)) H.I.

A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2 ( 2 y + 3 ) + 2 = 2(y + 1 ) + 3

por propiedad 1 : A( 1,y) = y + 2 por álgebra

Función de Ackerman: propiedades Demostración A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x − 1,A(x,y − 1 )) A(1, A(2, y )) = A(1,2 y + 3)) H.I.

A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2 ( 2 y + 3 ) + 2 = 2(y + 1 ) + 3

por propiedad 1 : A( 1,y) = y + 2 por álgebra

Q Q.E.D.

Parte 6 Reducción al Absurdo

Ejemplo: Reducción al absurdo Demostremos que es un número irracional, es decir, que no puede ser representado como una fracción de números enteros, por medio de “Reducción al Absurdo”. 2

Ejemplo: Reducción al absurdo Solución Supongamos que

es un número racional.

2

Ejemplo: Reducción al absurdo Solución Supongamos que 2 es un número racional. Esto significa que existen dos números m y n (primos relativos) tales que:

m 2= n

Ejemplo: Reducción al absurdo

m 2 =  n

( )

2

2

Explicación: Elevemos ambos lados de la igualdad anterior al cuadrado.

Ejemplo: Reducción al absurdo

Explicación: Lo cual podemos escribir

Ejemplo: Reducción al absurdo

2

m 2= 2 n

Explicación: Lo cual podemos escribir

Ejemplo: Reducción al absurdo

Explicación: Multiplicando ambos lados de la ecuación por n2.

Ejemplo: Reducción al absurdo

2

2n = m

2

Explicación: Multiplicando ambos lados de la ecuación por n2.

Ejemplo: Reducción al absurdo 2

2n = m

2

Por lo que m2 es un número par y también m lo es. Recuerde que la multiplicación de dos números impares es siempre impar, por lo que m no podría ser impar sin caer en una contradicción.

Ejemplo: Reducción al absurdo De lo anterior podemos concluir que existe un número k, tal que:

2k = m

Ejemplo: Reducción al absurdo De lo anterior podemos concluir que existe un número k, tal que: 2

4k = m

2 Sustituimos en la ecuación

Ejemplo: Reducción al absurdo De lo anterior podemos concluir que existe un número k, tal que: 2

4k = m

2 Sustituimos en la ecuación

2

2n = m

2

Ejemplo: Reducción al absurdo De lo anterior podemos concluir que existe un número k, tal que: 2

4k = m

2 Sustituimos en la ecuación

2

2n = m

2

Ejemplo: Reducción al absurdo

2

4k = m

2 Y tenemos

2

2n = m

2

Ejemplo: Reducción al absurdo

Y tenemos

2

2n = 4k

2

Ejemplo: Reducción al absurdo Por lo anterior n2 es par y n también lo es. De esto resulta que n y m son pares, lo cual contradice la hipótesis (acerca de que n y m son primos), y así se produce un absurdo, lo cual nos obliga a aceptar que la hipótesis planteada no es verdadera.

Ejemplo: Reducción al absurdo Por lo anterior n2 es par y n también lo es. De esto resulta que n y m son pares, lo cual contradice la hipótesis (acerca de que n y m son primos), y así se produce un absurdo, lo cual nos obliga a aceptar que la hipótesis planteada no es verdadera.

Q Q.E.D.

Ejercicio 1 Sea Fn el n-ésimo número de Fibonacci. Usando el PIM demuestre la validez de la siguiente proposición: n

1+ ∑ i =1

F =F 2i

2 n +1

, ∀n ≥ 1

Ejercicio 1 Caso Base 1

¿1 + ∑ i =1

F

2i

=

F

3

? Para n = 1

1

Por una parte:

1 + ∑ F2i = 1 + F2 = 1 + 1 = 2 i =1

Por otra parte:

F3 = 2

Con lo que se comprueba el caso base.

Ejercicio 1 Hipótesis Inductiva k

1 + ∑ F2 i = F2 k +1 , k ∈ N i =1

Tesis k +1

¿1 + ∑ F2 i = F2 ( k +1) +1 ? i =1

Ejercicio 1 k +1

Tesis

¿1 + ∑ F2 i = F2 ( k +1) +1 ? i =1

Demostración k +1

1+ ∑ i =1

k

F

2i

= 1+ (∑ i =1

k +1

F

2i

+

∑ F

2i

)

i = k +1

Explicación: por propiedades de sumatorias

Ejercicio 1 k +1

Tesis

¿1 + ∑ F2 i = F2 ( k +1) +1 ? i =1

Demostración k +1

1+ ∑ i =1

k

F

2i

= (1 + ∑ i =1

k +1

F

2i

)+

∑ F

2i

i = k +1

Explicación: por asociatividad de la suma

Ejercicio 1 k +1

Tesis

¿1 + ∑ F2 i = F2 ( k +1) +1 ? i =1

Demostración k +1

1+ ∑ i =1

k +1

F

2i

=

F

2 k +1

+

∑ F

2i

i = k +1

Explicación: sustituyendo Hipótesis Inductiva

Ejercicio 1 Tesis

k +1

¿1 + ∑ F2 i = F2 ( k +1) +1 ? i =1

Demostración

F =F =F =F =

2 k +1

+ F 2 ( k +1)

2 k +1

+ F 2k +2

2 k +3 2 ( k +1) +1

Explicación: por definición recursiva de los números de Fibonacci

Q Q.E.D.

Informática III Lenguajes

Agenda 1. Lenguajes, un poco de historia. 2. Alfabetos. 3. Cuerdas. 4. Operaciones entre cuerdas. 5. Lenguajes.

6. Ejemplos.

Lenguajes Un poco de historia

Un poco de historia  





Inicios de la computación: conexión de alambres Salto cuántico con el concepto de programa almacenado, sin embargo los lenguajes eran de “bajo nivel” Desarrollo de lenguajes de “alto nivel” unido a la formalización de la Teoría de Lenguajes Bases de la Teoría de Lenguajes: Teorías de Matemática Discreta y Lógica Matemática

Un poco de historia

 Paralelamente se construyeron “máquinas” que interpretaran estos lenguajes y los tradujeran a lenguaje máquina.  Este es un de los AVANCES más importantes en la computación

Elementos de la teoría de lenguajes  Los lenguajes están presentes cuando se necesita:  Comunicación entre agentes  Codificación de información  Elementos básicos de la teoría de lenguajes: • Un lenguaje • Una “máquina” para leer y analizar el lenguaje

Correspondencia entre “máquinas” y lenguajes LENGUAJES Lenguajes de alto nivel LCL, Lenguajes de Contexto Libre Lenguajes de bajo nivel LR, Lenguajes regulares

“MÁQUINAS” (Compiladores) Máquinas de Turing APD, Autómata “Push Down” AFD, Autómata finito determinístico

PROPÓSITOS (Lenguaje máquina)

¿Qué es un lenguaje? 

Todo lenguaje posee dos dimensiones 

Sintaxis



Semántica

Alfabetos

Alfabeto  Normalmente identificado por Σ  Conjunto finito y no vacío de símbolos  Por lo general se representan por letras minúsculas  Ej. alfabetos: abecedario, alfabeto binario

Cuerdas

Cuerdas  Dado un alfabeto Σ, una cuerda se define como una secuencia de letras sobre el alfabeto  Su representación usual son las últimas letras del abecedario: v, w, x, y, z  Conocidas también como palabras, oraciones, “strings”  Se postula la existencia de la cuerda nula λ

Cuerdas  Dado un alfabeto Σ, se definen dos conjuntos de cuerdas:  El conjunto clausura de Kleene, Σ * – Σ* = Universo de cuerdas o todas las cuerdas de longitud arbitraria – Σ* incluye la cuerda nula

 Y el conjunto Σ + = Σ * - { λ }

Operaciones con cuerdas

Concatenación 

La concatenación de dos o más cuerdas se define como la cuerda formada yuxtaponiéndolas, en orden indicado.



Puede considerarse como una operación binaria sobre Σ*, asociativa, no conmutativa y con elemento neutro la cuerda nula



Lo anterior constituye un semi-grupo también llamado monoide.

Ejemplo: Concatenación •Si w = a1a2…an; y v = b1b2…bm

wv sería: a1a2…anb1b2…bm, mientras que vw sería: b1b2…bma1a2…an

•No es conmutativa - Sí es asociativa •Para toda cuerda w: wλ = λw = w

Imagen inversa  La imagen inversa de una cuerda w, wR se define como:

w  *, a   λR = λ (wa)R = awR

caso base caso recursivo

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería:

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R = ac(ab)R

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R = ac(ab)R = acb(a)R

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R = ac(ab)R = acb(a)R = acba(λ)R

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R = ac(ab)R = acb(a)R = acba(λ)R = acbaλ

Ejemplo: Imagen inversa  Supongan la cuerda w = abca, su imagen inversa wR según la definición recursiva sería: wR = (abca)R = a(abc)R = ac(ab)R = acb(a)R = acba(λ)R = acbaλ wR = acba

Longitud o largo de una cuerda  Denotado por |w| y es el número de letras que w contiene.  Se define recursivamente:

w  *, a    |λ| = 0  |aw| = |w| +1

caso base caso recursivo

Ejemplo: Longitud de una cuerda  Supongan la cuerda w = abca, calculemos su largo, |w|, mediante la definición recursiva. |w| = |abca| = |bca| + 1

Ejemplo: Longitud de una cuerda  Supongan la cuerda w = abca, calculemos su largo, |w|, mediante la definición recursiva. |w| = |abca| = |bca| + 1 = |ca| + 1 + 1

Ejemplo: Longitud de una cuerda  Supongan la cuerda w = abca, calculemos su largo, |w|, mediante la definición recursiva. |w| = |abca| = |bca| + 1 = |ca| + 1 + 1 = |a| + 2 + 1

Ejemplo: Longitud de una cuerda  Supongan la cuerda w = abca, calculemos su largo, |w|, mediante la definición recursiva. |w| = |abca| = |bca| + 1 = |ca| + 1 + 1 = |a| + 2 + 1 = |λ| + 3 + 1

Ejemplo: Longitud de una cuerda  Supongan la cuerda w = abca, calculemos su largo, |w|, mediante la definición recursiva. |w| = |abca| = |bca| + 1 = |ca| + 1 + 1 = |a| + 2 + 1 = |λ| + 3 + 1 =4+0=4

Palíndromos 

Son cuerdas que se leen igual hacia adelante como hacia atrás, es decir: R = w , w es palíndromo ssi w w   *



Existen palíndromos de longitud par e impar

Ejemplos de palíndromos 

Considere el alfabeto Σ = {a,b} y la cuerda w = aabbaa wR = (aabbaa)R = aabbaa = w



La cuerda nula λ también es un palíndromo



“RADAR” construida sobre el abecedario también es un palíndromo

Potencia Definición recursiva:

w   *  w0 = λ  wn+1 = wnw

caso base caso recursivo

Ejemplo: Potencia 

Suponga la cuerda w = acb, calculemos algunas potencias.

w0 = λ

Ejemplo: Potencia  Suponga la cuerda w = acb, calculemos algunas potencias. w0 = λ w1 = acb

Ejemplo: Potencia  Suponga la cuerda w = acb, calculemos algunas potencias. w0 = λ w1 = acb w2 = acbacb

Ejemplo: Potencia  Suponga la cuerda w = acb, calculemos algunas potencias. w0 = λ w1 = acb w2 = acbacb w3 = acbacbacb

Prefijos  Sea w = abcba, veamos algunos ejemplos de prefijos de w • a • ab • abc • abcb • w • λ

Prefijos propios  Sea w = abcba, veamos algunos ejemplos de prefijos de w

• • • •

a ab abc abcb

Sufijos  Sea w = abcba, veamos algunos ejemplos de sufijos de w. • • • • •

a ba cba bcba abcba

• λ

Sufijos propios  Sea w = abcba, veamos algunos ejemplos de sufijos propios de w.    

a ba cba bcba

Subcuerda  Sea w = abcba, veamos algunos ejemplos de subcuerdas de w. − abc (subcuerda propia) − bcb (subcuerda propia) − bcba (subcuerda propia) −λ (no es subcuerda propia) −w (no es subcuerda propia)

Subsecuencia  Sea w = a1b2cb4a5 algunas subsecuencias de w: ─ cb4 ─ a1b4 ─ a1a5 ─ b2a5 ─λ ─w

Lenguajes

Definición Formal de un Lenguaje 

Un lenguaje es un subconjunto de la clausura de Kleene Σ*

Ejemplo de lenguajes

 Ø el conjunto vacío es un lenguaje del alfabeto  Σ*, la clausura de Kleene es un lenguaje

 Σ, el alfabeto mismo es también un lenguaje  { λ } es un lenguaje cuyo único elemento es la cuerda nula

Características 

Los lenguajes pueden ser finitos o infinitos



Pueden definirse en forma enumerativa, descriptiva o mediante métodos que se explicarán más adelante

Ejemplos

 Si Σ={a, b}, entonces: ─ L = {aba, bbbaaa, aaa} es un lenguaje finito definido en forma enumerativa ─ L = {anbn; donde n es un número natural} es un lenguaje infinito definido en forma descriptiva ─ L = {w ε Σ* tal que |w| = 5}, es el lenguaje de todas las cuerdas cuya longitud es 5

Unión entre lenguajes

 L U M (también denotado por L+M), es el lenguaje formado por cuerdas que pertenecen al lenguaje L o bien al lenguaje M

Ejemplo de Unión entre lenguajes  Si L={A, B, C, …, Z, a, b, c, …, z} y D={0,1,…,9} ─ L+D es el conjunto de palabras de longitud 1 (letras o dígitos) como: ─ A, z, C, b, 9, 8

Notación

 En notación de conjuntos:



L  M  w  * | w  L  w  M



Concatenación entre lenguajes

 Escrita por LM, es el lenguaje constituido por cuerdas que se forman concatenando una cuerda del lenguaje L con una cuerda del lenguaje M (en ese orden)

Ejemplo de concatenación entre lenguajes  Si L={A, B, C, …, Z, a, b, c, …, z} y D={0,1,…,9} ─ LD es el conjunto de cuerdas que consisten en un letra seguida de un dígito. Ejs: ─ A1, B9, Z3, z9, b5

Notación

 En notación de conjuntos:





LM  w   | x  L   y  M   w  xy *

Potencia de un lenguaje

 Si n es un número natural, Ln es el lenguaje formado por L concatenado consigo mismo n veces  Si n es cero, Ln = {λ}

Ejemplo de potencia de un lenguaje

 Si L={A, B, C, …, Z, a, b, c, …, z} y D={0,1,…,9} ─ L4 es el conjunto de palabras que contienen exactamente cuatro letras. Ejs: ─ AazZ, aaaa, Czwb, Hola

Notación

 En notación de conjuntos:



Ln  w  * | w1 , w2, ..., wn  L  wn  w1w2 ...wn



Ejemplo de Clausura de Kleene de un lenguaje  Si L={A, B, C, …, Z, a, b, c, …, z}

─ L* es el conjunto de todas las palabras de longitud arbitraria formadas únicamente por letras, incluyendo también la cuerda nula. Ejs: λ, A, a, z, da, zz, AKD, EIEIEIEI

Clausura de Klenee de un lenguaje

 Se denota por L* 

L*   Li i 0

Clausura positiva de un lenguaje

 La clausura positiva L* se define como la clausura de Kleene anterior, pero excluyendo la cuerda nula

L  L*   

Otros ejemplos

 Si L={A, B, C, …, Z, a, b, c, …, z} y D={0,1,…,9} ─ L(L+D)* es el conjunto de palabras que empiezan con una letra seguida de cero o más letras o dígitos. Ejs: A, z, AbdZ45, Dw383, t99595 ─ D+ es el conjunto de palabras con uno o más dígitos. Ejs: 0, 1000, 494949

EJERCICIOS

Ejercicio 1

 Utilizando

el

PIM

demuestre

que:

 El número de subsecuencias de una cuerda w de longitud n es 2n.

Ejercicio 2  

Si L={A, B, C, …, Z, a, b, c, …, z} y D={0,1,…,9} Determine si las siguientes cuerdas pertenecen a (L*D*  LD)+   

a123aab  3159abdd

Ejercicio 3, parte I 

Dado el alfabeto  = {a, b}, una cuerda de Finobacci se define recursivamente como:   



f1 = a; f2 = b fn = fn-1fn-2, para todo natural n3

Dada la definición anterior: 

Liste las 9 primeras cuerdas Fibonacci

Ejercicio 3, parte II 

La longitud de las cuerdas de Fibonacci tienen relación directa con los números de Fibonacci, de la siguiente manera:





fn= Fn siendo Fn el enésimo número de Fibonacci.



Demuestre esta afirmación utilizando el PIM.

Ejercicio 4 

Usando el PIM demuestre que: |wn| = n|w|



Para toda cuerda w y para todo número natural n

Ejercicio 5 

Demuestre por Inducción Matemática que: w, x*, wx=w+x