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\}$. ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
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$. ...
user avatar
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 ...
user avatar
  • 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), ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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]...
user avatar
  • 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 ...
user avatar
  • 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\}...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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\}^*\}$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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). ...
user avatar
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'...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible