• Author / Uploaded
• jhon

Citation preview

Actividad – Individual

1. Para cada inciso, escribir la expresión regular. a. El conjunto de cadenas formadas por 0 y 1, con a lo sumo una pareja de 1 consecutivos. Σ={0, 1} b. El conjunto de cadenas que si inician con cero, finalizan en 1 y si inician con 0, nunca contiene la cadena 10. Σ={0, 1} c. El conjunto de cadenas que nunca contienen un 1 después de un 0. Σ={0, 1} d. El conjunto de cadenas que si finalizan en cero, tendrán que empezar con 01 y nunca contener tres ceros contiguos. Σ={0, 1} 2. Reducir las siguientes expresiones regulares, utilizando la tabla de identidades. Asúmase que reducir significa disminuir la cantidad de operaciones. a. [𝑎∗ (𝑎+ |𝑏+ )(𝑏∗ 𝑏+ )((𝑎∗ 𝑎|𝑎)|𝑏𝑏 ∗ )] ∗

∗

b. [0∗ (0∗ 1)∗ )(0∗ 1∗ )∗ (𝜀|11∗ )]|[(((11∗ )0) )|(1∗ 0|(1∗ 1))] c. [𝑎∗ (𝑎𝑏|𝑎𝑐)∗ (𝜀|𝑏)(𝑏𝑎|𝑏𝑐)𝑐 ∗ (𝑎|𝜀)|(𝑎∗ |𝑏 ∗ )∗ ] 3. Elaborar las expresiones regulares para los siguientes lenguajes. Σ = { 0, 1 } a. L2 = cadenas que siempre finalizan en 0, y que al presentarse un 1, le siguen dos 0. Σ = { a, b } b. L6 = cadenas que si inician con b, entonces se debe de tener al símbolo a en cantidad impar. Σ = { x, z } c. L1 = cadenas que si contiene la subcadena xyx, entonces debe de iniciar y finalizar en z.