2022 Developer Survey is open! Take survey.

# Tag Info

### What does it mean to prove that a set of binary integers is regular?

The question want us to design a Deterministic Finite Automaton (DFA) that accepts Binary Representation of Integers that is divisible by 3. $\mathcal{L}=\{x\in\{0,1\}^∗:x$ is the binary ...
• 225
Accepted

### Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

Consider the following operation on context-free languages. For $L\subseteq \{a,b\}^*$, we have $L_\square = \{ u\square v \mid uv\in L\}$, where $\square$ is a new symbol. Thus $L_\square$ adds a ...
• 27.2k

### Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

We want to show the language $L = \{0^{2^n}: n \ge 0\}$ is nonregular. By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$, called the pumping length, such that all ...
• 1,005

### Myhill–Nerode equivalence classes for the language $b^ia^{5j}$

The Myhill-Nerode relation with respect to a given language $L \subseteq \Sigma^*$ is an equivalence relation on $\Sigma^*$ and hence gives a partition of $\Sigma^*$. Because this is a partition, the ...
• 1,005
Accepted

### Language of Turing machines that go through some configuration infinitely many times on empty input

No, $L$ is not decidable. Summary (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will ...
• 33.1k

### Myhill–Nerode equivalence classes for the language $b^ia^{5j}$

In order to check that these are the correct classes, you need to check three things: Any two words in the same class are equivalent. Any two words in different classes are inequivalent. Every word ...
• 269k
1 vote
Accepted

### An exercise that asks for informal description of the language accepted by a specific PDA

The language of this PDA seems to be the set of all strings that have twice as many $b$'s as $a$'s. If there is a deficit of $a$'s in the prefix seen so far in the sense that the number of $b$'s ...
• 1,005

Grammar ...
• 334

### Is this language a context-free language or not?

I do not think the linked question is relevant. Consider the context-free language $L = \{a^n b^n c^m d^m \mid m,n\ge 0\}$. Let us consider an example string, $uv = a^3 b^3 c^8 d^8$. Assuming $u$ and ...
• 27.2k
Accepted

• 22.7k
1 vote
Accepted

### Prove $REJECT\leq_mACCEPT$ and vice versa

There might have been confusion on the meaning of "return the opposite of what it returns" when you run $M$ on $w$. When $M$ runs forever, nothing can be returned by $M$. Then that rule does ...
• 33.1k
1 vote

Here is how to construct a regular expression for the set of strings over $\{a,b\}$ which contain an even number of $a$'s and at most one $b$. Strings that contain no $b$ are of the form $a^n$, where $... • 269k 1 vote Accepted ### Irregularity of$\{b^ma^n: (m,n)=1\}$using Nerode Let$P$be the set of all primes. Show that the words$\{b^p : p \in P\}\$ belong to different equivalence classes.
• 269k

Top 50 recent answers are included