1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje






descargar 326.75 Kb.
título1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje
página1/5
fecha de publicación31.05.2015
tamaño326.75 Kb.
tipoDocumentos
l.exam-10.com > Derecho > Documentos
  1   2   3   4   5
UNIDAD I
LENGUAJES Y GRAMATICAS”

1.1.- TERMINOLOGÍA, NOTACIÓN Y CONCEPTOS ELEMENTALES, ALFABETO, SÍMBOLOS, CADENA VACÍA, LENGUAJE, GRAMÁTICA.


  • Alfabeto: Un alfabeto es un conjunto de símbolos finito y no vacío. Convencionalmente, utilizamos el símbolo para designar un alfabeto. Entre los alfabetos más comunes se incluyen los siguientes:

  1. = {0,1}, el alfabeto binario

  2. = {a, b, ……z}, el conjunto de todas las letras minúsculas.

  3. El conjunto de todos los caracteres ASCII o el conjunto de todos los ASCII imprimibles.

  • Símbolos: Un símbolo es una representación tangible de algo abstracto, por lo tanto, es perceptible por medio de algunos de los sentidos, por ejemplo, una letra es un símbolo gráfico que representa un sonido concreto, un dígito es la representación de un valor numérico; los símbolos también pueden representar un concepto o una idea, como los que se emplean en arquitectura, electricidad y matemáticas.

  • Cadena vacía: Es aquella cadena que presenta cero apariciones de símbolos. Esta cadena designada por , es una cadena que puede construirse en cualquier alfabeto.

  • Lenguaje: Es simplemente un conjunto de cadenas que incluyen símbolos de un alfabeto. Esta definición incluye lenguajes familiares, como los lenguajes naturales y los de programación de alto nivel, así como conjuntos de cadenas no relacionados.

  • Gramática: que define los usos correctos de una lengua mediante preceptos.


1.2.- LENGUAJES: PROPIEDADES DE UN ALFABETO CERRADO DE KLEENE, CERRADURA POSITIVA Y SU RELACIÓN CON EL LENGUAJE.
CERRADURA DE KLEENE

Sea L un lenguaje sobre el alfabeto , se define a L* como la cerradura de Kleene o cerradura estrella como la unión infinita de todas las potencias de L, incluyendo la potencia cero.



Ejemplo:

Sea L1= {0,1}, entonces L1* = L10 L11 L12 ….

= {}{0,1}{00,01,10,11}{000,001,010,011,…}

= {,0,1,00,01,10,11,000,001,010,011,…}
Los lenguajes L1 = {} y L2 = \varnothing, son los únicos cuya cerradura de Kleene es finita, y dado que \varnothing0 = {}, se cumple que \varnothing* = {}, y por tanto, para ambos se tiene que: L1* = L2* = {}. También es interesante observar que aunque tengamos la igualdad de las cerraduras L1* = L2*, esto no significa que L1 y L2 tengan que ser iguales.
CERRADURA POSITIVA

De manera similar, se define la cerradura positiva de L, como la unión infinita de todas las potencias de L a partir de uno.



Ejemplo:

Sea L= {ab}, entonces L+ = {ab, abab, ababab, ababababab, ……}, mientras que L*= {, ab, abab, ababab, ababababab, ……}.
PROPIEDADES DE LAS CERRADURAS

Para cualquier lenguaje L, se cumplen las siguientes propiedades:

L* = {} L+

L+ = L. L* = L* . L = L* . L+ = L+ . L*

(L+)+ = L+

(L*)* = (L+)* = (L*)+ = L*
Si L, entonces se sigue necesariamente que: L+ = L*, mientras que si L, se cumple forzosamente que: L+ = L* - {}.
1.3.- OPERACIONES CON LENGUAJES: UNIÓN, CONCATENACIÓN, POTENCIACIÓN.
CONCATENACIÓN:

Sean L1 y L2 dos lenguajes, entonces L1 . L2 = {wx | w L1, x L2 } es el lenguaje concatenación de L1 con L2.
Ejemplo:

  • Sean los lenguajes L1 = {pátz, camé, yuré, cará, zitá} y L2 = {cuaro}, entonces la concatenación de L1 con L2 es L1. L2 = {pátzcuaro, camécuaro, yurécuaro, carácuaro, zitácuaro}.

  • Sean los lenguajes L1 = {01, 21} y L2 = {a, ba, ca}, entonces la concatenación de L1 con L2 es L1 . L2 ={01a, 01ba, 01ca, 21a, 21ba, 21ca}

  • Similarmente se puede obtener L2 . L1 ={a01, ba01, ca01, a21, ba21, ca21}



POTENCIA:

Sea L un lenguaje sobre el alfabeto , entonces para cualquier n 0, se tiene que la enésima potencia de L se define recursivamente como sigue:
= {Ɛ} para n = 0

para n > 0

Ejemplo:

  • Sea L= { ab } entonces L0 = {}, L1 = { ab}

  • Sea L = {0,1} entonces L0 = {}, L1 = {0, 1}, L2 = {00, 01, 10, 11}, Etc.


UNIÓN:

Las demás operaciones de conjuntos se aplican igualmente a los lenguajes, es decir: si L1 y L2 son dos lenguajes cualesquiera, entonces L1 L2 , L1 L2 , L1 - L2 , L2 L1 y L1 L2 también son lenguajes.
1.4 GRAMÁTICA GENERATIVA Y ÁRBOLES DE DERIVACIÓN: SÍMBOLOS TERMINALES, SÍMBOLOS NO TERMINALES, SÍMBOLOS INICIALES, REGLAS DE PRODUCCIÓN, DERIVACIÓN DE PALABRAS.
GRAMATICA GENERATIVA:

Una gramática generativa es la cuarteta G= (N, , S, P), donde:

es un alfabeto de símbolos terminales,

N es la colección de símbolos no terminales,

S es el símbolo inicial de una gramática (no terminal, S N) y

P es la colección de reglas de sustitución, también llamadas producciones.
Ejemplo: G= (N, , S, P), donde:

N= {S, A, B}

= {a, b}

P = {SaB, SbA, Aa, AaS, A bAA, Bb, BbS, BaBB}

DERIVACIÓN DE PALABRAS:

El proceso de generar una cadena se llama “derivación”, donde la doble flecha significa genera o deriva; parte de un símbolo inicial representado por S. Los símbolos en minúsculas son los elementos del alfabeto y se les conoce como símbolos terminales, mientras que las letras mayúsculas se denominan símbolos no terminales (SNT), debido a que solamente aparecen durante el proceso de derivación, pero no pueden figurar en una cadena finalizada, estos son los símbolos que pueden ser reemplazados aplicando alguna de las reglas de sustitución o producciones.


Ejemplo:

G= (N, , S, P), donde:

N= {S, A, B, C}

= {a, b}

P = S aA

SaB

AaA

AbC

BbB

BbC

C (por ser un estado de aceptación)
La secuencia de transiciones que genera la cadena w= aaab, es la siguiente:
S A A A C
La primer regla se interpreta como que la transición del estado S al estado A genera el símbolo a. La flecha expresa que S “es sustituido por” o “produce” la cadena Aa, de modo que puede utilizarse esta regla cuando se tiene al símbolo S en una cadena, el cual puede ser sustituido por la expresión que aparece a la derecha de la flecha.

Por lo tanto la cadena w= aaab se puede generar por medio de las reglas anteriores. De este modo si se parte del símbolo inicial S y se aplica la primer regla, se obtiene aA, y si luego se aplica en dos ocasiones la tercera regla, se obtiene aaaA, luego se emplea la cuarta regla para obtener aaabC y finalmente la última regla para terminar en aaab.

Este proceso se puede describir de manera compacta así:
SaAaaAaaaAaaabCaaab
ARBOL DE DERIVACIÓN:

Es un árbol que representa en forma gráfica la manera como una gramática dada genera a una cadena concreta y tiene las siguientes propiedades:

  • La etiqueta de la raíz es S.

  • La etiqueta de cualquier vértice que no es hoja es un símbolo no terminal.

  • La etiqueta de cualquier vertice hoja es un simbolo terminal o .

  • Para cada producción de la forma A w, que se aplique en una derivación, deberá haber un nodo etiquetado con el SNT A, cuyos descendientes correspondan a cada uno de los símbolos que forman la cadena w, (en el mismo orden).

  • La concatenación de los símbolos que haya en cada una de las hojas (leídos de izquierda a derecha) proporciona la cadena obtenida en la derivación que representa el árbol.

