A_TeoriaComputacionLIBRO 1 l

PROPÓSITO DE LA UNIDAD DE APRENDIZAJE

“Generar la habilidad matemática en el manejo de autómatas finitos y gramáticas como herramientas
para el desarrollo de software de base mediante la práctica dirigida por el profesor”. (Según programa
sintético de la unidad de aprendizaje: Teoría de la computación).
UNIDAD I
UNIDAD DE COMPETENCIA
“Explica los conceptos relacionados con Autómatas Finitos(AF), a través de dinámicas expositivas, aplicables
a los métodos de transformación y en la industria de automatismos secuenciales”.
“MARCO CONCEPTUAL”
TEMAS:
1.1 Sistemas formales
1.2 Teoría de conjuntos
1.3 Conceptos de lenguajes
1.4 Conceptos de expresiones regulares
1.5 Conceptos de autómatas finitos
1.6 Temas complementarios
DESARROLLO:
1.1 Sistemas formales
Recordemos que, de forma muysimplificada, un sistema es un conjunto de elementos
heterogéneos (diferentes) que interactúan entre sí para lograr un fin común. El sistema formal no es una
excepción, solo que los elementos que integran a un sistema formal son de tipo abstracto o
representativo del comportamiento de un sistema “real”, también se puede decir que en sistema formal
se tiene la abstracción, esto es, se utilizan símbolos paracada uno de los elementos del sistema que se
pretende representar y así analizar su comportamiento.

Lamentablemente no es fácil formalizar un sistema del mundo real, pero recordemos que para un
innovador no existe la palabra imposible y, si logramos hacer un modelo funcional en el papel, lo
podemos llevar a la solución real de muchos problemas que al simplificarlos y esquematizarlos ya
hacemosfactible su materialización en términos de crear nuevas tecnologías y compartir su lógica o
comportamiento para construir muchos otros servomecanismos o artefactos.
Todo esto puede ser confuso, mejor es describir un sistema real, esto es, un sistema que tiene un
conjunto de elementos como lo puede ser el sistema “mecánico” de un depósito de agua que se llena de
forma autónoma, se vacía mediante unmecanismo manual como es jalar una palanca, esto es, mediante
una llave especial que se activa en base al nivel del agua que se retiene en el contenedor o depósito de
agua.
EJERCICIO 1. Desarrolle un diagrama de flujo en el cual se representen tres variables: E, N y S, cada
una con la posibilidad de contener sólo dos valores (binarias): 0 y 1, mismos que permiten abstraer al
sistema manualmecánico del depósito de agua de nuestro inodoro, vamos a aprovechar tres de sus
elementos para hacer una abstracción muy simple, utilizando también tres letras mayúsculas para los
elementos que serán representados (simbolizados) con las letras mayúsculas:
E => representa la válvula de ingreso (entrada)
N => representa la cazoleta de nivel (flotador o proceso)
S => representa la válvula de descarga(salida)
Cada una de estas letras mayúsculas representan una variable binaria dentro de nuestra abstracción, esto
es, si la variable E tiene el valor de 0 (cero), significa que el agua no entra por la válvula de ingreso, si
toma el valor de 1 (uno), esto significa que el agua entra por la válvula de ingreso. Los valores binarios
son para cada una de las tres variables que tiene representaciones talescomo:
E Si es 0 =>el agua no entra.

Si es 1 => la válvula se abre y entra el agua.

N Si es 0 => no hay agua, está vacío el contenedor. Si es 1 => está lleno de agua el contenedor.
S Si es 0 => No hay salida de agua. Si es 1 => Sale el agua y abre válvula de ingreso E.

Este ejercicio consiste en relacionar las tres variables con sus dos valores cada una y mostrarlo mediante
un diagrama de flujoque contiene algunos de los símbolos, por ejemplo:
ENTRADA

DECISION:

PROCESO

INICIO O FIN

SALIDA

N

EXISTE UNA SOLUCIÓN PROPUESTA DE ESTE EJERCICIO AL FINAL DE ESTE
MATERIAL, EN LA UNIDAD TEMATICA CORRESPONDIENTE.
Algunos ejemplos de sistemas formales son aquellos en los que su modelado lo integran elementos
representativos o simbólicos, tales como: expresiones regulares; elementos...