Kategorier: Alle - longitud - cardinalidad - lenguaje - cadenas

av Diana Avella 3 år siden

193

Alfabetos

Un conjunto finito y no vacío cuyos elementos se denominan símbolos se define a través de la enumeración de dichos símbolos y se denota como Sigma. Las cadenas o palabras son concatenaciones de símbolos de un alfabeto, y pueden no tener sentido en nuestro lenguaje.

Alfabetos

Alfabetos

Conjunto finito, no vacío cuyos elementos se llaman símbolos.

·      Se define por la enumeración de los símbolos que contiene.

·      Se denota como ∑ .

Cadenas o palabras

Concatenación de símbolos del alfabeto.

·      Formada con los símbolos de un alfabeto.

·      Pueden no tener sentido en nuestro lenguaje.

·      Se denotan con letras minúsculas.

·      Palabras tiene sentido y las cadenas no tienen sentido.

·      ∑*=El conjunto de todas las cadenas sobre un alfabeto ∑ incluyendo (λ).

cantidad de elementos.

·      ·      Cardinalidad= A^n donde A=Cardinalidad n=longitud.

Longitud de una cadena

Cantidad de elementos que tiene una cadena.

·      Se representa con |x|

·      La cadena con longitud cero se llama vacía, se representa con la letra griega Lamda(λ)

Lenguaje universal

Conjunto de todas las cadenas que se pueden formar con las letras del alfabeto.

·      Se denota como W(∑)

·      Es un conjunto finito.

·      Tienen sentido.

Lenguaje

Conjunto de cadenas.

·      ɸ<=L<=∑* donde L es el lenguaje

·      Se denota con letras mayúsculas.

·      Se denota con ɸ Lenguaje vacío.

Operaciones entre lenguajes

Operación estrella o cierre

La cantidad de cadenas multiplicada n veces incluyendo A^0

. Se denota con A^*

Clausura positiva o cierre

La cantidad de cadenas multiplicada n veces positivas.

·       Se denota con A^+ n veces.

Potencia de un lenguaje

Concatenación sucesiva de A^n donde n son las veces que se multiplica un mismo lenguaje.

·     A^0 = {λ}

·   A^1 =A

·     A^n =A*A*A… n veces.

Reflexión o inversa del lenguaje

Es escribir de atrás hacia adelante una cadena.

·       Se denota como A^R

Concatenación

Colocar un elemento del primer conjunto y pegarlo con un elemento del segundo conjunto. Es decir, L1 primero y luego L2.

·       La cardinalidad del resultado de una concatenación de dos lenguajes es multiplicar la cardinalidad de cada lenguaje. |A*B|=|A|*|B|.

·       No es conmutativa es decir AB≠BA el orden no importa.

Intersección

Intersección = “y” es decir que debe estar en ambos.

·       Se denota con el símbolo “∩”

Unión o alternativa

Unión = “o” es decir puede estar en uno o en el otro o en ambos.

·       Se denota con el símbolo “U”

·       Es asociativa (AU B)U C=A U (B U C)

·       El lenguaje vacío es elemento neutro de la concatenación L U ɸ = ɸ U L=L.

·       Es conmutativa es decir A U B= B U A 

Operaciones entre cadenas
Reflexión o inversa

Es escribir de atrás hacia adelante una cadena.

·       Se denota como U^R

Potencia

Concatenación sucesiva de U^n donde n son las veces que se multiplica una misma cadena.

·    U^0 =λ

·    U^1=u

· U^n= u*u*u… n veces.

Concatenación de dos cadenas

colocar una cadena junto a otra.

·       No es conmutativa es decir ab≠ba el orden si importa.

·       Es asociativa (uv)w=u(vw)

·       La longitud del resultado de una concatenación de dos cadenas es sumar la longitud de cada cadena. |uv|=|u|+|v|.

·       La cadena vacía es el elemento neutro de la concatenación. uλ= λu=u.

Cardinalidad

cantidad de elementos.

·       Cardinalidad= 2^n donde n es la longitud.