Taller1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4 style=\"text-align: right;\">Yeliana Andrea Torres Medina - 28791125</h4>\n",
    "<h1 style=\"text-align: center;\">Taller 1 - Introducción a Teoría de la computación</h1>\n",
    "<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>1. Considere el problema de determinar si un código corresponde a un ISBN de 13 dígitos. Construya un autómata finito determinístico para identificar si un código es válido o no. Especifique formalmente el autómata, dibuje el diagrama y la tabla de transiciones. Implemente el autómata correspondiente utilizado una clase autómata. (4 Puntos)</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>2. Construya un autómata finito determinístico sobre el alfabeto el cual acepte todas las cadenas que contengan NO más de dos ocurrencias consecutivas de la misma entrada (Por ejemplo, abba es aceptada y abbba no es aceptada). Especifique formalmente el autómata, dibuje el diagrama y la tabla de transiciones. (2 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sea $M$ un DFA, lo definimos como: $M=(Q, \\sum, \\delta, q0, F)$ donde:<br><br>\n",
    "$Q=\\{q1, q2, q3, q4, q5\\}$ $\\sum=\\{0, 1\\}$ $F=\\{q0, q1, q2, q3, q4\\}$<br><br>\n",
    "Tabla de transiciones:\n",
    "<table style=\"float: left;\">\n",
    "  <tr>\n",
    "    <th> </th>\n",
    "    <th>0</th>\n",
    "    <th>1</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q0</th>\n",
    "    <td>q1</td>\n",
    "    <td>q2</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q1</th>\n",
    "    <td>q3</td>\n",
    "    <td>q2</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q2</th>\n",
    "    <td>q1</td>\n",
    "    <td>q4</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q3</th>\n",
    "    <td>q5</td>\n",
    "    <td>q2</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q4</th>\n",
    "    <td>q5</td>\n",
    "    <td>q1</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <th>q5</th>\n",
    "    <td>q5</td>\n",
    "    <td>q5</td>\n",
    "  </tr>\n",
    "</table>\n",
    "<img src=\"Punto2.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>3. Dado un autómata finito determinístico $M$, construya un nuevo autómata finito determinístico $M'$ con el mismo alfabeto de entrada y con la propiedad de que para todos los $u \\in \\sum*$, $u$ es aceptado por $M'$ si y solo si $u$ NO es aceptado por $M$. (2 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Sea $M=(Q,\\sum,\\delta,q0,F)$ un DFA cuyo lenguaje es $L=\\{u$ $|$ $\\widehat{\\delta}(u)\\in F\\}$<br>\n",
    "y $M'=(Q,\\sum,\\delta,q0,F')$ un DFA cuyo lenguaje es $L=\\{u$ $|$ $\\widehat{\\delta}(u)\\in F'\\}$, tal que $F'=Q-F$.<br><br>\n",
    "Es decir, el conjunto de estados finales de $M'$ se conforma de todos aquellos estados que no sean finales en $M$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>4. Dados dos autómatas finitos determinísticos $M_1$ y $M_2$ con el mismo alfabeto de entrada, construya un tercer autómata finito determinístico ($M$) con la propiedad que $u \\in \\sum*$ es aceptado por $M$ sí y solo si es aceptado por ambos $M_1$ y $M_2$. (2 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Sean $M_1=(Q_1,\\sum,\\delta_1,r0,F_1)$ un DFA cuyo lenguaje es $L=\\{u$ $|$ $\\widehat{\\delta}(u)\\in F_2\\}$<br>\n",
    "y $M_2=(Q_2,\\sum,\\delta_2,s0,F_2)$ un DFA cuyo lenguaje es $L=\\{u$ $|$ $\\widehat{\\delta}(u)\\in F_2\\}$<br>\n",
    "Obtenemos un DFA $M=(Q,\\sum,\\delta,(r0,s0),F)$ cuyo lenguaje es $L=\\{u$ $|$ $\\widehat{\\delta}(u)\\in F_1$ y $\\widehat{\\delta}(u)\\in F_2\\}$ donde:<br><br>\n",
    "$Q=Q_1XQ_2=\\{(r,s)$ | $r\\in Q_1$ y $s\\in Q_2\\}$<br>\n",
    "$F=\\{(r,s)\\in Q$ | $r\\in F_1$ y $s\\in F_2\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>5. Construya un autómata finito no determinístico que permita aceptar palabras sobre el alfabeto ${1, 2, 3}$ tal que el último símbolo aparezca al menos dos veces, pero sin la intervención de un símbolo superior en la mitad. Por ejemplo, 11, 2112, 123113, 3212113, etc. (2 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"Punto5.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>6. Escriba un autómata que reconozca todos las cadenas sobre ${0, 1}$ que representan números binarios que son divisibles por $5$. Por ejemplo, 0, 101, 1010, 1111, 11001. (3 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"Punto6.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>7. Un sistema de transiciones es una generalización de los autómata finitos no determinísticos con $\\epsilon$-transiciones, en la cual se admiten transiciones adicionales con palabras de longitud mayor o igual a 1. Dé una definición formal de los sistemas de transiciones, y pruebe que los lenguajes aceptados por un sistema de transiciones son aceptados por un DFA. (3 Puntos)</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>8. Pruebe o desapruebe la siguiente afirmación: El siguiente autómata acepta el lenguaje $L=\\{w$ $|$ $w=a^ib^j$ $o$ $w=a^ic^j, i≥1, j≥1\\}$ (2 Puntos)</p>\n",
    "<img src=\"Punto7.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La afirmación no es cierta dado que, como no acepta palabras que tengan cierta cantidad de a's y en seguida cierta cantidad de c's, se inclumple la segunda condición donde $w=a^ib^j$. <br><br>\n",
    "Por ejemplo: Sabiendo que $A=(Q,\\sum,\\delta,q0,F)$ con $Q=\\{1,2,3,4,5,6\\}$ y $F=\\{3\\}$ <br>\n",
    "$ac$ --> $\\widehat{\\delta}(ac)=5$ y $5\\not\\in F$. Luego no se cumple para todas las palabras $w=a^ib^j$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>9. Respecto al uso de autómatas (máquinas de estado finito) para el diseño de personajes de video juegos (4 Puntos):\n",
    "    <ol>\n",
    "        <li>¿Cúales son las ventajas del uso de la abstracción de maquinas de estado frente a una implementación utlizando condicionales?</li>\n",
    "        <p>El uso de autómatas en casi todos los casos, agiliza y hace más breve el proceso de definir las acciones que realiza un personaje determinado. A diferencia de los condicionales, que incluyen un solo caso por cada uno, los autómatas usan la recursión para hacer muchos caminos con pocos estados.</p><br>\n",
    "        <li>¿Cómo se utilizan los autómatas en el diseño de personajes para video juegos?</li>\n",
    "        <p>La forma más obvia para modelar el comportamiento de un personaje de videojuego con un autómata, es un grafo donde los caminos o etiquetas estén definidas por comandos (botones) que da el usuario (jugador) y los estados son acciones que realiza el personaje. Por ejemplo, se modela la secuencia de botones, uno después de otro, que hay que presionar para lograr que el personaje arroje un poder especial, lo cual ocurre si se llega a un estado final.</p><br>\n",
    "        <li>Seleccione su personaje de video juegos parecido, especifique formalmente su autómata, encuentre el lenguaje aceptado por el automata, pruebe que el lenguaje propuesto efectivamente es aceptado por el autómata. Seleccione un personaje con al menos cuatro estados y 4 acciones.</li>\n",
    "        <p>Se usará el personaje principal del juego Kirby Adventures para este ejercicio. Definimos el autómata como: $A=(Q,\\sum,\\delta,q0,F)$</p>\n",
    "        <img src=\"Punto9.png\"/>\n",
    "        <p>Los estados significan lo siguiente: </p>\n",
    "        <ul>\n",
    "            <li>1 - El personaje se encuentra en movimiento</li>\n",
    "            <li>2 - El personaje ha tragado a un enemigo</li>\n",
    "            <li>3 - El personaje salta</li>\n",
    "            <li>4 - El personaje adquiere el poder del enemigo que tragó</li>\n",
    "            <li>5 - El personaje, que ha adquirido un poder, puede atacar usando el botón A</li>\n",
    "        </ul>\n",
    "    </ol>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}