Unidad 1 Lenguajes y Automatas 1

Unidad 1: Introducción a la Teoría de Lenguajes y Autómatas.


1.1  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 una axioma. Igual que se define un punto en la geometría. La cual normalmente los símbolos son letras (a, b, c,…. z), dígitos (0,1,…9, caracteres (+, -, *, /,>,< …..). los símbolos pueden estar formados por varias letras o 
caracteres.
                                        



Alfabeto:

El alfabeto o abecedario es un conjunto de letras, con un determinado orden. podríamos precisamente decir que el alfabeto es un conjunto de letras (caracteres o grafemas) de un sistema de escritura, cada una representa aproximadamente un fonema (consonante o vocal).


1.2 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 λ. la cadena vacía desempeña, en la teoría de lenguajes formales, un papel similar al que desempeña el conjunto vacío Ø en la teoría de conjuntos.

Longitud de cadena.


La longitud de cadena es el numero de símbolos que contiene. La notación empleada es la que es la que se indica en el ejemplo:Utilizamos las cadenas de los ejemplos:I abcb I = 4,I a + 2*b I = 5I 000111 I = 6I if a > b then a = b; I = 9
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).

Concatenación de cadenas.

La concatenación de dos cadenas u y v, escrita uv, es "pegar" las dos cadenas para formar una nueva.
Ejemplo:
Sea u = ab
v = ca
w = bb. Entonces
uv = abca
uw = cabb
(uv) w = abcabb
u(vw) = abcabb

El resultado de la concatenación de u, v y w es independiente del orden en que las operaciones son ejecutadas. Matemáticamente esta propiedad es conocida como asociatividad.
Universo del discurso.
Es un conjunto de todas las cadenas donde podemos formar con símbolos del alfabeto V le denominamos universo del discurso de V y la representamos de la siguiente manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadena vacía pertenece a W(V).
Ejemplo:

Un afabeto con una sola letra V = { a }, podemos decir que el universo del discurso es: W(V) = { λ, a, aa, aaa, aaaa,....} y asi contiene una cadenas infinitas.

                                                        1.3 Lenguajes.


Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un súper conjunto de Σ.
La elección del termino "lenguaje" puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el Ingles, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.


Tipos de lenguajes.

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. Con este fin podemos acércanos a la definición mas clara y formal de la lengua castellana.

Lenguaje artificial.

en este lenguaje aplicamos el mismo método en el  cual definimos un fragmento del lenguaje de programación. Donde pretendemos describir las instrucciones el cual nos permite asignar un valor a una expresión ó a una variable en un lenguaje C.

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,...} Este ejemplo podemos apreciar las palabras de L1 son solo repeticiones de "ab" donde se repiten varias veces. Su regularidad consiste en las palabras que contienen "ab" varias veces.


1.4 Herramientas computadoras ligadas con lenguajes.

Traductor.

Un traductor es un programa que tiene como entrada un texto escrito en un lenguaje (lenguaje fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto) que preserva el significado de origen.
Ejemplos de traductores son los ensambladores y los compiladores.


Compilador.

El compilador es un programa informático que traduce un programa escrito en lenguaje de programación y lo pasa a lenguaje de programación, podemos decir que este programa nos permite traducir un código fuente de un programa en lenguaje de nivel alto, y lo pasmos a otro nivel inferior (lenguaje maquina).


Ensambladores.

El ensamblador es el programa en que se realiza la traduccion  de un programa escrito en ensamblador y lo pasa a lenguaje maquina. Directa o no directa la traducción en que las instrucciones no son mas que instrucciones que ejecuta la computadora.

Interpretes.

Los interpretes son los que realizan normalmente dos operaciones:
  • Traducen el código fuente a un formato interno.
  • Ejecuta o interpretan el programa traducido al formato interno.
Donde la primera pertenece al interprete el cual llama a veces al compilador, así se genera el código interno, pero no es el lenguaje de maquina, ni lenguaje de símbolos, ni mucho menos un lenguaje de nivel alto.






Comentarios

Publicar un comentario

Entradas más populares de este blog

Unidad 2 Lenguajes y Automatas 1 - Expresiones Regulares.

Imagen
Unidad 2 - Expresiones Regulares. 2.1. Definición formal de una ER. Es un equivalente algebraico para un autómata. Utilizado en muchos lugares como un lenguaje para describir patrones en texto que son sencillos pero muy útiles. Pueden definir exactamente los mismos lenguajes que los autómatas pueden describir: Lenguajes regulares. Ofrecen algo que los autómatas no: Manera declarativa de expresar las cadenas que queremos aceptar. Dado un alfabeto Σ, una , expresión regular sobre expresión regular sobre Σ se define de forma recursiva: ER primitivas: Φ, λ, {a | a ЄЄЄ Σ Є} Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α). No existen otras reglas para la construcción de ER sobre Σ. Ejemplos de usos. Comandos de búsqueda, e.g., grep de UNIX. sistema de formato de texto: Usan notación de tipo expresión regular para describir patrones. Convierte la expresión regular a un DFA o un NFA y simul...
Leer más

Graficacion Unidad 3

Imagen
UNIDAD 3  GRAFICACION EN 3D 3.1.- Representación De Objetos En Tres Dimensiones. En computación, un modelo en 3D es: “Un mundo conceptual en tres dimensiones”. Un modelo 3D se ve de dos formas distintas: Desde un punto de vista técnico, es un grupo de fórmulas matemáticas que describen un “mundo” en tres dimensiones. Desde un punto de vista visual, valga la redundancia, un modelo en 3D es una representación esquemática visible a través de un conjunto de objetos, elementos y propiedades que, una vez procesados (renderización), se convertirán en una imagen en 3D o una animación 3d. La representación de los objetos en tres dimensiones sobre una superficie plana, de manera que ofrezcan una sensación de volumen se llama Perspectiva. Se representan los objetos sobre tres ejes XYZ. En el eje Z, se representa la altura. En el eje Y, se representa la anchura y en el eje X, se representa la longitud. Los distintos tipos de perspectivas dependen de la inclinac...
Leer más

Unidad 3 Lenguajes y Automatas 1

Imagen
Unidad III: Autómatas finitos  Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida. La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky. 3.1 Definición formal Formalmente,  Un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:   Q : es un conjunto finito de estados;   Σ : es un a...
Leer más