Lenguaje regular - Historial de revisiones

Javiermartin jc: Texto reemplazado: «
» por «»

2019-07-06T20:30:52Z

Texto reemplazado: «<div align="justify">» por «»

UrbanoNoris3 jc en 13:53 28 feb 2012

2012-02-28T13:53:56Z

Jhonlier12017 jc.hlg: /* Definiciones. */

2012-02-24T19:12:53Z

‎Definiciones.

Jhonlier12017 jc.hlg: /* Definición. */

2012-02-23T17:10:26Z

‎Definición.

Jhonlier12017 jc.hlg: /* Definición. */

2012-02-23T17:10:03Z

‎Definición.

Jhonlier12017 jc.hlg: Página creada con '{{Definición|nombre=Lenguaje regular|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 3, reconocibles con [[Autómata finit...'

2012-02-23T16:46:06Z

Página creada con '{{Definición|nombre=Lenguaje regular|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 3, reconocibles con [[Autómata finit...'

Página nueva

{{Definición|nombre=Lenguaje regular|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la [[jerarquía de Chomsky]] son los lenguajes de tipo 3, reconocibles con [[Autómata finito|autómatas finitos]].}}
<div align="justify">
'''Lenguaje regular'''. En [[Lingüística]], [[Matemáticas]] e [[Informática]] y en la [[jerarquía de Chomsky]] se refiere a los lenguajes de tipo 3, aquellos que pueden representarse mediante [[Gramática regular|gramáticas regulares]], [[Autómata finito|autómatas finitos]] o [[Expresión regular|expresiones regulares]].

Son los [[Lenguaje formal|lenguajes formales]] más simples, con los mecanismos de representación y reconocimiento más estudiados. Su aplicación práctica en la teoría y construcción de [[Intérprete|intérpretes]] y [[Compilador|compiladores]] de [[Lenguaje de programacion|lenguajes de programación]] o de [[Lenguaje de especifcación|especificación]] o [[Lenguaje de formato|formato de información]], especialmente como microcomponentes del [[analizador lexicográfico]] que detecta los [[Token|tókenes]] como [[Constante numérica|constantes numéricas]], [[Cadena de texto|cadenas de texto]], operadores, palabras reservadas (''keywords''), separadores, etc. Pero también se puede apreciar su uso en [[Máquina expendedora|máquinas expendedoras]], [[Teléfono público|teléfonos públicos]], [[Calculadora|calculadoras]] y otros artefactos electromecánicos.

==Definición.==
Se dice que un lenguaje es regular si y sólo si se cumple cualquiera de las siguientes proposiciones:
* Tiene al menos una [[gramática regular]] ''G'' que lo produce.
* Puede ser reconocido por un [[autómata finito]] ''A''.
* Existe una [[expresión regular]] ''E<sub>r</sub>'' que representa a todas las cadenas de ''L''.

[[Archivo:Jerarquia_Chomsky.gif|center|Ubicación de los LR en la Jerarquía de Chomsky]]

==Ejemplo 1.==
Demuestre que el lenguaje conformado por los nombres de [[variable|variables]] de [[PROLOG]] es un lenguaje regular.

Primero debe recordarse que un nombre de variable PROLOG viene dada por la forma:

''cualquier palabra que comience con una letra mayúscula seguida o no de combinaciones de letras, cifras o subrayados o que comience con al menos un subrayado seguido o no de cualquier secuencia de alfanuméricos o subrayados''.

Cada de las siguientes construcciones son equivalentes en virtud de la definición dada antes:

* La expresión regular ''(A|B|...|Z)|_(A|B|...|Z|a|b|...|z|_)*''.
* El siguiente autómata finito representado como [[diagrama de estados]] permite el reconocimiento de variables de PROLOG.
** [[Archivo:Variable_PROLOG_diagrama_estados.gif|middle]]
* Una gramática con producciones de la forma:
** [[Archivo:S_flecha_mayuscula_F_o_subrayado_F.gif|middle]].
** [[Archivo:F_flecha_vacia_o_letra_F_o_digito_F_o_subrayado_F.gif|middle]].

==Importancia de los lenguajes regulares.==
La existencia y formalización de los lenguajes regulares (LR) y su vinculación con otros artefactos lingüísticos-matemáticos ya bien formalizados, estudiados e incluso llevados a la práctica ha sido de vital importancia en el ulterior desarrollo de los mecanismos de procesamiento de lenguajes de computadora, fundamentalmente en los analizadores lexicográficos gracias a la posibilidad de derivar el reconocimiento de los LR mediante autómatas finitos que son fáciles de implementar computacionalmente con mecanismos simples y rápidos, óptimos en la obtención de ''parsers'' veloces y robustos que a su vez le ofrecen a los desarrolladores información detallada de los errores léxicos, sintácticos e incluso advierten sobre errores semánticos.

Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos [[Lenguaje de programación de propósito general|lenguajes de propósito general]] modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los ''tókenes'' o partículas lexicales del [[código fuente]] como fase del proceso completo de interpretación o compilado, según sea el caso.

A manera de ilustración en el caso del ejemplo anterior vemos la siguiente [[función]] [[Python]] que a partir de cualquiera de los elementos formalizadores del LR correspondiente permite decidir si un texto ''w'' es una variable PROLOG:

<pre>
def variablePROLOG(w):
'''(str)-->bool. True si "w" es un nombre de variable correcto'''
if (w[0].isalpha and w[0]==w[0].upper()) or w[0]=='_':
#El primer caracter es una mayuscula o un subrayado
w = w[1:] #Se quita el primer caracter
while w and (w[0].isalnum() or w[0]=='_'):
#Mientras queden caracteres en "w" y el primer caracter actual sea un alfanumerico o un subrayado, todo esta bien
w = w[1:] #Quitar el primer caracter
if w=='':
#Si ya no quedan elementos a revisar, es una variable PROLOG
return True
return False
</pre>

Varias funciones de esa naturaleza componen los analizadores lexicográficos para discriminar la función de cada ''token'' del lenguaje en cuestión: constante númerica, literal de cadena de texto, identificador, separador, etc.; según sea el caso.

Y también puede verse que existe una estrecha relación en cómo implementar las funciones reconocedoras de LR y la expresión o la gramática regulares o el autómata finito correspondiente, al punto que desde hace más de 3 décadas existen aplicaciones generadoras de analizadores lexicográficos como el [[Flex]] o el [[Bisonte]].

Pero el alcance de los LR no se queda en el mundo de la [[compilación]] de lenguajes de ordenador como se ve en el siguiente ejemplo.

===Ejemplo 2.===
En un acuario de [[Miami]] se entrenan las capacidades intelectuales de los [[Delfín|delfines]] en cautiverio y tiene especial importancia los resultados que tiene uno de los ejemplares quien ha aprendido a reconocer cantidades pares a partir de imagenes de peces, llegando a distinguir cuando hay un número par o no de peces en la imagen. Muestre que las imágenes de cantidad de peces pares es un lenguaje regular que puede percibir el delfín.

Se define a cada pez de las imágenes con la letra ''p'' minúscula y se ve que para las imagenes pares puede definirse las siguientes producciones de una gramática regular:

* [[Archivo:I_flecha_pp_o_pp_I.gif|middle]]

Por ende, se trata de un LR.

==Véase también.==
* [[Gramática regular]].
* [[Autómata finito]].
* [[Expresión regular]].
* [[Flex]].
* [[Jerarquía de Chomsky]].
* [[Lenguaje libre de contexto]].

==Fuentes.==
# Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
# Conferencias de la Asignatura "Compilación 1" del [[Departamento de Ciencias de la Computación de la Universidad de Oriente|Departamento de Ciencias de la Computación]] de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
# [http://es.wikipedia.org/wiki/Lenguaje_regular Lenguajes regulares en Wikipedia]. Consultado el [[23 de febrero]] de [[2012]].

</div>
[[Categoría:Lingüística]][[Categoría:Matemáticas]][[Categoría:Informática]]

← Revisión anterior		Revisión del 19:12 24 feb 2012
Línea 14:		Línea 14:

	[[Archivo:Jerarquia_Chomsky.gif\|center\|Ubicación de los LR en la Jerarquía de Chomsky]]		[[Archivo:Jerarquia_Chomsky.gif\|center\|Ubicación de los LR en la Jerarquía de Chomsky]]
		+
		+	También puede realizarse una definición recursiva-constructiva de los lenguajes regulares mediante el [[álgebra de lenguajes formales]].
		+
		+	Un lenguaje regular sobre un alfabeto ''T'' ó ''L<sub>R</sub>(T)'' es:
		+	# El lenguaje vacío ''{}''.
		+	# El lenguaje conformado por la cadena vacía [[Archivo:Lenguaje_trivial.gif\|middle]] o [[lenguaje trivial]].
		+	# Un lenguaje ''{x}'' conformado por un único símbolo ''x'' de ''T''.
		+	# Si ''A'' y ''B'' son lenguajes regulares sobre ''T'', entonces ''AB'' ([[Concatenación de lenguajes]]), [[Archivo:A_union_B.gif\|middle]] ([[Unión de lenguajes]]), ''A*'' ([[Clausura de lenguaje]] o [[Estrella de Kleene]]) son también lenguajes regulares sobre ''T''.
		+	# Cualquier otro lenguaje que pueda obtenerse a partir de 1 a 4.

	==Ejemplo 1.==		==Ejemplo 1.==

@@ Línea 1: / Línea 1: @@
 {{Definición|nombre=Lenguaje regular|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la [[jerarquía de Chomsky]] son los lenguajes de tipo 3, reconocibles con [[Autómata finito|autómatas finitos]].}}
-<div align="justify">
 '''Lenguaje regular'''. En [[Lingüística]], [[Matemáticas]] e [[Informática]]  y en la [[jerarquía de Chomsky]] se refiere a los lenguajes de tipo 3, aquellos que pueden representarse mediante [[Gramática regular|gramáticas regulares]], [[Autómata finito|autómatas finitos]] o [[Expresión regular|expresiones regulares]].

@@ Línea 25: / Línea 25: @@
 ==Ejemplo 1.==
-Demuestre que el lenguaje conformado por los nombres de [[variable|variables]] de [[PROLOG]] es un lenguaje regular.
+Demuestre que el lenguaje conformado por los nombres de [[variable|variables]] de PROLOG es un lenguaje regular.
 Primero debe recordarse que un nombre de variable PROLOG viene dada por la forma:
-''cualquier palabra que comience con una letra mayúscula seguida o no de combinaciones de letras, cifras o subrayados o que comience con al menos un subrayado seguido o no de cualquier secuencia de alfanuméricos o subrayados''.
+''Cualquier palabra que comience con una letra mayúscula seguida o no de combinaciones de letras, cifras o subrayados o que comience con al menos un subrayado seguido o no de cualquier secuencia de alfanuméricos o subrayados''.
 Cada de las siguientes construcciones son equivalentes en virtud de la definición dada antes:
@@ Línea 43: / Línea 43: @@
 La existencia y formalización de los lenguajes regulares (LR) y su vinculación con otros artefactos lingüísticos-matemáticos ya bien formalizados, estudiados e incluso llevados a la práctica ha sido de vital importancia en el ulterior desarrollo de los mecanismos de procesamiento de lenguajes de computadora, fundamentalmente en los analizadores lexicográficos gracias a la posibilidad de derivar el reconocimiento de los LR mediante autómatas finitos que son fáciles de implementar computacionalmente con mecanismos simples y rápidos, óptimos en la obtención de ''parsers'' veloces y robustos que a su vez le ofrecen a los desarrolladores información detallada de los errores léxicos, sintácticos e incluso advierten sobre errores semánticos.
-Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos [[Lenguaje de programación de propósito general|lenguajes de propósito general]] modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los ''tókenes'' o partículas lexicales del [[código fuente]] como fase del proceso completo de interpretación o compilado, según sea el caso.
+Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos Lenguaje de programación de propósito general modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los ''tókenes'' o partículas lexicales del [[código fuente]] como fase del proceso completo de interpretación o compilado, según sea el caso.
-A manera de ilustración en el caso del ejemplo anterior vemos la siguiente [[función]] [[Python]] que a partir de cualquiera de los elementos formalizadores del LR correspondiente permite decidir si un texto ''w'' es una variable PROLOG:
+A manera de ilustración en el caso del ejemplo anterior vemos la siguiente función Python que a partir de cualquiera de los elementos formalizadores del LR correspondiente permite decidir si un texto ''w'' es una variable PROLOG:
 <pre>
@@ Línea 68: / Línea 68: @@
 Pero el alcance de los LR no se queda en el mundo de la [[compilación]] de lenguajes de ordenador como se ve en el siguiente ejemplo.
-===Ejemplo 2.===
+===Ejemplo 2===
 En un acuario de [[Miami]] se entrenan las capacidades intelectuales de los [[Delfín|delfines]] en cautiverio y tiene especial importancia los resultados que tiene uno de los ejemplares quien ha aprendido a reconocer cantidades pares a partir de imagenes de peces, llegando a distinguir cuando hay un número par o no de peces en la imagen. Muestre que las imágenes de cantidad de peces pares es un lenguaje regular que puede percibir el delfín.
@@ Línea 85: / Línea 85: @@
 * [[Lenguaje libre de contexto]].
-==Fuentes.==
+==Fuentes==
-# Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
+*Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
-# Conferencias de la Asignatura "Compilación 1" del [[Departamento de Ciencias de la Computación de la Universidad de Oriente|Departamento de Ciencias de la Computación]] de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
+*Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
-# [http://es.wikipedia.org/wiki/Lenguaje_regular Lenguajes regulares en Wikipedia]. Consultado el [[23 de febrero]] de [[2012]].
+*Artículo [http://es.wikipedia.org/wiki/Lenguaje_regular Lenguajes regulares]. Consultado el [[23 de febrero]] de [[2012]].
 [[Categoría:Lingüística]][[Categoría:Matemáticas]][[Categoría:Informática]]

@@ Línea 5: / Línea 5: @@
 Son los [[Lenguaje formal|lenguajes formales]] más simples, con los mecanismos de representación y reconocimiento más estudiados. Su aplicación práctica en la teoría y construcción de [[Intérprete|intérpretes]] y [[Compilador|compiladores]] de [[Lenguaje de programacion|lenguajes de programación]] o de [[Lenguaje de especifcación|especificación]] o [[Lenguaje de formato|formato de información]], especialmente como microcomponentes del [[analizador lexicográfico]] que detecta los [[Token|tókenes]] como [[Constante numérica|constantes numéricas]], [[Cadena de texto|cadenas de texto]], operadores, palabras reservadas (''keywords''), separadores, etc. Pero también se puede apreciar su uso en [[Máquina expendedora|máquinas expendedoras]], [[Teléfono público|teléfonos públicos]], [[Calculadora|calculadoras]] y otros artefactos electromecánicos.
-==Definición.==
+==Definiciones.==
 Se dice que un lenguaje es regular si y sólo si se cumple cualquiera de las siguientes proposiciones:
 * Tiene al menos una [[gramática regular]] ''G'' que lo produce.

@@ Línea 10: / Línea 10: @@
 * Puede ser reconocido por un [[autómata finito]] ''A''.
 * Existe una [[expresión regular]] ''E<sub>r</sub>'' que representa a todas las cadenas de ''L''.
 [[Archivo:Jerarquia_Chomsky.gif|center|Ubicación de los LR en la Jerarquía de Chomsky]]

Lenguaje regular - Historial de revisiones

Javiermartin jc: Texto reemplazado: «» por «»

UrbanoNoris3 jc en 13:53 28 feb 2012

Jhonlier12017 jc.hlg: /* Definiciones. */

Jhonlier12017 jc.hlg: /* Definición. */

Jhonlier12017 jc.hlg: /* Definición. */

Jhonlier12017 jc.hlg: Página creada con '{{Definición|nombre=Lenguaje regular|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 3, reconocibles con [[Autómata finit...'

Javiermartin jc: Texto reemplazado: «
» por «»