teoria computacional

Compiladores e Interprete s

EPCI - UNPRG

EXPRESIONES REGULARES
Son entes formales o estructuras matemáticas utilizadas para es pecificar parámetros de formación de
c omponentes léxicos.
Las Expresiones Regulares denotan o representan lenguajes.
Fueron desarrollados en los años ’60 por Klene.
Se tienen las siguientes reglas E.R. para la represent ación del lenguaje, definidas sobre
1.2.
3.
4.
5.
6.
7.

= { a, b }

Sea a una expresión regular denota un lenguaje regular o una cadena.
Sea ab una expresión regular esta denota un lenguaje regular
L(ab) = L(a) L(b) = {a}{b } = {ab}
Sea a b una ex presión regular esta denota un lenguaje regular
L(a b) = L(a) ∪ L(b) = {a} ∪ {b} = {a,b}
Sea a* una expresión regular esta denota un lenguaje regular
L(a*) = L(a)* = (L(a))*= ({a})* = {a}* = { , a, aa, aaa, ...}
+
Sea a una expresión regular esta denota un lenguaje regular
+
+
+
+
+
L(a ) = L(a) = (L(a)) = ({a}) = {a} = {a, aa, aaa, ...}
Sea una expresión regular esta denota un lenguaje regular
L( ) = { }
En general, sea ‘r’ una E. R. esta denota un L. R. L® siendo ‘r’ una E.R. compuesta po e las E.R.
definidas previament e, se utilizan dichas reglaspara obtener el lenguaje asociado a ella (r).

Ejemplo:
Hallar los lenguajes asociados a las siguientes expresiones regulares:
+

1.
2.
3.
4.
5.

(a b*) a bb sobre = { a, b }
+
+
(xy* mn) (mn* mn )xy mn sobre = { x y, mn }
+
(((0* 1*)*) 0 1*) 01 sobre = { 0, 1 }
+
+
((ab cd*) (cd* ab)*) abcd s obre = { ab,cd }
++
(((a b)* b ) )* a b*) ab sobre = { a,b }

1.

(a b*) a bbsobre = { a, b }
+
L((a b*) a bb)
+
L(a b*) L(a )L(b)L(b)
+
L(a) L(b*) L(a )L(b)L(b)
+
L(a) L(b)* L(a) L(b)L(b)
+
L(a) (L(b))* (L(a)) L(b)L(b)
+
{a} ∪ ({b})* ({a}) {b}{b}
{a} ∪ { ,b, bb,... } {a,aa, aaa,…} {bb}
{ ,a,b,bb,...} {abb, aabb,…}
{abb,aabb,…babb,…}

2.

(xy* mn) (mn* mn )xy mn sobre = { x y, mn }
+
+
L((xy* mn) (mn* mn )xy mn)
+
+
L(xy* mn) L(mn* mn ) L(xy ) L(mn)
++
L(xy*) L(mn) L(mn*) L(mn ) L(xy ) L(mn)
+
(L(xy))* L(mn) (L(mn))* ( L(mn)) L(mn)
+
+
({xy}* ∪ {mn}) ({mn}* ∪{mn }) {xy } {mn}
{ , xy, xyxy,…} ∪ {mn} { ,mn, mnmn,…} ∪ {mn, mnmn,…} {xy, xyxy,…} {mn}
{ , xy, xyxy,…, mn} { ,mn, mnmn,…} {xymn, xyxymn,…}
{ , xy, xyxy,…, mn} {xymn, xyxymn,…,mnxymn, mnxyxymn,… }
{xymn, xyxymn,…,mnxymn, mnxyxymn,…xyxymn,xyxyxymn,…,xymnxymn, xymnxyxymn,…}

+Ing. Luis Reyes Lescano

+

+

1

Compiladores e Interprete s

EPCI - UNPRG

+

3.

(((0* 1*)*) 0 1*) 01 sobre = { 0, 1 }
+
L((((0* 1*)*) 0 1*) 01)
+
L((((0* 1*)*) ) L( 0 1*)) L( 0) L(1)
+
(((L(0*) L(1)*)*) L (0) L(1)*) L( 0) L(1)
+
((((L(0))* (L(1))*)*) L (0) L(1)*) L( 0) L(1)
+
+
((({0}*∪ {1}*)* ) {0} ∪ { 1} ) {0} {1}
(({ , 0, 00,…} ∪ { , 1, 11,...})* {0} ∪ { 1,11,... }) {01}
{ , 0, 00,…,1, 11,...}* {0, 1, 11...} {01}
{ , 0, 00,…,1, 11,...} {0, 1, 11...} { 01}
{0, 1, 11,...00, 01, 011,...,000, 001,...,10,...} {01}
{001, 101, 1101,..., 0001, 0 0101, 0011,..., 00001, 00101,...}

4.

((ab cd*) (cd* ab)*) abcd s obre = { ab,cd }
+
+
L(((ab cd*) (cd* ab)*) abcd )
+
+
L(ab cd*) L(cd* ab)* L(ab) L(cd )
+
+
(L(ab cd*)) (L(c d* ab))* L(ab)(L(cd))
+
+
(L(ab) (L(cd))*) ((L(cd))* L(ab))* L(ab) (L(cd))
+
+
({ab} ∪ {cd})*) ( {cd}* ∪ {ab})* {ab} {cd}
+
{ , ab, cd, cdcd,...} { , cd, cdcd,…,ab}* {abcd, abcdcd,…}
{ , ab, cd, cdcd,...} { , cd, cdcd,…,ab,…} { abcd, abc dcd,…}
{ , ab, cd, cdcd,...} {abcd, abcdcd,…,cdabcd, cdabcdcd,…, ababcd…}
{abcd, abcdcd,…,cdabc d, cdabcdcd,…,ababcd …}

5.

((((a b)* b ) )* a b*) ab sobre = { a,b }++
L(((((a b)* b ) )* a b*) ab)
++
(L(((a b)* b ) )*) L(a b*) L(a) L(b)
+
((L(a b)* L (b) )* L(a) L(b*)) L(a) L(b)
+
(((L(a) L(b))* (L(b)) )* L(a) (L(b))*) L(a) L(b)
+
((({a} ∪ {b})* ∪ {b} )* {a} ∪ { b}*) {a} {b}
+
(({a,b}* ∪ {b} )* {a} ∪ {b}*) {ab}
({ , a, b, ab, ba,…,bb, bbb,…}* { , a, b, bb,…}) {ab}
({ , a, b, ab, ba,…,bb, bbb,…} { , a, b, bb,…} ) {ab}
{ ,a, b, ab, ba,…, bb,...