LENGUAJES Y AUTOMATAS I

Buscar este blog

máquina de turing

el noviembre 26, 2024

Obtener vínculo
Facebook
X
Pinterest
Correo electrónico
Otras apps

Obtener vínculo
Facebook
X
Pinterest
Correo electrónico
Otras apps

Comentarios

Publicar un comentario

Entradas populares

5.5 Diagramas de sintaxis 5.6 Eliminación de la ambigüedad. 5.7 Tipos de analizadores sintácticos 5.8 Generación de matriz predictiva (cálculo first y follow) subir al blog con imágenes y videos

ANALISIS SINTACTICO 5.1 GLC. Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X → α, donde X es una variable y α es una cadena que puede contener variables y constantes. Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”) Capturan la noción de constituyente sintáctico y la noción de orden. Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurador. Propiedades computacionales interesantes: se puede reco nocer en tiempo polinómico. Una Gramática Libre de Contexto es una tupla con 4 parámetros: G = (V, T, P, S) V – conjunto de símbolos variables T – conjunto de símbolos terminales S Є V, símbolo inicial P – conjunto de reglas de producción: A → α, con α sucesión de símbolos de V U T, eventualmente vacía (α = ε) Una GLC es un dispositivo generador. Definimos el lenguaje LG generado por una gramática G del siguiente modo: G = { w / S →* w } , siendo ⇒* una “especie” de clausura transitiva de ...

5.1 DEfinición y clasificación de gramaticas 5.2 geamaticas libre de contexto 5.3 arboles de derivación

https://prezi.com/view/MS4SeTDsu8xq74tS1ByG/

Longitud de una cadena y potencia de alfabeto

Longitud de una cadena Suele ser útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por símbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la longitud de una cadena es igual al “número de símbolos” que contiene; esta proposición está aceptada coloquialmente, sin embargo, no es estrictamente correcta. Así, en la cadena 01101 sólo hay dos símbolos, 0 y 1, aunque tiene cinco posiciones para los mismos y su longitus es igual a 5. Sin embargo, generalmente podremos utilizar la expresión “número de símbolos” cuando realmente a lo que se está haciendo referencia es al “número de posiciones”. La notación estándar para indicar la longitud de una cadena w es |w|. Por ejemplo, |011| = 3 y |ε| = 0. Potencias de un alfabeto Si Σ es un alfabeto, podemos expresar el conjunto de todas las cadenas de una determinada longitud de dicho alfabeto utilizando una notación exponencial. Definimos Σk para que sea el conjunto ...

Con tecnología de Blogger