Please enable JavaScript.
Coggle requires JavaScript to display documents.
Formales, Autómatas y Procesadores de Lenguajes (Conjuntos (Operaciones…
Formales, Autómatas y
Procesadores de Lenguajes
Conjuntos
Definicion
a toda agrupación de individuos bien definidos que cumplen una propiedad
Notacion
A = {Números naturales menores que 5}
B = {verde, blanco, rojo}
A = {m : m es un número natural, y 1 ≤ m ≤ 5}
Operaciones
Union (U)
A U B
Interseccion(∩)
A ∩ B
Diferencia: ( \ )
A / B
Complemento
A
Diferencia simétrica (Δ)
A Δ B
Producto cartesiano (×)
A X B
Tabla de la verdad
arreglo que nos permite tener los posibles valores de verdad de una proposición compuesta a partir de los valores de verdad de las proposiciones simples.
Propiedades
Alfabeto
conjunto no vacío y finito de símbolos se conoce como alfabeto.
𝚺 = {0,1,2,3,4,5,6,7,8,9}
Palabra
Una secuencia finita de símbolos de un determinado alfabeto
123,54,6654
Lenguajes
Un sistema de comunicación estructurado para el que existe un contexto de uso y
ciertos principios combinatorios formales.
{1,11,111,1111,11111,…}
Mueve loco
Alfabetos, Palabras y Lenguajes
Alfabeto
Un conjunto no vacío y finito de símbolos se conoce como alfabeto.
El símbolo que representa a un alfabeto es: 𝚺
ejemplo: 𝚺 = {0,1,2,3,4,5,6,7,8,9}
también se le pueden aplicar las operaciones de conjunto.
𝚺1 ⋃ 𝚺2
𝚺1 ⋂ 𝚺2
𝚺1 - 𝚺2
𝚺2 - 𝚺1
Palabra
Una secuencia finita de símbolos de un determinado alfabeto se conoce como Palabra
sobre dicho alfabeto.
Con la definición que hemos dado de palabra de un alfabeto, las palabras, BTEUDW y
KUKOPLSI también son consideradas palabras.
Lenguaje
Un lenguaje es un sistema de comunicación estructurado para el que existe un contexto de uso y
ciertos principios combinatorios formales. Existen contextos tanto naturales como artificiales.
Es un conjunto de palabras, por tanto el Ejemplo {1,12,123,1234,12345,123456}
Lenguajes Formales
Los lenguajes formales son construcciones artificiales humanas que se usan en matemática
y otras disciplinas formales, incluyendo lenguajes de programación.
Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien
formadas.
Operaciones con cadenas
La longitud de w es el número de símbolos que tiene la cadena. Así que, si w = 121
sobre el alfabeto 𝚺 = {1,2}, entonces |w| = 3.
la concatenación de w con z es la cadena que se obtiene al añadir
a la cadena w la palabra z. Por ejemplo:
Si w = “banana” y z = “rama”, la concatenación de w con z es la cadena “bananarama”.
La concatenación de las palabras w y z, se denota como wz o w· z es decir:
|wz| = |w|+|z|
Vamos a introducir la noción de potencia de una palabra sobre un alfabeto.
ejemplo:
w0 = ɛ
w1= 122
w2 = 122122
w3 = 122122122 y así sucesivamente.
Sufijos y prefijos
Dentro de las cadenas de un alfabeto, los sufijos y prefijos son análogos a lo que convencionalmente
conocemos.
Entonces si w y x son palabras, se dice que x es prefijo de w, si para alguna cadena y se obtiene que w
= xy.
ejemplo:
Si w = 121 entonces la cadena x = 12 es un prefijo de w e y = 1.
Si y = ɛ, entonces para w = xy se tiene que w = x, con lo que toda palabra puede considerarse
prefijo de sí misma.
Inversa o transpuesta
Sea una palabra w, sería definida como la imagen refleja de w.
Ejemplo: w = “able” entonces su inversa es “elba”.
Para denotar la inversa de w se usa wI
Lenguajes
Se clasifican como:
Lenguaje de bajo nivel
"Son aquellos que sus instrucciones ejercen un control directo sobre el "hardware" y están condicionados por la estructura física de las computadoras que lo soportan".
Tipos de bajo nivel
Código Binario
Lenguaje más básico que forma parte de todos los sistemas informáticos. Es muy habitual por ser bastante sencillo de utilizar. Tan solo se usan dos números para formar el código, el 1 que representa al “todo” y el 0 que por el contrario es el “nada”.
Lenguaje ensamblador
algo más complicado porque los códigos que utiliza no los descifra directamente el ordenador, por lo que habrá que pasarlo a lenguaje de máquina para que la computadora entienda la orden que estamos queriendo transmitirle
Lenguaje de máquina
Es el sistema de códigos directamente interpretable por un circuito microprogramable, como
el microprocesador de una computadora o el microcontrolador de un autómata.
Lenguaje de alto nivel
Se caracteriza por expresar los algoritmos de una manera adecuada a la capacidad cognitiva humana, en lugar de la capacidad con que los ejecutan las máquinas.
Modos de ejecución
Interpretado
Estos lenguajes son leídos y ejecutados directamente, sin compilación; requieren de un programa “interpretador” que lee cada línea siguiendo el flujo del programa y realiza la ejecución. Algunas ventajas son la independencia de plataformas y la facilidad para depurar;. Algunos ejemplos son: Perl, PHP, Python, Ruby, SmallTalk y Java.
Compilado
Estos lenguajes convierten el código en ejecutable antes de correr el programa, el programa se traduce a partir del código fuente a través de un compilador para que sea posible ejecutarlo en una plataforma determinada. Tienen como ventaja que son más rápidos en su ejecución ya que no requieren interpretación y se enfocan en la eficiencia en lugar de soporte en múltiples plataformas. Algunos ejemplos son: C, C++, COBOL, FORTRAN, Pascal, Visual Basic y Visual FoxPro.
Características
utilizan muchos elementos de lenguaje natural y ocultan detalles relativos al sistema
proceso de desarrollo más simple y amigable para el programador.
se enfocan en la usabilidad.
Aplicaciones
Suelen usar tipos de datos para la programacion y hay lenguajes de proposito general (cualquier tipo de aplicacion) y de proposito especifico (como FORTRAN para trabajos científicos)
Función principal
Se tratan de lenguajes independientes de la arquitectura del ordenador. Por lo que, en principio, un programa escrito en un lenguaje de alto nivel, lo puedes migrar de una maquina a otra sin ningun tipo de problema
Clasificación de los Lenguajes Formales
Jerarquía de Chomsky
El primer trabajo que desarrolló teorías formales sobre gramáticas y lenguajes fue obra de Avram Noam Chomsky
El concepto de Gramática Formal adquirió gran importancia para la especificación. Ello condujo rápidamente al diseño riguroso de algoritmos de traducción y compilación.
La Teoría de los Lenguajes y Gramáticas Formales tiene una relación directa con la Teoría de Autómatas, siendo posible establecer entre ambas una correspondencia denominada en Álgebra isomorfismo.
Las gramáticas han sido clasificadas de acuerdo a
las particularidades y restricciones propias, en función de la forma de reglas de derivación o producción.
Clasificación
Gramáticas regulares Tipo 3
Es de Tipo 2,1,0
Independientes del contexto Tipo 2
Contiene las de Tipo 3
Sensibles al contexto Tipo 1
Contiene las de tipo 2 y 3
Las gramáticas no restringidas Tipo 0
Contienen a todas las demás (Tipo 1,2,3)
Tipos de Automatas
Autómatas Finitos (y máquinas secuenciales )
Autómatas Probabilísticos
Autómatas a Pila
Células de Mc Culloch-Piks
Máquinas de Turing
Autómatas Celulares
Redes de Neuronas Artificiales
Restricciones
