Lenguajes formales

En esta página vamos a explicar que son, como se utilizar y cuales son las funciones de los lenguajes formales:

Introducción: Definiciones

  • Definiciones:

• Símbolos (del lenguaje)
• Alfabeto (del lenguaje)
• Palabra (Cadena,string); longitud de palabra / cadena;
• Palabra Vacía
• Universo del Discurso (Lenguaje universal ???).

Símbolo:

• entidad abstracta, no se define (análogo al punto en geometría).
• ¿Qué puede representar un símbolo?Cualquier cosa o concepto.
– ¿Ejemplos?
• ¿Como se representan los símbolos?
• Se representan con letras,dígitos,caracteres,palabras(insertar_tarjeta, disparo, salto)
• También posible encontrar símbolos formados por varios caracteres ,por ejemplo :IF, THEN, ELSE,…

Alfabeto(Σ):

•conjunto finito no vacío de letras o símbolos.
•Sea “a” una letra y Σ un alfabeto, si a pertenece a ese alfabeto Σ : a є Σ
-Ejemplos:
Σ1={A,B,C,…,Z}
Σ2={0,1}
Σ3={IF, THEN ,ELSE, BEGIN, END}

CADENA.PALABRA(ótira):

•toda secuencia finita de símbolos del alfabeto. Ejemplos: Σ1={A,B,C,…,Z}; palabras sobre Σ1 JUAN,ISABEL,etc.
¿Son“NAUJ”,“MIGUELANGEL”,

Σ2={0,1};palabrassobre Σ2 00011101

Σ3= {IF, THEN, ELSE, BEGIN, END}; palabrassobre3IFTHENELSEEND

 Notación

•Las palabras se representan por letras minúsculas del final del alfabeto (x,y,z)
Ejemplo: x=JUAN; y=IFTHENELSEEND; z=00001111111111

Longitud de cadena-palabra:

•Se representa con x
•Es el nºde símbolos que componen una palabra.

Palabra vacía:

Es aquella palabra cuya longitud es cero, lambda=0;
– Sobre cualquier alfabeto es posible construir lambda;
– Utilidad de lambda: será el elemento neutro en muchas operaciones sobre palabras y lenguajes.

Universo del discurso:

• Es el conjunto de todas las cadenas /palabras que se pueden formar con los símbolos de un alfabeto Σ
• También se denomina Lenguaje Universal del alfabeto Σ
• Se representa como W(Σ)
• Es un conjunto infinito (i.e.número infinito de palabras)
– Ejemplo:sea Σ4={A,B},W(Σ4)={,A,B,AA,AB,BA,BB,AAA,…}con un número de palabras.

¿Que es un lenguaje?

Se denomina Lenguaje sobre el alfabeto.
a todo subconjunto del lenguaje universal de Σ(L є W(Σ)).
i.e. a todo conjunto de palabras sobre un determinado Σ.
i.e. a todo conjunto de palabras generado a partir del alfabeto Σ.

Lenguajes especiales


• Lenguaje vacío
•{λ}=Lenguaje de la palabra vacía
Lenguaje vacio y lenguaje de la palabra vacía se diferencian en el número de palabras (cardinalidad) que los forman lenguaje vacio = 0 mientras que lenguaje de la palabra vacia = 1.
Se parecen en que son lenguajes sobre cualquier alfabeto
• Un alfabeto es uno de los lenguajes generados por el mismo:

Operaciones con lenguajes

Operaciones con lenguajes : sobre un alfabeto dado Σ
1.Unión de lenguajes
2.Concatenación de lenguajes
3.Binoide Libre
4.Potencia de un lenguaje
5.Clausura o cierre positivo de un lenguaje
6.Iteración,clausura o cierre de un lenguaje
7.Reflexión de lenguajes

Unión de lenguajes

Sean L1 y L2 definidos sobre el mismo alfabeto , L1, L2 W();

se llama unión de dos lenguajes, L1, L2 y se representa por L1 L2 al lenguaje así definido:
L1L2={x/x є L1 ó x є L2}=
Es el conjunto formado indistintamente por palabras de uno u otro de los dos lenguajes (equivale a la suma) L1+L2=L1L2

Concatenación de lenguajes

•Sean L1y L2 definidos sobre el mismo alfabeto, L1, L2 W(), se llama concatenación o producto de dos lenguajes, L1 y L2, y se representa por L1·L2 al lenguaje así definido:
L1·L2={xy/ x є L1 AND y є L2}
•Es el conjunto de palabras formado por la concatenación de palabras de L1 con palabras de L2
•Definición válida para lenguajes con algún elemento.
•Y con el lenguaje vacío: · L=L · =L

Propiedades:

– Operación cerrad.

– Propiedad Asociativa.

– Con elemento neutro.

– Propiedad distributiva respecto a la unión.

Binoide libre

– La concatenación (monoide) de lenguajes y la unión(monoide)de lenguajes constituyen un binoide
– Los símbolos de Σ se pueden considerar conjuntos de una sola palabra
– Con Σ, la unión y la concatenación se puede formar cualquier lenguaje sobre dicho Σ.Excepto y {λ}.
El alfabeto es un conjunto de generadores para el conjunto
L es el BINOIDE LIBRE (operaciones U y •) generado por Σ

Potencia de un lenguaje

Reducción de la concatenación a los casos que se refieren a un mismo lenguaje
Potencia i-ésima de un lenguaje al resultado de concatenar ese lenguaje consigo mismo  i veces
Concatenación es asociativa, es decir, no especificar el orden
Li = L·L·L·…·L ; iveces
Se define L1=L
Se cumple:
L1+i=L·Li=Li·L(i>0)
Lj+i=Li·Lj(i,j>0)
•Si se define L0={λ},entonces(i>=0) (i,j >= 0)

Anuncios

1 comentario (+add yours?)

  1. Bienvenidos a nuestro nuevo blog « Automátas, gramáticas y lenguajes formales
    Feb 29, 2012 @ 09:25:04

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: