300 views

### Show that if S is an arithmetic progression, then A can be recognized by a DFA [duplicate]

A set S of nonnegative integers is called an arithmetic progresion if there exist some integers n and p such that S = {n + ip : i ≥ 0} Let A ⊆ {a}∗ and consider S = {| x |: x ∈ A}. (1) Show that if ...
4k views

### Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ for ...
2k views

### Can a Turing Machine decide if an NFA accepts a string of prime length?

I want to know if the following problem is decidable: Instance: An NFA A with n states Question: Does there exist some prime number p such that A accepts some string of length p. My belief is that ...
### If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?
Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also ...