Lenguajes Sobre Alfabetos
1. Sea L = {x, 00} , Potencia L a la potencia 0, 1, 2, 3
2.Para un alfabeto ∑ = {a1,a2,…,an} se pueden numerar las palabras de ∑* de la siguiente manera:
ε0
a11
a22..
ann
a1a1n+1
a1a2n+2
Potencia el lenguaje ∑ = {a, b}, en una secuencia de 0 hasta n como en el ejemplo anterior para determinar su patrón.
ε0
ab11
ab22
..
abnn
ab1ab1n+1
ab1ab2n+2
3.Potencia ellenguaje L(φ) = { } hasta n
4.Escribe las operaciones básicas con expresiones regulares
Selección de alternativas : Se indica con el operador |(barra vertical). Si r y s son ER, entonces r | s es unaER que define a cualquier cadena que concuerde con una r o una s, también se dice que r | s , es la unión de los lenguajes de r y s y lo podemos definir: L( r | s ) = L( r ) U L( s ). Esta operaciónse puede extender a más de dos ER.
Concatenación: Se indica con la yuxtaposición de las ER. Si r y s son ER, entonces rs es una ER que define a cualquier cadena que concuerde con la concatenación de ry s , esta operación la podemos definir: L(rs) = L(r)L(s).Esta operación se puede extender a más de dos ER.
Repetición o Cerradura: También se conoce con el nombre de cerradura de Kleene. Se indicacon el operador *. Si r es una ER, entonces r* es una ER que define a las cadenas de caracteres representadas por la concatenación repetida de r en n veces, o sea que lo podemos definir como: L(r*) =L(r)*o también lo podemos definir como la unión infinita de conjuntos r :r* n = r 0 r 1 r 2...r n.
Potencia de un lenguaje: Se define la potencia i-ésima de un lenguaje a la operación de concatenarloconsigo mismo i veces.
Li= LLL ....L
5.Escriba las siguientes expresiones regulares para los siguientes lenguajes.
5.1) El conjunto de cadenas del alfabeto {a,b,c}que contenga por lo menos una a y por lo menos una b.
5.2) Todas las cadenas que constan de un 0 y un número cualquiera de 1s.
5.3) El conjunto de cadenas del alfabeto {a,b,c} que...
Regístrate para leer el documento completo.