• Author / Uploaded
• Jonathan Lopez

• Categories
• Expresión regular
• Conjunto (Matemáticas)
• Formalismo (deductivo)
• Lingüística
• Conceptos matemáticos

Citation preview

ACTIVIDAD 2 GENERAR CADENAS A PARTIR DE UNA EXPRESION REGULAR •

Palabra o cadena: es una secuencia de símbolos del alfabeto,es decir, s = a1a2...an, donde ai  .

Por lo general se utilizan las primeras letras del alfabeto, a, b, c, d, e, para denotar símbolos del alfabeto y las últimas letras, s, t, u, v, w, x, y, z, para denotar palabras.

•

•

Las expresiones regulares se utilizan para abreviar la descripción de conjuntos regulares. –

El conjunto regular {a} es representado por a.

–

Las operaciones de unión, concatenación y cerradura de Kleene son denotadas por +, yuxtaposición y *, respectivamente.

Definición recursiva de una expresión regular. Sea  un alfabeto. Las expresiones regulares sobre  se definen recursivamente de la siguiente manera: –

Base: ,  y a, para toda a  , son expresiones regulares sobre .

–

Paso recursivo: Si u y v son expresiones regulares sobre , entonces las expresiones (u+v), (uv) y (u*) también lo son y representan a los conjuntos {u}  {v}, {u}{v} y {u}*, respectivamente.

–

Cerradura: u es una expresión regular sobre  sólo si puede ser obtenido a partir de los elementos base mediante un número finito de aplicaciones del paso recursivo.

EJEMPLO 1 Lenguaje CADENA

Expresión regular

{}



{0}

0

{001} = {0}{0}{1}

001

{0, 1} = {0}{1}

0+1

{0, 10} = {0}{10}

0 + 10

{1, }{001}

(1 + )001

{110}*{0, 1}

(110)*(0 + 1)

{1}*{10}

1*10

{10, 111, 11010}*

(10 + 111 + 11010)*

{0, 10}*({11}*{001, }) (0 + 10)*((11)* + 001 + ) (00 + 01 + 10 + 11)*

((0 + 1)(0 + 1))*

EJEMPLO 2 •

El conjunto {bawab | w  {a, b}*} es regular sobre {a, b} Demostración: Conjunto Expresión Justificación 1. {a} a Base 2. {b} b Base 3. {a}{b}={ab} ab Concatenación de 1 y 2 4. {a}  {b}={a,b} a+b Unión de 1 y 2 5. {b}{a}={ba} ba Concatenación de 2 y 1 * * 6. {a,b} (a+b) Cerradura Kleene de 4 7. {ba}{a,b}* ba(a+b)* Concatenación de 5 y 6 * * 8. {ba}{a,b} {ab} ba(a+b) ab Concatenación de 7 y 3

•

(a+b)*aa(a+b)*+(a+b)*bb(a+b)*: –

•

Expresión regular que represente al conjunto de cadenas sobre {a, b} que contienen exactamente dos b’s: –

•

Representan cadenas con un número par de b’s.

Expresión regular para el lenguaje sobre {a, b} en cuyas palabras inmediatamente antes de toda b aparece una a: –

•

representan al conjunto de cadenas sobre {a, b} que contienen dos o más b’s.

a*(a*ba*ba*)* y a*(ba*ba*)* –

•

a*ba*ba*

a*ba*b(a+b)*, (a+b)*ba*ba*, (a+b)*b(a+b)*b(a+b)* –

•

Representa al conjunto de cadenas sobre {a, b} que contienen a la subcadena aa o a la subcadena bb o a ambas subcadenas.

(a+ab)*.

Expresión regular que representa a las palabras que contienen exactamente una vez dos b’s contiguas:

(ba+bc+a+c)*bb(a+c+ab+cb)