algorithm that can determine for every regular language

how can I show that there exists an algorithm that can determine for eve开发者_运维技巧ry regular language L, whether or not |L| ≥ 5

Give an algorithm, which proves that such algorithms exist :D

Remember that regular languages can be matched by regular expressions (there's a 1-to-1 correspondence). Now, looking at a regular expression, we can count the number of | and * in there, to determine if we have 5 or more strings that will be accepted.

I think case analysis will help. For example, if the language supports the following:

1. A - atom
2. (X|Y)
3. XY (concatenation)

The following shows the number of possible words for the cases:

1. case A 1
2. case (X|Y) l+r, where l = words X, r = words Y
3. case XY l*r, where l = words X, r = words Y

Now, if we have an algorithm that can determine the number of words, the algorithm asked for is trivial.

It is quite simple. How is a regular language generated? By an dfa (deterministic finite automate).

You can use dfa not just for checking if a word is in a language L but also for generate all words from L. This is done by traversing the graph recursive. Potenially L can contain infinite words so the traversing algorithm runs also endlessly. But in case you found a word you increment a counter. And when you finally reach your 5 words you break it.