New answers tagged formal-languages
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 ...
- 225
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 ...
- 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 ...
- 1,005
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 ...
- 1,005
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 ...
- 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 ...
- 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
2
votes
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 ...
- 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^...
- 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 ...
- 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 ...
- 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 < ...
- 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
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 $...
- 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