Autómatas

Autómatas

Un autómata es un modelo computacional que consiste en un conjunto de estados bien definidos: un estado inicial un alfabeto de entrada y una función de transición. Esta definición se iguala a la de un autómata finito o máquina de estados.

En un autómata un estado es la representación de su condición en un instante dado. Un autómata comienza en el estado inicial con un conjunto de símbolos; su paso de un estado a otro se efectúa a través de la función de transición, la cual, partiendo de su estado actual y un conjunto de símbolos de entrada, lo lleva al nuevo estado.

Demostraciones deductivas: el método de deductivos basa en ir encadenando estados que se suponen verdaderos de manera tal que se obtienen de nuevos estados; es decir, es aquel que combina principios necesarios y simples (axiomas postulados, teoremas definiciones, etc.) para deducir nuevas estados. Por ejemplo: a) Todo cuadrado es figura geométrica, toda figura geométrica es un plano, todo cuadrado es un plano. B) Toda arquitectura es un estudio, todo el estudio es una profesión, toda arquitectura es una profesión.

Demostraciones inductivas: Se basa en estados iniciales reales y verdaderos que apoyan la función de transición y que nos llevan a otro estado nuevo verdadero. Ejemplo: Demostrar que si n es un número entero positivo, entonces 4n+15n−1 es múltiplo de 9.

Solución: Si n=1 entonces: 4(1)+15(1)−1=18 y como 9 es múltiplo de 18 se tiene que la afirmación es cierta.

Demostraciones de la conversión contradictoria: En una proposición demostrar “si H, entonces C” mediante la demostración de la proposición equivalente “si no C, entonces no H”. Esta última recibe el nombre de conversión contradictoria de la primera. Ejemplo: Si a todos les gusta nadar, entonces todos saben nadar. Conversión contradictoria: Si no sabes nadar, no te gusta la natación.

Demostración por reducción al absurdo: La Reducción al Absurdo es uno de los métodos más usados para hacer demostraciones matemáticas. La idea es suponer que la proposición que queremos demostrar es falsa, y a partir de esta suposición, usando deducciones matemáticas, llegar a una contradicción o algo absurdo, lo cual implica que nuestra proposición es necesariamente cierta. Ejemplo:

Demuestre que si m y n son enteros tales que n + n2 + n3 = m + m2, entonces n es par

Solución. Supongamos que n es impar. A partir de esto debemos conseguir una contradicción. Como n es impar, entonces n2 y n3 son ambos impares, de donde n + n2 + n3 es impar (ya que es la suma de tres impares). Entonces, como m + m2 = n + n2 + n3, se tiene que m + m2 es impar. Sin embargo, m+m2 es siempre par (ya que m+m2 = m (m+1) y necesariamente alguno de los números m ó m+1 es par). Hemos llegado a una contradicción. De allí se tiene que n es par, que es lo que queríamos demostrar.

Contraejemplos: Un contraejemplo

...