I'm taking a course on formal languages and was given this exercise:
Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings.
Can someone give me a hint? Thanks!
I'm taking a course on formal languages and was given this exercise:
Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings.
Can someone give me a hint? Thanks!
Normalize the FSM to eliminate unreachable states. (If you were not given a FSM, construct one.) The resulting FSM either contains a loop, or not. If it does, then… . If not, then … . (You fill in the dots.)
Or alternatively, if you are given a regular expression, normalize it to eliminate trivial terms like $\varnothing\cdot X$ and $\epsilon^\star$. The resulting expression either contains a ∗ or does not….