Revisión 1: Lenguajes Regulares
Se realiza revisan conceptos de los Lenguajes Regulares:
  • Operaciones de Lenguajes Regulares ERER+
  • Autómatas finitos AFAF
  • Autómatas finitos no determinísticos AFNDAFND
  • Autómatas finitos no determiínisticos con transiciones epsilón AFND-εAFND\text{-}\varepsilon
Se investiga sobre la minimización de autómatas finitos (determinístico)
Se aplican el uso de expresiones regulares profesionales

 

Sección uno: ERERAFND-εAFND\textnormal{-}\varepsilonAFNDAFNDAFAF


Para los ejercicios de 1 a 6  proponer lo siguiente para el lenguaje correspondiente:
  1. Cadenas aceptadas y rechazadas por el lenguaje
  1. Una ERER que represente al Lenguaje Regular
  1. Usando la ERER del punto anterior obtener un AFND-εAFND\textnormal{-}\varepsilon que acepte al lenguaje, utilizando el procedimiento de reducción correspondiente
  1. Usando el AFND-εAFND\textnormal{-}\varepsilon del punto anterior obtener un AFNDAFND, utilizando el procedimiento de reducción correspondiente
  1. Usando el AFNDAFND del punto anterior obtener un AFAF, utilizando el procedimiento de reducción correspondiente
  1. Para 2, 3, 4  y 5 proporcionar una explicación corta (de tres a cinco oraciones) por qué se representa o se sigue aceptando al mismo lenguaje

Evidencia a incluir:
  1. 10 cadenas que pertenezcan al lenguaje
  1. 10 cadenas que no pertenezcan al lenguaje
  1. ER para el lenguaje y explicación como la ERER representa al lenguaje
  1. AFND-εAFND\textnormal{-}\varepsilon derivado de la ER y explicación como el AFND-εAFND\textnormal{-}\varepsilon acepta al lenguaje
  1. AFNDAFND derivado del AFND-εAFND\textnormal{-}\varepsilon y explicación como el AFNDAFND sigue aceptando al mismo lenguaje
  1. AFAF derivado del AFNDAFND y explicación como el AFAF sigue aceptando al mismo lenguaje

Sugerencias 
Para las reducciones usar el software

Ejercicio 1

Con Σ={a,b,c}\Sigma=\{a,b,c\} el lenguaje L1L_1 con cadenas cuyos primeros cinco símbolos son 3 aes  y 2 ces en cualquier orden

Ejercicio 2

Con Σ={x,y,z}\Sigma=\{x,y,z\} el lenguaje L2L_2 con cadenas cuyos últimos cinco símbolos son 2 zetas  y 3 yes en cualquier orden

Ejercicio 3

Con Σ={i,j,k}\Sigma=\{i,j,k\} el lenguaje L3L_3 con cadenas que en algún momento tienen una secuencia de cinco símbolos consistentes de  2 ies  y 3 kas en cualquier orden

Ejercicio 4

Con Σ={a,b,c}\Sigma=\{a,b,c\} el lenguaje L4L_4 con cadenas cuyos primeros tres símbolos son 2 aes  y 1 ce o 1 be y 2 ces o  1 a y 2 bes en cualquier orden

Ejercicio 5

Con Σ={x,y,z}\Sigma=\{x,y,z\} el lenguaje L5L_5 con cadenas cuyos últimos tres símbolos son 2 equis y 1 zeta o 1 ye y 2 zetas o  1 equis y 2 yes en cualquier orden

Ejercicio 6

Con Σ={i,j,k}\Sigma=\{i,j,k\} el lenguaje L6L_6 con cadenas que en algún momento tienen una secuencia de tres símbolos 2 ies  y 1 ka o 1 jota y 2 kas o 1 i y 2 kas en cualquier orden