TP Discreta



Universidad Abierta
Interamericana







Asignatura: Matemática Discreta y Autómatas Finitos
Año: 2014
Turno: Noche
Integrantes: Zeballos, Sebastián Jesús
Responder
1. ¿Qué es una cadena?
Una cadena (o palabra) es una secuencia finita de símbolos que pertenecen a V y una cadena vacía (o palabra vacía), denotada por l es la cadena sin símbolos.
2. ¿Qué es un lenguaje?
Los lenguajes sepueden especificar de varias formas. Una de ellas es consiste en enumerar todas las palabras que conforman el lenguaje, dar algunos criterios que una palabra debe satisfacer para pertenecer al lenguaje. Otro modo importante de definir un lenguaje es utilizando una gramática.
3. ¿Qué es una gramática?
Una gramática proporciona un conjunto de símbolos de varios tipos y un conjunto de reglas paraconstruir palabras. Concretamente, una gramática consta de un vocabulario o alfabeto V, que es el conjunto de símbolos usados para obtener los elementos de un lenguaje.
Por definición:
Una gramática es un conjunto de reglas de formación de cadenas válidas en un lenguaje.
Una gramática con estructura de frases G = (V, T, S, P) consiste en:
Un vocabulario V
Un subconjunto T de V formado por loselementos terminales
Un símbolo inicial S de V - T
Un conjunto P de producciones.

4. ¿Cuándo una gramática es libre de contexto?
Una gramática de tipo 2 sólo puede tener producciones de la forma w1 ® w2, donde w1 es un único símbolo no terminal. La gramática de tipo 2 también se llama independiente del contexto o gramática libre de contexto, puesto que un símbolo no terminal que está en el ladoizquierdo de una producción puede ser remplazado en una cadena siempre que aparezca independientemente de lo que figure en la cadena.
5. ¿Cuándo un lenguaje es sensible al contexto?
Cuando se tiene una producción de la forma lw1r® lw2r (pero no de la forma w1 ® w2), la gramática se denomina de tipo 1, sensible al contexto o dependiente del contexto.
Un lenguaje generado por una gramática de tipo 1 sellama lenguaje sensible al contexto o dependiente del contexto.

6. ¿Cuándo un lenguaje es regular?
Una gramática de tipo 3, también llamados regulares, sólo puede tener producciones de la forma w1 ® w2, con w1 = A, y bien w2 = aB o bien w2 = a, siendo A y B símbolos no terminales y a un símbolo terminal o con w1 = A y w1 = l. Esta gramática es la que genera los lenguajes denominadosregulares.


7. ¿Cuándo un circuito es secuencial?
En los sistemas secuenciales, los valores de las salidas, en un momento dado, no dependen exclusivamente de los valores de las entradas en dicho momento, sino también dependen del estado anterior o estado interno.

8. ¿Qué es el diagrama de transición de una máquina de estado finito?
Es un grafo dirigido con aristas etiquetadas. En este diagrama, cadaestado se representa por un círculo. Los arcos se etiquetan con el par formado por la entrada y la salida de cada transición.

9. ¿Cuándo una cadena es aceptada por un autómata de estado finito?
Un autómata finito M = {S, I, f, s0, F} consiste en un conjunto finito de estados S; un alfabeto fuente I, que contiene los símbolos de entrada; una función de transición f, que asigna a cada par deestado y entrada el estado siguiente (esto es, f: S x I® S); un estado inicial s0 y un subconjunto F de S de estados de salida.
Se dice que una cadena x es aceptada o reconocida por el autómata M = {S, I, f, s0, F} si transforma el estado inicial s0 en algún estado final, esto es f (s0, x) es un estado de F.

10. ¿Qué es un autómata de estado finito no determinista?
Un autómata finito nodeterminista M = {S, I, f, s0, F} consiste en un conjunto finito de estados S; un alfabeto fuente I, que contiene los símbolos de entrada; una función de transición f, que asigna un conjunto de estados a cada par de estado y entrada (esto es, f: S x I® P(S)); un estado inicial s0 y un subconjunto F de S de estados de salida.

11. ¿Cuál es la importancia de las gramáticas libres de contexto?
La...