Autómatas, gramáticas y lenguajes - Daniela Morales

Vista previa del material en texto

Autómatas, gramáticas y lenguajes
¿Qué es un retraso unitario de tiempo?
Es aquel que acepta como entrada un bit xt en el tiempo t y produce xt−1, el bit recibido como entrada en el tiempo t – 1. El retraso unitario de tiempo se dibuja como
se muestra en la figura:
Un sumador en serie acepta como entrada dos números binarios
y produce la suma zN+1zN · · · z0 de x y y. Los números x y y se introducen de manera secuencial por pares, x0, y0; . . . ; xN, yN; 0, 0. Se produce la suma z0, z1, . . . , zN+1.
¿Qué es un sumador en serie?
Muestra el comportamiento dependiente del tiempo de un sistema de información. Representa los estados que puede tomar un componente o un sistema y muestra los eventos que implican el cambio de un estado a otro.
¿Qué es un diagrama de transición?
¿Qué es un flip-flop SR?
Un flip-flop es un componente básico de los circuitos digitales puesto que sirve como celda
de memoria de un bit. El flip-flop SR (o flip-flop set-reset) se define mediante la tabla
El flip-flop SR “recuerda” si el último valor de S o R era 1. (Si Q = 1, el último valor de S era 1; si Q = 0, el último valor de R era 1). Se puede modelar el flip-flop SR como una máquina de estado finito definiendo dos estados: “el último valor de S era 1” o “el último valor de R era 1”Se define la entrada como los nuevos valores de S y R; la notación sr significa que S = s y R = r. Se define Q como la salida. Se ha designado de manera arbitraria el estado inicial como “S era igual a 1”
Un autómata de estado finito A = (I, O, S, f, g, σ0) es una máquina de estado finito en la que el conjunto de símbolos de salida es {0, 1} y donde el estado actual determina la última salida. Aquellos estados para los que la última salida fue 1 se llaman estados de aceptación.
Defina autómata de estado finito.
¿Qué significa para una cadena ser aceptada por un autómata de
estado finito?
Si una cadena se alimenta a un autómata de estado finito, terminará ya sea en un estado
de aceptación o en un estado de no aceptación. Este estado final determina si el autómata
de estado finito acepta la cadena.
¿Qué son autómatas de estado finito equivalentes?
Si dos autómatas de estado finito aceptan precisamente las mismas cadenas, se dice que los autómatas son equivalentes.
Tabla de transición de datos.
Es la manera más cercana de representar los autómatas, consta de de filas que representan los estados y las columnas que representan los símbolos de entrada.
Referencias
Lipschutz, S., & Lipson, M. (2021). Schaum’s Outline of Discrete Mathematics, Fourth Edition (4th ed.). McGraw-Hill Companies.