Expresiones regulares, gramática regular y lenguajes regulares

Como se discutió en Jerarquía de Chomsky , los lenguajes regulares son los tipos de lenguajes más restringidos y son aceptados por autómatas finitos.
 
Expresiones
regulares Las expresiones regulares se utilizan para indicar lenguajes regulares. Una expresión es regular si:

• ɸ es una expresión regular para el lenguaje regular ɸ.
• ɛ es una expresión regular para el lenguaje regular {ɛ}.
• Si a ∈ Σ (Σ representa el alfabeto de entrada ), a es una expresión regular con lenguaje {a}.
• Si a y b son expresiones regulares, a + b también es una expresión regular con lenguaje {a,b}.
• Si a y b son expresiones regulares, ab (concatenación de a y b) también es regular.
• Si a es una expresión regular, a* (0 o más veces a) también es regular.

Expresión regular	Idiomas regulares
conjunto de vocales	( un ∪ mi ∪ yo ∪ o ∪ tu )	{a, e, yo, o, u}
a seguido de 0 o más b	(ab * )	{a, ab, abb, abbb, abbbb,….}
cualquier no de vocales seguidas de cualquier no. de consonantes	v * .c * (donde v – vocales y c – consonantes)	{ ε , a ,aou, aiou, b, abcd…..} donde ε representa una string vacía (en el caso de 0 vocales y o consonantes)

 
Gramática regular: una gramática es regular si tiene reglas de la forma A -> a o A -> aB o A -> ɛ donde ɛ es un símbolo especial llamado NULL.
 
Lenguajes regulares: un lenguaje es regular si se puede expresar en términos de expresiones regulares.
 
Propiedades de clausura de la
unión de lenguas regulares: Si L1 y Si L2 son dos lenguas regulares, su unión L1 ∪ L2 también será regular. Por ejemplo, L1 = {a ⁿ | norte ≥ 0} y L2 = {b ^norte | norte ≥ 0}
L3 = L1 ∪ L2 = {un ^norte ∪ segundo ^norte | n ≥ 0} también es regular.
Intersección: Si L1 y Si L2 son dos lenguas regulares, su intersección L1 ∩ L2 también será regular. Por ejemplo,
L1= {a ^msegundo ^norte | norte ≥ 0 y metro ≥ 0} y L2= {un ^{metro segundo norte} ∪ segundo ^norte un ^metro | norte ≥ 0 y metro ≥ 0}
L3 = L1 ∩ L2 = {un metro ^{segundo norte} | n ≥ 0 y m ≥ 0} también es regular.
Concatenación: Si L1 y L2 son dos idiomas regulares, su concatenación L1.L2 también será regular. Por ejemplo,
L1 = {a ⁿ | norte ≥ 0} y L2 = {b ^norte | norte ≥ 0}
L3 = L1.L2 = {un ^metro . segundo ^norte | m ≥ 0 y n ≥ 0} también es regular.
Cierre Kleene: Si L1 es un lenguaje regular, su cierre Kleene L1* también será regular. Por ejemplo,
L1 = (a ∪ b)
L1* = (a ∪ b)*
Complemento: Si L(G) es lenguaje regular, su complemento L'(G) también lo será. El complemento de un idioma se puede encontrar restando las strings que están en L(G) de todas las strings posibles. Por ejemplo,
L(G) = {a ⁿ | norte > 3}
L'(G) = {un ^norte | n <= 3}

Nota: dos expresiones regulares son equivalentes si los lenguajes generados por ellas son iguales. Por ejemplo, (a+b*)* y (a+b)* generan el mismo idioma. Cada string generada por (a+b*)* también es generada por (a+b)* y viceversa.

¿Cómo resolver problemas sobre expresiones regulares y lenguajes regulares?