1.5 JERARQUÍA DE CHOMSKY PARA LAS GRAMÁTICAS
1.5.1 Gramáticas tipo 0 o de estructuras de frase.
Corresponden a las gramáticas no restringidas, también conocidas como las gramáticas irrestrictas o gramáticas de estructura frase. A los lenguajes generados por estas gramáticas se les llama lenguajes recursivamente enumerables, o simplemente lenguajes enumerables y pueden ser aceptados, pero tal vez no decididos, por alguna de Turing.
1.5.2 Gramáticas tipo 1 o sensitiva al contexto.
Gramáticas sensibles al contexto. Los autómatas lineales acotados reconocen lenguajes de este tipo. Las producciones son de la forma: y deben cumplir que
1.5.3 Gramática tipo 2 o de libre contexto.
Corresponden a las gramáticas independientes del contexto, las cuales generan los lenguajes independientes del contexto y pueden ser reconocidos por medio de los autómatas de pila no determinista.
1.5.4 Gramática tipo 3 o regular.
Los lenguajes reconocidos por estas gramáticas se denominan lenguajes regulares, y son reconocidos por autómatas finitos.
1.6 GRAMÁTICAS Y LENGUAJES.
Informalmente, tal como se entiende en el contexto de los lenguajes naturales, una gramática es un conjunto de reglas que definen la estructura de algún lenguaje formal. Esto es, la estructura de las cadenas válidas dentro de dicho lenguaje.


UNIDAD II
AUTOMATAS DE ESTADO FINITO”

2.1 ESPECIFICACIÓN DE UN AUTÓMATA DE ESTADO FINITO.
Un Autómata finito (AF) es una máquina de estados que determina si una cadena pertenece o no a un Lenguaje. Para decidir si la cadena pertenece al lenguaje lee los caracteres que la forman de izquierda a derecha y con esta información decide si debe permanecer en el estado en el que se encuentre o cambiarse a otro estado. El AF tiene un solo estado inicial que es el estado en el que se encuentra cundo empieza a leer la entrada y puede tener varios estado finales. Si cuando termine de leer la entrada se encuentra en uno de estos estados finales, entonces la entrada es una cadena que pertenece al Lenguaje. Si cuando termine de leer la entrada no queda el autómata en uno de los estados finales, entonces la entrada no es una cadena que forme parte del lenguaje.
2.1.1 AUTÓMATA FINITO DETERMINISTA.
Formalmente se define a un autómata finito determinista (AFD) por la quíntupla M= (Q, , s, F, ), donde: Q es un conjunto finito de estados, es el alfabeto de entrada, s Q es el estado inicial, F es el subconjunto de Q de los estados de aceptación (F Q) y es la función de transición definida por : Q x Q.

La característica principal de un AFD es que es una función que está definida para todos los posibles estados qi Q y para todos los símbolos . Es decir, para cualquier pareja de la forma (qi, j ) siempre existe un único estado siguiente.
Ejemplo:
Sea M el AFD donde Q= {q0, q1}, ={a, b}, s= q0, F={ q0} y las siguientes transiciones: ( q0,a)= q0, ( q0,b) = q1 , ( q1,a) = q1 y ( q1,b) = q0.
Esto se representa por medio de la siguiente tabla de transiciones:


Tabla 2.1
A partir de la tabla se puede construir el diagrama de transiciones correspondiente a este AFD, el cual se muestra en la siguiente figura:


Figura 2.1
  1   2   3   4   5

Añadir el documento a tu blog o sitio web

similar:

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconLa “chupa” a que hace referencia V era una pieza de vestimenta típicamente...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconEn una primera clasificación general de las propiedades de la materia,...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje icon8 Incapacidad de relación. Vínculo con adultos. No relación con iguales. 6

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconResumen de las teorías clasicas
«teorías clásicas», que fueron enunciadas en relación al trabajo y la energía durante aquella primera época (siglo XIX y principios...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconSe definen las prácticas del lenguaje como las diferentes formas...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconSe definen las prácticas del lenguaje como las diferentes formas...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconLos lenguajes fracasados – guía de trabajo
«La conciencia aparece entonces como una forma de con­tacto social con uno mismo»?

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconLo verosímil se refiere a la relación de un texto con la opinión...
«el honor de la familia es sagrado», o, en un filme policíaco, ver al detective empeñarse contra viento y marea en descubrir al culpable,...

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconLa relación conocimiento y lenguaje en la cibernética de segundo orden1

1 lenguajes: propiedades de un alfabeto cerrado de kleene, cerradura positiva y su relación con el lenguaje iconVigésima letra del alfabeto latino. Numéricamente representa 5; por...






© 2015
contactos
l.exam-10.com