Cheap and Secure Web Hosting Provider : See Now

[Solved]: If a machine recognizes language L, can it also recognize L*?

, , No Comments
Problem Detail: 

This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings in L* will be accepted as well. One problem I see with this is that a machine can only accept one language, so it might be problematic...

Asked By : maregor

Answered By : Raphael

One problem I see with this is that a machine can only accept one language, so it might be problematic.

You are answering your own question: by definition¹, any given automaton accepts $L$ and $L^*$ if and only if $L = L^*$. This can happen -- examples include $L = \{ \varepsilon \}$ and $L = \Sigma^*$, for instance, but not as a rule.

It is not clear from your question if you understand the acceptance criterion of finite automata. The automaton has to be in a final state after reading the whole input, not in the beginning or at any time.


  1. The language accepted by automaton $A$ is uniquely defined to be the set of words $w$ for which $A(w)$ is (an) accepting (computation).
Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback