# Tag Info

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

### 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

### 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

### 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
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
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
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
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
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
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), ...
• 141k
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
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
Accepted

• 11.3k

### 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