edición: Renny Centeno DISEÑO: Ana Fernández

Núcleo De Monagas Curso especialidad de grado Universidad De Oriente

Editorial Desde las oficinas de Java Conocimiento queremos agradecerte por

acompañarnos en esta edición, si nos has seguido desde la primera

edición o bien esta es tu primera experiencia con la revista,

esperamos satisfacer tu curiosidad tecnológica y animarte a

iniciarte e indagar más en cada uno de los temas que tocamos, esta

semana ha sido dura y tortuosa para el equipo de Java Conocimiento,

no ha sido fácil desglosar el tema que se abordara en esta edición,

a pesar de que algunos de los miembros del equipo tenían

conocimiento sobre autómatas este no es el tema en cuestión aunque

si guarda estrecha relación con este que nos es más como comprobar

que un lenguaje es regular.

un lenguaje regular es formal, formal se

refiere a que posee un conjunto de reglas

y condiciones que lo hacen ser considerado

como correcto o “protocolar” para que

los seres humanos se comuniquen con este,

por obvias razones se tuvo la necesidad

de trasmitirle estos lenguajes a una

máquina para que esta realízala sus diferentes funciones, ya que de

otra manera seria imposible para un ser humano indicarle a las

maquinas ¿Qué hacer?, estos lenguajes regulares son representados

en las maquinas mediante autómatas, el diseño del autómata

definirá los lenguajes que aceptara y por ende los que se

convertirán en lenguajes regulares de ese autómata en específico,

como nos podemos dar cuenta es impetuoso que hablemos un poco de

los autómatas y de los lenguajes regulares para pasar a explicar

los diferentes métodos que nos permitirán saber si un lenguaje es

regular o no, esperamos que te sea de gran ayuda y enriquecimiento

intelectual el contenido que trataremos, recordando que en Java

conocimiento trabajamos para ofrecerle la mejor información a

nuestros lectores.

Contenido

Introduccion…………………………………5 Lenguaje formal vs lenguaje informal……………………………………………6 Ligero vistaso a los automatas…………………8 Lenguaje regular………………………………………10 Como demostrar que un lenguaje no es regular…………………………………………………………12 Un poco de humor………………………………………………17 Referencias bibliograficas…………………………………………18

Introducción El hombre tiene en este planeta no menos de 2000 mil años depende de

la perspectiva que se le vea claro, religión y ciencia no van de la

mano pero algo en que deben coincidir es que el hombre nació con la

necesidad de poder comunicarse con quienes lo rodeaban, a partir de

ahí surgieron muchos avances en la humanidad hasta tener cantidad

de lenguajes, estos lenguajes puede ser informales(coloquiales) o

formales, los formales son la manera eficiente en que un lenguaje

sirve para que los individuos se comuniquen.

Las maquinas

necesitan un lenguaje

al igual que los

humanos para poder

comunicarse en este

caso con los seres

humanos que son los

que le indican lo que

deben ejecutar, he

aquí donde entran los

lenguajes regulares

y los autómatas como

conceptos importantes para plasmar la comunicación dentro de las

maquinas, los autómatas permiten representar los lenguajes

formales dentro de una máquina, esto trae consigo diferentes

aplicaciones como representar los procesos de un software de

manera eficiente, los lenguajes que acepta un autómata dependerá

del tipo de autómata y de cómo este diseñado(para que fin).

Resulta crucial conocer y manejar los mecanismos o técnicas con

las cuales cuentan los autómatas para descartar que lenguajes y

cuales no pertenecen a ellos, y así saber con precisión los

lenguajes regulares que aceptan los diferentes autómatas.

Lenguaje formal vs lenguaje informal

Cada hablante maneja su forma de

expresarse dependiendo de la situación

comunicativa en que se encuentra,

dependiendo de qué quiere decir, a quién

se dirige, para qué y con qué fin.

Así, al hablar por teléfono con un amigo,

usamos un lenguaje cotidiano, relajado y

lleno de muletillas. Pero si debemos

hablar con un adulto, nuestro lenguaje se

vuelve más estructurado y dejamos las

muletillas de lado.

De esta misma forma, no es lo mismo

escribir una carta a un amigo contándole

tus vacaciones, que escribir una carta de

felicitaciones al diario.

Existen dos formas comunicarse:

la informal y la formal.

El lenguaje informal

Como se señaló en la introducción, este

tipo de lenguaje es utilizado cuando

conversamos con nuestros pares y con

gente con la cual tenemos mucha

