Linked Questions

-1
votes
1answer
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 ...
3
votes
5answers
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 ...
14
votes
1answer
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 ...
12
votes
2answers
2k views

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 ...
4
votes
2answers
4k views

Why is this example a regular language?

Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\} $$ According to the Pumping Lemma, a language $L$ is regular if : $y \ne ...
13
votes
2answers
579 views

Is a unary language regular iff its exponent is a linear function?

While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build ...
8
votes
3answers
462 views

Proving the language which consists of all strings in some language is the same length as some string in another language is regular

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
5
votes
1answer
2k views

Prove that the language of non-prime numbers written in unary is not regular

Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$ Heres what I have: "If ...
4
votes
1answer
200 views

Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$. How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?
1
vote
1answer
159 views

Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem? At other languages with $\Sigma >1$ we can usually separate the word or ...
3
votes
0answers
42 views

Sets whose decimal expansions form a regular language

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \...