CUESTIONARIOS

UNIDAD 1

Define que significa cada uno de los conceptos siguientes:

Alfabeto:

Un alfabeto es un conjunto finito no vacío cuyos elementos se llaman símbolos. Denotamos un alfabeto arbitrario con la letra Σ.

Símbolos:

Es una entidad abstracta que no se puede definir, ya que se dejaría como un axioma. Igual que se define un punto en la geometría.

Cadenas:

Una cadena o palabra sobre un alfabeto Σ. admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ.

Longitud de cadena.

La longitud de cadena es el número de símbolos que contiene

Cadena Vacía.

Una cadena vacía es la única cadena de caracteres de tamaño cero. Y la podemos denotar usualmente con letras λ o Є (griegas).

Lenguajes

Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina lenguaje.

Lenguaje natural (castellano)

Nosotros estamos relacionados con el concepto tradicional de gramática que, de esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos indican que es correcto y que no lo es del, lenguaje natural.

Lenguaje artificial

en este lenguaje aplicamos el mismo método en el cual definimos un fragmento del lenguaje de programación.

Lenguaje regular

Llamamos así a los lenguajes porque sus palabras contienen "regularidades" o repeticiones de los mismos componentes, por ejemplo en este lenguaje L1 = {ab, abab, ababab, abababab,...}

UNIDAD 2

¿Qué es una expresión regular?

Una expresión regular es un conjunto de caracteres que definen un patrón, el cual puede ser comparado contra una cadena de texto cualquiera en aras de determinar si dicha cadena cumple con los requerimientos de formato. Si la cadena cumple, se puede extraer la porción de texto que concuerda en uno o varios grupos.

¿Cuáles son algunos de los elementos de una expresión?

• Clases de caracteres
• Caracteres de escape
• Grupos

Menciona algunas de las operaciones para expresiones regulares

• Unión o Alternativa
• Concatenación

Menciona las tres operaciones básicas que se pueden realizar sobre las ER:

• Selección de alternativas
• Concatenación
• Repetición o Cerradura

¿Cómo se indica la selección de alternativas?

Se indica con el operador |(barra vertical).

¿Cómo se indica la selección de Concatenación?

Se indica con la yuxtaposición de las ER.

¿Cómo se indica la selección de Repetición o Cerradura?

Se indica con el operador *.

¿Con que otro nombre se conoce la selección de repetición o cerradura?

También se conoce con el nombre de cerradura de Kleene.

UNIDAD 3

UNIDAD 4

¿Qué es un analizador léxico?

(en inglés scanner) es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos.

¿Qué es un token?

Es un par que consiste en un nombre de token y un valor de atributo opcional.

¿Qué es un patrón?

Es una descripción de la forma que pueden tomar los lexemas de un token. En el caso de una palabra clave como token, el patrón es sólo la secuencia de caracteres que forman la palabra clave.

¿Qué es un lexema?

Es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de ese token.

¿Qué es una tabla?

Es un conjunto de pares clave-valor, llamados elementos de la tabla. La tabla de símbolos es una componente necesaria de un compilador.

Menciona las operaciones que realiza el compilador

• Reportar clara y exactamente la presencia de errores
• Recuperarse de cada error lo suficientemente rápido para poder detectar errores subsiguientes

UNIDAD 5

¿Qué es el análisis Sintáctico?

En el modelo del compilador, el analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente.

¿Qué es el árbol de derivación?

Es una representación gráfica (en forma de árbol invertido) de un proceso de derivación en una gramática.

¿Cuáles son los pasos para definir el árbol de derivación?

• la raíz del árbol será el símbolo inicial de la gramática
• los nodos interiores del árbol están etiquetados por los símbolos no terminales
• las hojas están etiquetadas por símbolos terminales
• si un nodo interior etiquetado por A, posee como hijos los nodos etiquetados por X1,X2, ...Xn , entonces A→ X1,X2, ...Xn es una producción de la gramática, en donde Xi , representa símbolo terminal o no terminal.

¿Cuándo una gramática formal está en Forma normal de Chomsky?

si todas sus reglas de producción son de alguna de las siguientes formas:A → BC o
A → a odonde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

¿Qué es un diagramas de sintaxis?Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto.

UNIDAD 6

¿Qué es la máquina de turing?

Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

¿Quién invento la máquina de turing?

La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936.

Puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo:

Máquina de turing

¿Cuál es el funcionamiento de MT?

Su funcionamiento se basa en una función de transición, para detenerse en un estado final o de aceptación, representando así la salida.

¿Cuáles son las operaciones que se pueden realizar en esta máquina?

· avanzar el cabezal lector/escritor para la derecha.

· avanzar el cabezal lector/escritor para la izquierda.

¿Cuál es el objetivo de la creación modular de una máquina de Turing?

es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de máquinas más pequeñas, mediante diagramas de transiciones.

Menciona los pasos para la construcción de una máquina de Turing:

• Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.
• limine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los diagramas que se combinan.
• Para cada uno de los antiguos estados de parada p y cada x en y.