2022 Developer Survey is open! Take survey.

New answers tagged

0 votes

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 ...
user avatar
2 votes
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 ...
user avatar
  • 27.2k
0 votes

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 ...
user avatar
2 votes

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 ...
user avatar
3 votes
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 ...
user avatar
  • 33.1k
2 votes

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 ...
user avatar
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 ...
user avatar
2 votes

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

Grammar ...
user avatar
3 votes

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 ...
user avatar
  • 27.2k
8 votes
Accepted

Is this language a context-free language or not?

No, $L_1$ is not necessarily context-free. For example, let $L=\{0^n1^{3n}\mid n\ge0\}$. If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$. So, $L_1=\{1^...
user avatar
  • 33.1k
1 vote

Is the language of words that are unbalanced in the first half context-free?

(Note: this answer doesn't fully answer the question — I don't know whether the language is context-free — it merely addresses the question of whether it satisfies the pumping lemma, which was raised ...
user avatar
  • 521
1 vote

Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem

Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q. After processing $a^p$ you are in a state S that ...
user avatar
  • 24.9k
2 votes
Accepted

Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem

Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k < ...
user avatar
  • 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 ...
user avatar
  • 33.1k
1 vote

Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's

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 $...
user avatar
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.
user avatar

Top 50 recent answers are included