confianza. Ejemplo: entre amigos,

familiares, compañeros de cursos, etc. Es

el lenguaje que utilizamos diariamente y

que se caracteriza por ser expresivo y

emotivo, porque lo empleamos con gente

cercana a nosotros, lo que también nos

permite utilizar otros elementos como los

apodos, los diminutivos, etc.

Características del lenguaje informal

Se repite mucho una misma idea.

Utilización de muletillas, que son

palabras o frases que repite mucho

una persona.

Por ejemplo: cachai, ya po, bueno, po,

etc.

Utilización de modismos, frases o

palabras que tienen significado y

que se usan en un lugar

determinado.

Lenguaje formal vs lenguaje informal

Por ejemplo: altiro, irse al chancho,

latero, etc.

Poco uso de vocabulario, siempre

se utilizan las mismas palabras.

Por ejemplo: "Ana hizo las tareas,

después hizo su cama y, al final, hizo

deporte.

Frases cortas e inconclusas.

Por ejemplo: "Entonces, eso fue po…"

Las frases u oraciones no están

bien organizadas.

Mucha repetición de palabras.

El lenguaje formal

Este tipo de lenguaje es el que se utiliza

en situaciones que son más serias y

formales, y donde los hablantes,

generalmente, tienen una relación lejana.

Ejemplo: doctor-paciente, jefe-empleado,

etc.

Este lenguaje no lo utilizamos

diariamente, sino que sólo en ciertas

oportunidades.

Características del lenguaje formal

Correcta pronunciación.

Adecuado y variado vocabulario.

Utilización de oraciones o frases

bien construidas.

No se usan las muletillas,

vulgarismos, modismos.

Discurso fluido y continuo.

Se utilizan frases u oraciones más

largas.

No hay evidentes repetición de

palabras.

No es redundante, se entrega la

información de una sola vez.

La información está bien

estructurada y tiene un orden

lógico.

No hay omisiones, las frases están

completas.

Ligero vistazo a los autómatas

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas

en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de

