Lenguajes y Autómatas - Módulo 1.3 (Expresiones regulares)
HTML-код
- Опубликовано: 14 дек 2024
- Material elaborado por el Profesor Dr. Fabián Riquelme Csori, para el curso de Lenguajes y Autómatas, de la Escuela de Ingeniería Civil Informática de la Universidad de Valparaíso, Chile.
MÓDULOS DEL CURSO
Capítulo 1. Lenguajes regulares y autómatas finitos.
1. Alfabetos, cadenas y lenguajes
2. Jerarquía de Chomsky
3. Expresiones regulares
4. Autómatas finitos deterministas (DFA)
5. Autómatas finitos no-deterministas (NFA)
6. Conversión y equivalencia NFA-DFA
7. Lema del bombeo (para lenguajes regulares)
Capítulo 2. Lenguajes libres de contexto y autómatas de pila
1. Gramáticas libres de contexto (CFG)
2. Árboles de derivación
3. Autómatas de pila (PDA)
4. Conversión CFG-PDA
5. Lema del bombeo (para lenguajes libres de contexto)
Capítulo 3. Máquinas de Turing y computabilidad
1. Tesis de Church-Turing
2. Máquinas de Turing (TM)
3. TM en notación modular
4. Variaciones de TM
5. TM no-deterministas
Muy,muy buena sus clases! Ya mire todo el temario. Super completo el contenido y excelente su forma de explicar los temas. Gracias!
Buenas profe tengo una pregunta. Si tengo una expresion regular que sea (a+b*)*, quiere decir que las cadenas validas serian => Epsilon, a, b, ab, bb, abb, bbb, abbb, bbb y asi sucesivamente?? Muchas gracias por su respuesta.
Esa expresión regular (a+b*)* es equivalente a: (a+b)*, por lo que también se considerarían a las cadenas: aa, ba, abb, aab, aabb, abab, ... y así sucesivamente :D
Hola. Ambas fórmulas no son equivalentes, ya que (a+b)* solo permite una "b" después de cada "a". "ba" no puede ser generada por ninguna de esas fórmulas, porque ambas empiezan con a+ y por tanto obligan que la cadena siempre empiece con una "a". Saludos.
Hola. Esa fórmula significa "concatenación de 0 más subcadenas de 1 o más a's seguida de 0 o más b's". Por lo tanto, cualquier cadena que empiece con "b" no puede ser generada por esa expresión regular. En cambio sí podrías generar cadenas como "aa", "aaa", "ab", "aab", "abb", etc. Saludos
por que en el ultimo ejemplo alternas entre una y otra? se supone que solo se puede una u otra pero no las dos
porque la barra | representa un OR lógico: se puede elegir 00 o 01, y la clausura de Kleene permite que esta selección pueda variar o mantenerse cada vez
Tengo exactamente la misma duda, la cláusula permite hacer n combinaciones, más no la concatenacion según entiendo
Una buena explicacion.
Si me dan (0+11). 0^*
Aca el mas es seleccion ? Se suele usar tambien el | para seleccion?
Muchas gracias profesor
Profe recibe consulta por email. Tengo un problema pero es con foto.?
si quisiera
crear una ER que inicie con cualquier numero del 16 al 20(16,17,18,19,o 20) como seria?
@@unprofedeinformatica muchas gracias, muy buen contenido el que haces
@@THENOTO890 ¿Te refieres a esto? (1[6-9]|20)
Profe hay alguna manera o truco para sacar una expresion regular dado un enunciado?
Hola profe para orientarme un poco con las E.R estaria bien si me dicen
Hallar cadenas con al menos una letra b
(a^* . b . a^* ) | (a|b)^*
El punto es concatenacion
si en ves del * hubiera un 2 afuera del parentesis, quiere decir que solo se harian 2 repeticiones? osea por ejemplo: (00+01+10+11)^2
deberia ser asi? : (e,00,01,10,11,0000,0101,1010,1111)
@@unprofedeinformatica perfecto, en un inicio lo hice así, pero no estaba seguro, muchas gracias!
en el ejemplo (00 | 01*) tambien se valen las repeticiones?
por ejemplo 0001....1
@@unprofedeinformatica entonces como disyunción, ésta funciona como exclusiva, ¿cierto? Pues de lo contrario ¿se podría aceptar: 000, 0001, 0001...1?
Muy buena explicación
Gracias, mañana tengo examen y no entendia nada JAJAJAJ :)
Que tal a todos no se si alguien me pueda ayudar con este problema la verdad que no entiendo muy bien lo de desmostraiciones y sin expreciones regulares espero me puedan ayudar
Pruebe que el lenguaje { 0, 10 }* consiste de todas las cadenas binarias que terminan en 0 y no contienen un prefijo que termine en 11 (más la cadena vacía)