Pregunta 1: ¿Cuál de los siguientes idiomas sobre el alfabeto {0,1} está descrito por la expresión regular?
(0+1)*0(0+1)*0(0+1)*
(A) El conjunto de todas las strings que contienen la substring 00.
(B) El conjunto de todas las strings que contienen como máximo dos 0.
(C) El conjunto de todas las strings que contienen al menos dos 0.
(D) El conjunto de todas las strings que comienzan y terminan con 0 o 1.

Solución: la opción A dice que debe tener la substring 00. Pero 10101 también es parte del lenguaje pero no contiene 00 como substring. Entonces no es la opción correcta.
La opción B dice que puede tener un máximo de dos 0, pero 00000 también es parte del lenguaje. Entonces no es la opción correcta.
La opción C dice que debe contener al menos dos 0. En la expresión regular, hay dos 0 presentes. Así que esta es la opción correcta.
La opción D dice que contiene todas las strings que comienzan y terminan con 0 o 1. Pero también puede generar strings que comienzan con 0 y terminan con 1 o viceversa. Entonces no es correcto.
 
Pregunta 2: ¿Cuál de los siguientes idiomas es generado por una gramática dada?
S -> comoS | bS | ∊
(A) {un ^norte segundo ^metro | n,m ≥ 0}
(B) {w ∈ {a,b}* | w tiene igual número de a y b}
(C) {a ⁿ | norte ≥ 0} ∪ {segundo ^norte | norte ≥ 0} ∪ {un norte ^{segundo norte} | norte ≥ 0}
(D) {a,b}*

Solución: la opción (A) dice que tendrá 0 o más a seguidos de 0 o más b. Pero S -> bS => baS => ba también es parte del lenguaje. Entonces (A) no es correcto.
La opción (B) dice que tendrá igual no. de a y b. Pero Pero S -> bS => b también es parte del lenguaje. Entonces (B) no es correcto.
La opción (C) dice que tendrá 0 o más a o 0 o más b o a seguidas de b. Pero como se muestra en la opción (A), ba también es parte del lenguaje. Entonces (C) no es correcto.
La opción (D) dice que puede tener cualquier número de a y cualquier número de b en cualquier orden. Entonces (D) es correcta.
 
Pregunta 3: La expresión regular 0*(10*)* denota el mismo conjunto que
(A) (1*0)*1*
(B) 0 + (0 + 10)*
(C) (0 + 1)* 10 (0 + 1)*
(D) ninguno de estos

Solución: Dos expresiones regulares son equivalentes si los lenguajes generados por ellas son iguales.
La opción (A) puede generar todas las strings generadas por 0*(10*)*. Entonces son equivalentes.
La string nula de la opción (B) no puede generarse con los idiomas dados, pero 0*(10*)* sí. Entonces no son equivalentes.
La opción (C) tendrá 10 como substring, pero 0*(10*)* puede o no. Entonces no son equivalentes.
 

Pregunta 4: La expresión regular para el idioma que tiene los alfabetos de entrada a y b, en el que dos a no se juntan:
(A) (b + ab)* + (b +ab)*a
(B) a(b + ba) )* + (b + ba)*
(C) ambas opciones (A) y (B)
(D) ninguna de las anteriores

Solución:
La opción (C) que indica ambas opciones (A) y (B) es la expresión regular correcta para la pregunta planteada.
El idioma de la pregunta se puede expresar como L={&epsilon,a,b,bb,ab,aba,ba,bab,baba,abab,…}.

En la opción (A), ‘ab’ se considera el bloque de construcción para encontrar la expresión regular requerida.(b + ab)* cubre todos los casos de strings generadas que terminan en ‘b’.(b + ab)*a cubre todos los casos de strings generadas que terminan en a.

Aplicando una lógica similar para la opción (B), podemos ver que la expresión regular se deriva considerando ‘ba’ como el bloque de construcción y cubre todos los casos de strings que comienzan con a y que comienzan con b.

Este artículo ha sido aportado por Sonal Tuteja.
 
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.