Algoritmo para saber si un lenguaje regular contiene al menos n cadenas

Question

Estoy haciendo un curso sobre lenguajes formales y me dieron este ejercicio:

Dar un algoritmo para saber si un lenguaje regular $L$ contiene al menos $100$ cuerdas.

¿Puede alguien darme una pista? Gracias.

Answer 1

1. Normalizar el FSM para eliminar los estados inalcanzables. (Si no te han dado un FSM, construye uno.) El FSM resultante contiene un bucle, o no. Si lo contiene, entonces . Si no, entonces . (Rellena los puntos.)

2. O bien, si te dan una expresión regular, normalízala para eliminar términos triviales como $\varnothing\cdot X$ y $\epsilon^\star$ . La expresión resultante contiene un ∗ o no .