una serie de estados de acuerdo a una función de transición (que puede ser expresada como

una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al

autómata a qué estado cambiar dados unos determinados estados y símbolos.

La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense

en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora

del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una

vez la entrada se ha agotado, el autómata se detiene.

Dependiendo del

estado en el que el

autómata finaliza

se dice que este ha

aceptado o

rechazado la

entrada. Si éste

termina en el

estado "acepta", el

autómata acepta la

palabra. Si lo hace

en el estado

"rechaza", el

autómata rechazó

la palabra, el

conjunto de todas

las palabras

aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Los conceptos básicos de símbolos, palabras, alfabetos y strings son comunes en la mayoría

de las descripciones de los autómatas. Estos son:

Símbolo

Un dato arbitrario que tiene algún significado a o efecto en la máquina. A estos símbolos

también se les llama "letras" o "átomos".1

Ligero vistazo a los autómatas

Palabra

Una cadena finita formada por la concatenación de un número de símbolos.

Alfabeto

Conjunto finito de símbolos. Un alfabeto se indica normalmente con , que es

el conjunto de letras en un alfabeto.

Lenguaje

Un conjunto de palabras, formado por símbolos en un alfabeto dado. Puede ser infinito.

Clausura de Kleene

Un lenguaje se puede considerar como un subconjunto de todas las posibles palabras. El

conjunto de todas las palabras puede, a su vez, ser considerado como el conjunto de todas

las posibles concatenaciones de cadenas. Formalmente, este conjunto de todas las cadenas

se llama en inglés free monoid. Se indica cómo , y el superíndice * se llama la estrella de

Kleene.

Lenguajes regulares

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áticas

regulares, autómatas finitos o expresiones

regulares.

Son los 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érpretes y

compiladores de lenguajes de

programación o de especificación o

formato de información, especialmente

como microcomponentes del analizador

lexicográfico que detecta los tókenes

como constantes numéricas, cadenas de

texto, operadores, palabras reservadas

(keywords), separadores, etc. Pero

también se puede apreciar su uso en

máquinas expendedoras, teléfonos

públicos, calculadoras y otros artefactos

electromecánicos.

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 Er

que representa a todas las cadenas

de L.

En la imagen Noam Chomsky

Dentro de la Jerarquía de Chomsky se

refiere a los lenguajes de tipo 3, el

subconjunto de lenguajes formales más

Lenguajes regulares

restringido dentro de la jerarquía, como se

ve en la imagen.

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 ó

LR (T) es:

1. El lenguaje vacío {}.

2. El lenguaje conformado por la

cadena vacía Lenguaje trivial.gif o

lenguaje trivial.

3. Un lenguaje {x} conformado por

un único símbolo x de T.

4. Si A y B son lenguajes regulares

sobre T, entonces AB

(Concatenación de lenguajes), A

unión B. (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.

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 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.

Cómo demostrar que un lenguaje no es regular

La clase de lenguajes conocida como

lenguajes regulares tiene como mínimo

cuatro descripciones diferentes. Son los

lenguajes aceptados por los AFD, los

AFN y los AFN-ε ; también son los

lenguajes definidos por las expresiones

regulares.

No todo lenguaje es un lenguaje regular.

En esta sección vamos a presentar una

potente técnica, conocida como el “lema

de bombeo”, que nos va a permitir

demostrar que determinados lenguajes no

son regulares.

Además proporcionaremos varios

ejemplos de lenguajes no regulares y

también veremos cómo el lema de

bombeo puede emplearse junto con las

propiedades de clausura de los lenguajes

regulares para demostrar

El lema de bombeo para los lenguajes

regulares

Consideremos el lenguaje = {0n1n | n

≥ 1}. Este lenguaje contiene las cadenas

01, 0011, 000111, etc., que constan de

uno o más ceros seguidos de un número

igual de unos. Establecemos que L01 no

es un lenguaje regular. El argumento

intuitivo es que si fuera regular,

entonces sería el lenguaje de algún

AFD A, que tendría un determinado

número de estados, digamos k estados.

Imagine que este autómata recibe k ceros

como entrada. Después de recibir los k+1

prefijos de la entrada: ε ,0,00, . . . ,0k se

encontrará en un cierto estado.

Dado que sólo existen k estados distintos,

el principio del juego de las sillas nos

dice que después de leer dos prefijos

diferentes, por ejemplo, 0i y 0j, A tiene

que encontrarse en el mismo estado, por

ejemplo q.

Cómo demostrar que un lenguaje no es regular

Sin embargo, en lugar de esto, suponemos

que después de leer i o j ceros, el

autómata A comienza a recibir unos como

entrada. Después de recibir i unos, debe

aceptar si previamente ha recibido i ceros,

pero no si ha recibido j ceros. Puesto que

estaba en el estado q cuando comenzaron

a llegar unos, no puede “recordar” si

había recibido i o j ceros, por lo que

podemos “engañar” a A y hacerle cometer

un error: aceptar cuando no debe hacerlo

o no aceptar cuando debería hacerlo.

El argumento anterior es de carácter

informal, pero puede precisarse. Sin

embargo, puede llegarse a la misma

conclusión, que el lenguaje no es un

lenguaje regular, utilizando un resultado

general de la forma siguiente.

(El lema de bombeo para lenguajes

regulares) Sea L un lenguaje regular.

Existe entonces una constante n (que

depende de L) tal que para toda cadena w

perteneciente a L con |w| ≥ n, podemos

descomponer w en tres cadenas, w = xyz,

tales que:

1. y ≠ ε.

2. |xy| ≤ n.

3. Para todo k ≥ 0, la cadena

también pertenece a L.

Es decir, siempre podemos hallar una

cadena no vacía y no demasiado alejada

del principio de w que pueda

“bombearse”; es decir, si se repite y

cualquier número de veces, o se borra (el

caso en que k = 0), la cadena resultante

también pertenece al lenguaje L.

DEMOSTRACIÓN: Supongamos que L

es regular. Entonces L =L(A) para algún

AFD A. Supongamos que A tiene n

estados. Consideremos ahora cualquier

cadena w de longitud n o mayor, por

ejemplo w = a1a2 · · ·am, donde m ≥ n y

cada ai es un símbolo de entrada. Para i =

0,1, . . . ,n definimos el estado pi como δ

(q0,a1a2 · · ·ai), donde δ es la función de

transición de A y q0 es el estado inicial de

A. Es decir, pi es el estado en que se

encuentra A después de leer los primeros i

símbolos de w. Observe que p0 = q0.

Por el principio del juego de las sillas, no

es posible que los n+1 pi para i = 0,1, . . .

,n sean diferentes, ya que sólo existen n

estados distintos. Por tanto, podemos

determinar dos enteros distintos i y j, con

0 ≤ i< j ≤ n, tales que pi = pj . Ahora

podemos descomponer w = xyz como

sigue:

1. x = a1a2 · · ·ai.

2. y = ai+1ai+2 · · ·aj .

3. z = aj+1aj+2 · · ·am.

Toda cadena de longitud mayor que el

número de estados hace que un estado se

repita

El lema de bombeo como un juego

entre adversarios

El teorema cuya proposición implica

varias alternativas de cuantificadores

“para todo” y “existe” puede interpretarse

como un juego entre dos personas. El

lema de bombeo es un ejemplo

importante de este tipo de teorema, ya

que implica cuatro identificadores

diferentes:

“para todos los lenguajes L existe n tal

que para toda w perteneciente a L con |w|

≥ n existe xyz igual a w tal que · · · ”.

Podemos interpretar la aplicación del

lema de bombeo como un juego en el

que:

1. El jugador 1 selecciona el lenguaje L

para demostrar que no es regular.

2. El jugador 2 selecciona n, pero no

revela al jugador 1 lo que vale n; el

jugador 1 debe plantear el juego para

todos los n posibles.

3. El jugador 1 selecciona w, que puede

depender de n y cuya longitud tiene que

ser al menos igual a n.

4. El jugador 2 divide w en x, y y z,

teniendo en cuenta las restricciones que se

estipulan en el lema de bombeo; y _=ε y

|xy| ≤ n. De nuevo, el jugador 2 no dice al

jugador 1 qué valores tienen x, y y z,

aunque debe respetar las restricciones.

5. El jugador 1 “gana” eligiendo un valor

de k, que puede ser una función de n, x,y

y z, tal que no pertenezca a L.

Es decir, x nos lleva a pi una vez; y nos

lleva desde pi a pi de nuevo (ya que pi

también es pj) y z es el restode w. Las

relaciones entre las cadenas y los estados

se muestran en la Figura 4.1. Observe que

x puede estar vacía en el caso de que i =

0. También z puede estar vacía si j = n =

m. Sin embargo, y no puede estar vacía,

ya que i es estrictamente menor que j.

Consideremos ahora lo que ocurre si el

autómata A recibe la entrada para

cualquier k ≥ 0. Si k = 0, entonces el

autómata va desde el estado inicial q0

(que también es p0) hasta pi para la

entrada x. Puesto que pi también es pj , al

leer la entrada z, A tiene que ir desde pi

hasta el estado de aceptación, por tanto, A

acepta xz.

Si k > 0, entonces A va desde q0 hasta pi

para la entrada x, va en círculo desde pi

hasta pi k veces para la entrada yk, y

luego pasa al estado de aceptación para la

entrada z. Por tanto, para cualquier k ≥ 0,

A también acepta ; es decir,

pertenece a L.

Aplicaciones del lema de bombeo

Veamos algunos ejemplos de cómo se

utiliza el lema de bombeo. En cada caso,

propondremos un lenguaje y utilizaremos

el lema de bombeo para demostrar que el

lenguaje no es regular

Ejemplo 1

Demostremos que el lenguaje Leq que

consta de todas las cadenas con un

número igual de ceros que de unos (en

ningún orden en particular) no es un

lenguaje regular. En función del “juego

de dos adversarios” descrito en el

recuadro “El lema de bombeo como un

juego entre adversarios”, nosotros

seremos el jugador 1 y debemos

enfrentarnos con cualquier elección que

haga el jugador 2. Supongamos que n es

la constante que existiría si Leq fuera

regular, de acuerdo con el lema de

bombeo; es decir, el “jugador 2” elige n.

Nosotros seleccionamos w = 0n1n, es

decir, n ceros seguidos de n unos, una

cadena que seguramente pertenece a Leq.

Ahora el “jugador 2” divide w en xyz.

Todo lo que sabemos es que y _= ε y |xy|

≤ n. Sin embargo, dicha información es

muy útil y “ganamos” de la forma

siguiente. Dado que |xy| ≤ n y que xy

procede del principio de w, sabemos que

x e y constan sólo de ceros. El lema de

bombeo nos dice que xz pertenece a Leq,

si Leq es regular.

Esta conclusión corresponde al caso en

que k = 0 en el lema de bombeo.1 Sin

embargo, xz tiene n unos, ya que todos los

unos de w están en z. Pero xz también

tiene menos de n ceros, porque hemos

perdido los ceros de y.

Puesto que y _= ε , sabemos que no puede

haber más de n−1 ceros entre x y z. Por

tanto, después de suponer que Leq es un

lenguaje regular, hemos demostrado un

hecho que sabemos que es falso, que xz

pertenece a Leq.

Tenemos una demostración por reducción

al absurdo del hecho de que Leq no es

regular.

Ejemplo 2

Vamos a demostrar que el lenguaje Lpr, que consta de todas las cadenas de unos cuya

longitud es un número primo no es un lenguaje regular. Supongamos que lo fuera. Entonces

existiría una constante n que satisfaría las condiciones del lema de bombeo. Consideremos

un número primo p ≥ n+2; que debe existir ya que hay un número infinito de primos. Sea w

= 1p.

Por el lema de bombeo, podemos dividir w=xyz tal que y _=ε y |xy| ≤ n. Sea |y|=m.

Entonces |xz|= p−m.

Consideremos ahora la cadena xyp−mz, que debe pertenecer a Lpr de acuerdo con el tema

de bombeo, si Lpr es realmente regular. Sin embargo:

|xyp−mz| = |xz|+(p−m)|y|= p−m+(p−m)m= (m+1)(p−m) Parece que |xyp−mz| no es un

número primo, ya que tiene dos factores: m+1 y p−m. Sin embargo, tenemos que

comprobar que ninguno de estos factores es igual a 1, ya que entonces (m+1)(p−m) podría

ser primo.

Pero m+1 > 1, ya que y _=ε implica que m ≥ 1. Además, p−m > 1, ya que hemos elegido p

≥ n+2 y m ≤ n puesto que:

m = |y| ≤ |xy| ≤ n

Por tanto, p−m ≥ 2.

De nuevo, hemos comenzado asumiendo que el lenguaje en cuestión era regular y hemos

llegado a una contradicción demostrando que no pertenece al lenguaje una cadena que el

lema de bombeo exigía que perteneciera al lenguaje.

Por tanto, concluimos que Lpr no es un lenguaje regular.

Bibliografía Contenido:

http://www.ecured.cu/, Lenguaje regular, 2015, recuperado de:

http://www.ecured.cu/index.php/Lenguaje_regular

http://www.icarito.cl/, Lenguaje formal e informal, 2010, recuperado de:

http://www.icarito.cl/enciclopedia/articulo/primer-ciclo-basico/lenguaje-y-

comunicacion/comunicacion-oral/2010/03/50-8919-9-lenguaje-formal-e-informal.shtml

http://es.wikipedia.org/, Teoría de autómatas, 2015, recuperado de:

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_aut%C3%B3matas

Hopcroft John, Rajeev Motwani y Ullman Jeffrey (2007), Introducción a la teoría de

autómatas lenguajes y computación (Tercera Edición), Madrid.

Imágenes:

jornalggn.com.br/, Chomsky não acha inevitável o fim da mídia impressa, 2015, recuperado

de: http://jornalggn.com.br/blog/antonio-ateu/chomsky-nao-acha-inevitavel-o-fim-da-

midia-impressa

http://aprendizdetecnologias.blogspot.com/, Signos básicos en las expresiones regulares y

su significado, 2009, recuperado de:

http://aprendizdetecnologias.blogspot.com/2009/03/signos-basicos-en-las-expresiones.html

enpositivo.com, La importancia del lenguaje,2015,recuperado de:

http://enpositivo.com/2013/02/lenguajes-y-actitudes/

URBIOLA,Idi,4 CONSEJOS PARA QUE TERMINES LO QUE EMPIEZAS,2013,

recuperado de: https://www.belelu.com/2013/12/4-consejos-para-que-termines-lo-que-

empiezas/

https://sites.google.com, Autómatas, S.F. , recuperado de:

https://sites.google.com/site/almadeherrero/d-objetos/electricidad/proyectos-

mecanicos/automatas

http://mykingdomforafilm.blogspot.com/,Escenas míticas del cine, 2014, recuperado de:

http://mykingdomforafilm.blogspot.com/2015_01_01_archive.html

http://www.chistes21.com/, Mejores chistes del mes,2014, recuperado de:

http://www.chistes21.com/top/

http://www.blogodisea.com/, La autómata maría Antonieta,2015, recuperado de:

http://www.blogodisea.com/tocadora-del-timpano-automata-maria-antonieta.html

revistahistoriaparatodos.wordpress.com, Editorial,2015, recuperado de:

https://revistahistoriaparatodos.wordpress.com/2015/03/11/editorial-tucuman-indefenso/

CHEREZOV, Killic, 3d render puntos blancos Mano aislada sobre un fondo blanco, S.F. ,

recuperado de: http://es.123rf.com/photo_18935466_3d-white-man-points-hand-isolated-

render-on-a-white-background.html