11
votes
Accepted
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
$\newcommand{\m}{\operatorname{\%}}$
Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language.
Note $L=\{ w\mid d(w)=0\}$.
...
- 34.1k
6
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
The following language is not regular $L = \{a^n b^m c^n \mid m = n \bmod 2\}$.
To see that $L$ is not regular, suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. ...
- 23.4k
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
So far every language that I saw containing modulo was a regular language.
As John L. notes, that's a very good observation. Indeed, any language where the only constraint on words is that some ...
- 2,010
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Lucky enough, your case is quite easy. The language is defined by the rule "total number of letters, modulo 3, equals total number of a's, modulo 3". This is equivalent to "number of ...
- 25.2k
3
votes
Accepted
Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?
The answer to the question "Is $L_u = L_1 \cup L_2$ decidable?" is "sometimes".
For a positive example, let both $L_1$ and $L_2$ be the empty language.
For a negative example, ...
- 34.1k
3
votes
Accepted
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Lemma:
The parity of the Hamming distance between two strings is the parity of the total number of $1$s.
Proof:
If you toggle any bit in any of the strings, the parity of the distance changes. Start ...
- 3,910
3
votes
Accepted
Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
The constraints on $w, x,y, z$ are not given, I choose everyone $\geq 0.$
The strings could be equal $a$ and equal $d,$ equal $b$ and equal $c,$ equal $b$ and equal $d,$ equal $a$ and equal $c $ etc(...
- 466
3
votes
Accepted
Is the given language regular, CFL or in P
If a word is in your language, then it is of the form $w_1w_2$, where $|w_1| = |w_2|$ and $w_1$ contains a balanced string of length $100$, say $y$. Note that there are finitely many options for $y$. ...
- 270k
3
votes
Accepted
Why 2- way DFA is equivalent to NFA (and thus DFA)?
The language $L=\{ (u\#,v\#) \mid |u|=|2v|\}$ from your question is actually a two-dimensional language, that is a relation between two strings, each written on their own input tape. In that way the ...
- 27.6k
3
votes
Accepted
Are the set of all Bitcoin addresses a context-sensitive language?
Any answer I give you is likely to be unsatisfying and a little silly, both because we're squarely in theory-land here (and not the useful kind of theory, but theory that is irrelevant in practice), ...
D.W.♦
- 141k
3
votes
Accepted
Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free
Recall that every finite state automaton can be changed into a rightlinear grammar which has productions like $X\to aY $ and $X\to \varepsilon$.
Your language can be generated using the same technique,...
- 27.6k
2
votes
Accepted
Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
Your language is DCFL. But you made NPDA because in state $q_5$ the transitions $(q_5,\epsilon,a)\neq\emptyset$ and $(q_5,\epsilon,A)\neq\emptyset$ made your diagram NPDA as I previously said. Below ...
- 466
2
votes
Accepted
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
If $L$ is regular , then FirstHalves or $Half(L)$ is also regular.
Algorithm:
Design $DFA, M$ of language $L$
Find the reversal of $DFA$ ,$M$ , say $N.$
Traverse $M$ for one transition (for given $\...
- 466
2
votes
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
$w$ and $x$ are binary strings.
Clearly $|wx|=|xw|$ and $|wx|_0=|xw|_0$. Suppose $wx$ and $xw$ differ only at position $i$, so that $(wx)[i]\ne(xw)[i]$, $(wx)[1..i-1]=(xw)[1..i-1]$, and $(wx)[i+1..n+k]...
- 11.3k
2
votes
Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?
A few things,
It's hard to find what your proof attempt is trying to do. I know you're stuck, but you should at least have a strategy of what you want to do. In your proof, a good idea is to use ...
- 304
2
votes
Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
Let $F=\{x2y : |x| = |y|,\ x\in \{0\}^*,\ y\in\{0,1\}^*,\ d(x,y) = 1\}$, the language of all strings $0^n2y$ where $y$ consists of $n-1$ $0$s and one $1$.
Note that $F=\{0^p00^q20^q10^p: p\ge0, q\ge0\}...
- 34.1k
2
votes
Accepted
Prove a stronger version of the pumping lemma for context-free languages
Proof Idea for the usual pumping lemma
Let $z$ be a very long string in $L$. A parse tree for $z$ is so tall that it must contain some long path from the start symbol at the root of the tree to
one of ...
- 34.1k
2
votes
Accepted
Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
The result of this concatenation is $\Sigma^*$, which is regular.
I will leave it to you to verify this is the case.
- 10.8k
2
votes
Accepted
Formal language rewrite rules: strange notation
Yes, I think that's basically the intent. I guess the book is trying to write grammars without grammatical symbols. For me, it's abuse of notation, but that's pretty common.
Because there is no formal ...
- 11.3k
1
vote
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
Idea
The pumping lemma for context-free languages is not useful since M is "pumpable" with pumping length $p=2$. Instead, we will select a word in $\mathcal M$ that has less number of $a$'s ...
- 34.1k
1
vote
Accepted
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Regular languages are closed under reversal, therefore $L^R = \{v^R \mid v \in L\}$ is regular. Moreover, regular languages are closed under concatenation, therefore $L' = L \circ \{\#\} \circ L^R$ is ...
- 23.4k
1
vote
Accepted
variable repetitions in pumping lemma for context-free languages
It is certainly possible that some variables repeat in the subtree $T_3$, $T_4$ or $T_5$. There is nothing wrong with those situations, except that those situations are too relaxed for us to ensure &...
- 34.1k
1
vote
is there a non-context free language A such that A1 is context free?
No. Note that $A = A1 / \{1\}$, the right quotient of $A1$ over $\{1\}$. Since $\{1\}$ is a regular language, we know that $A$ is context-free when $A1$ is context-free, thanks to this post that ...
- 34.1k
1
vote
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Your operation is very general, and in its generality your conjecture is not true.
For instance take for $o$ the identity, then we get the simple example $o(\{a,b\}^*) = \{wcw\mid w\in \{a,b\}^*\}$ ...
- 27.6k
1
vote
Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
This answer on purpose is more complicated than necessary. My goal is to apply a general property of regular and context-free languages, see: Prove that the equal-length concatenation of regular ...
- 27.6k
1
vote
If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular
Start with an automaton for $L$, with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. Construct a new automaton whose set of states is $Q \times 2^Q$. After ...
- 270k
1
vote
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
The language $\mathrm{half}(L)=\{x\mid xy\in L,|x|=|y|\}$ can be quite complicated, compared to the original language $L$. I am afraid that there is no simple construction and we have to keep track of ...
- 27.6k
1
vote
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
I guess this question Prove half(L) is regular is the same.
There are several ways to prove a language is regular:
By building DFA, NFA, or Regular Expression (which is the case in your question).
...
- 456
1
vote
Accepted
prove $A$ is context-free
This language is regular and this is an NFA that describes it:
Please notice that the language has nothing to do with "counting" and it doesn't need any memory so you can simply realize it'...
- 456
1
vote
Accepted
Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $
First of all your language is CFL means NCFL not DCFL because machine has push confusion. Therefore DPDA design is not possible. Only NPDA has power to accept your language.
You have to understand ...
- 466
Only top scored, non community-wiki answers of a minimum length are eligible