Cheap and Secure Web Hosting Provider : See Now

[Solved]: Proof that whether a regular language is finite is decidable

, , No Comments
Problem Detail: 

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When you generate all strings from length 0 to n, if the machine accepts any of them then the language is non-empty. We don't have to check words with length > n because of the pumping lemma. The question claims that you can solve the decision problem for finiteness in a similar way.

I know intuitively that a regular language is finite if its finite, well-formed regular expression does not contain a Kleene star, but I don't know how to convert this notion around. My thought is that we have to know if there are any words in the language whose length is greather than n, but that requires checking all words.

Then I thought: Have the machine count the number of states n in the FSM. Generate all of the strings of length 0 to n. Then, check every word to see if the only possible way to pump this word xyz is to make y≡λ. If every word pumps only according to this condition, then the language is finite. However, this feels somehow incomplete.

Could someone give me a hint or push me in the right direction? Thanks.

Asked By : user327716

Answered By : Raphael

Show that an NFA accepts an infinite language if and only if there is a (directed) path from the initial to an accepting state which contains at least one state more than once.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55592

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback