Archive for 2016
Gramática
Gramática
Es
una estructura matemática con un conjunto de reglas de formación que definen
las cadenas de caracteres admisibles en un determinado lenguaje formal o lengua
natural. Las gramáticas formales aparecen en varios contextos diferentes: la
lógica matemática, las ciencias de la computación y la lingüística teórica,
frecuentemente con métodos e intereses divergentes. Una gramática formal no
describe el significado de las fórmulas bien formadas, sino solamente su forma.
Representación
Gráfica:
Llamamos
Gramática Generativa a la cuádrupla G = (V,
T, P, S) donde:
* V: alfabeto de variables o símbolos no
terminales.
* T:
alfabeto de símbolos terminales.
* P: conjunto de reglas de producción.
* S:
Símbolo especial de V denominado axioma o símbolo inicial de la gramática.
Ejemplo:
La
siguiente gramática genera las cadenas del lenguaje L1 = {wcwR / w _ {a, b}* }
G1 =
({A}, {a, b, c}, P1, S1), y P1 contiene las siguientes producciones:
S1 _
A
A _
aAa
A _
bAb
A _
c
Gramáticas Libres de Contexto (CFG’S) y Lenguaje Natural o Sensible al Contexto
Gramáticas
Libres de Contexto (CFG’S)
Las gramáticas libres de contexto amplían la
capacidad para especificar lenguajes al incluir algunos lenguajes que no son
reconocidos por un autómata finito
Son útiles para describir expresiones
aritméticas que tengan una anidación arbitraria de paréntesis balanceados y
estructuras de bloque en los lenguajes de programación.
Características
de las Gramáticas:
* Un alfabeto S de caracteres llamados símbolos terminales con los cuales se obtienen cadenas que forman las palabras de un lenguaje.
* Un conjunto de símbolos no terminales, uno de los cuales es el símbolo S conocido como símbolo inicial.
* Un conjunto finito de producciones de la forma. Un no terminal ® cadenas finitas de terminales y/o no terminales.
* Un alfabeto S de caracteres llamados símbolos terminales con los cuales se obtienen cadenas que forman las palabras de un lenguaje.
* Un conjunto de símbolos no terminales, uno de los cuales es el símbolo S conocido como símbolo inicial.
* Un conjunto finito de producciones de la forma. Un no terminal ® cadenas finitas de terminales y/o no terminales.
Lenguaje
Natural o Sensible al Contexto:
Lenguaje
Artificial:
Estudiar
actividades humanas. Toma de decisiones y resolver problemas.
* Análisis Morfológico: Palabras individuales no incluye
* Análisis Morfológico: Palabras individuales no incluye
* * Integración del Discurso
Lenguaje Natural:
* Análisis Sintáctico: secuencias lineales.
* Análisis de las Pragmáticas: Se re interpretan para determinar su significado actual.
* Análisis Semántico: Significados a las estructuras.
* Análisis Sintáctico: secuencias lineales.
* Análisis de las Pragmáticas: Se re interpretan para determinar su significado actual.
* Análisis Semántico: Significados a las estructuras.
Lenguajes Regulares
Lenguajes
Regulares
Son usados
en la construcción de analizadores léxicos - programas que analizan un texto y
extraen los lexemas (o unidades léxicas) que hay en el mismo.
Estos
Pueden ser el conjunto de los lenguajes regulares sobre
un alfabeto S está formado por el lenguaje vacío. Los lenguajes unitarios
incluido {e} y todos los lenguajes obtenidos a partir de la concatenación,
unión y cerradura de estrella de lenguajes.
Ejemplo:
Expresión
Regular
|
Lenguaje
Regular
|
10
|
L={La cadena de
10}
|
1 + 0
|
L={Una cadena
de 0 ó una cadena de 1}
|
1*
|
L={Cualquier
cadena de 1’s incluyendo e }
|
(00)*
|
L={Cadenas de
0’s de longitud par, incluyendo e }
|
0*1*
|
L={Cadenas de
ninguno o más 0’s concatenadas a cadenas de ninguno o más 1’s}
|
1(1 + 0)*
|
L={Todas las
cadenas sobre el alfabeto {1, 0} que empiecen con 1}
|
(1 + 0)*00
|
L={Todas las
cadenas sobre el alfabeto {1, 0} que terminen en 00}
|
(1 + 0)*00(1
+ 0)*
|
L={Cualquier
combinación de 0’s ó 1’s que contengan al menos dos ceros consecutivos}
|
Representación Finita del Lenguaje y Expresiones Regulares
Representación Finita del Lenguaje
Palíndromos:
Cadenas que se leen igual de
izquierda a derecha y viceversa.
Un Alfabeto:
Es un conjunto finito de símbolos.
Un Lenguaje:
Conjunto de cadenas de símbolos tomados de
algún alfabeto.
Lectura:
Sobre
el alfabeto {0,1} es seria la siguiente {1,0}.
Expresiones Regulares
Los lenguajes aceptados por un autómata
finito se describen con facilidad mediante expresiones simples llamadas
expresiones regulares.
Sea S un alfabeto. La expresión regular sobre
S y los conjuntos que denotan se definen de manera recursiva.
Æ es una expresión regular y denota al
conjunto vacío. Es una expresión regular y denota al conjunto {e }. Para cada a
Î S , a es una expresión regular y denota al conjunto {a}
Cadenas o Strings
Cadenas o Strings
Es una secuencia finita de símbolos.
Ejemplo:
a, b y c son
símbolos y abcb es una cadena.
Tipos de Cadenas:
Cadena Vacía:
Denotada
por e es la cadena que consiste en cero símbolos. Por ende tiene longitud |e
|=0.
Longitud:
Si w es
una cadena sobre cualquier alfabeto, su longitud se denota como |w |. La
longitud de w es el número de símbolos que tiene la cadena
Ejemplo:
abcb tiene longitud |w | =4.
Concatenación:
Es
la cadena que se forma al escribir la primera seguida de la segunda, sin que
haya espacio entre ellas. La concatenación de las cadenas w y z se
denota como wz ó w.z.
Ejemplo:
Si w=
"banana" y z= "rama", la concatenación de w con z es
la cadena "bananarama. Es decir, e w= we =w para cada cadena w.
Potencia de Cadenas:
La
noción de potencia de una cadena sobre un alfabeto es dada por la notación wk
que denota la concatenación de k copias de la cadena w.
Ejemplo:
Si w=122 sobre el alfabeto S ={1, 2}, se
tiene:
w0 = e
w1 = 122
w2 = 122122
w3 = 122122122
Sufijo:
Están
formados por los últimos símbolos de está. La cadena abc sus prefijos son: e, c, bc y
abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio.
Sub Cadena:
Cadena
w es una subcadena o subpalabra de otra cadena z si existen las cadena x e y
para las cuales z= xwy.
La Transpuesta:
La
inversa o transpuesta de una cadena w es la imagen refleja de w. Para denotar
la inversa de w se usa wI
Por ejemplo:
si w = "able" entonces
su inversa es "elba".
Alfabeto
Alfabeto
Es conjunto no vacío y finito de símbolos. Símbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vacía, la cual se denota por el símbolo e, es una palabra sobre cualquier alfabeto.
Ejemplo:
{0,1}
{a,b,c…,x,y,z}
{0,1,2,3,4,5,6,7,8,9}
{a,b}
En Ingles:
La
colección finita es el conjunto de las letras del alfabeto junto con los
símbolos que se usan para construir palabras en inglés
Conjuntos
Conjuntos
Es
una colección de objetos llamados elementos del conjunto. Si A es un
conjunto y a es un elemento de A utilizaremos la notación a Î A (se
lee "a es un elemento de A"). Se usa la notación bÏ A cuando b no
es un elemento de A.
Operaciones Con Conjuntos:
El Conjunto Æ llamado conjunto vacío:
No tiene elementos. El conjunto vacío es un
subconjunto de todos los conjuntos.
La Unión:
De conjuntos A y B se
denota por A È B y es un conjunto formado por los elementos que
aparecen en A, en B o en ambos.
Ejemplo:
Si A={1, 2, 3} y B= {a, b},
entonces A È B={1, 2, 3, a, b}.
La Intersección:
De A y B es el conjunto
de todos los elementos que aparecen simultáneamente en A y también
en B.
Ejemplo:
Por lo tanto A Ç B ={x| xÎ A y x Î B}.
El conjunto Potencia:
A, es el conjunto formado por todos los
subconjuntos de A.
Ejemplo:
sea A={a, b, c} . Entonces 2A ={Æ , {a},
{b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Producto cartesiano
AxB, es el conjunto de todos los pares
ordenados de los que el primer elemento proviene de A y el segundo de B.
Así que, AxB ={(a, b)|aÎ A y bÎ B}.
Ejemplo:
Sí A={1,2,3} y B={5,6}
entonces: AxB ={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.
La Intersección:
Cuando cualquier elemento de A que
este en B, o cualquier elemento de B que este en A, ó que sean iguales.
Ejemplo:
Si A={2, 4, 5, 7, 8} y B={2, 4},
entonces AÌ B={2, 4}.
La Cardinalidad:
De un conjunto es el número de elementos de
ese conjunto.
Ejemplo:
Si A={a, b} entonces |A|=2.
La
cardinalidad del conjunto vacío es 0 porque no tiene ningún elemento,
