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,912
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
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
  • 34k
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.2k
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
  • 34k
2 votes
Accepted

Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

$S \rightarrow aSb/A $ $A \rightarrow \epsilon/a/aa/aaa/B$ $B \rightarrow bB/\epsilon$
user avatar
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.2k
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
  • 34k
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

expression/pattern for language where product of number of 0s and 1s is even

I don't know whether writing the complement of a regular expression will satisfy the requirements of your test, but anyway it's not correct. $2^∗(002^∗|112^∗)^∗012^∗$ must start with $0$, $11$, or $2$,...
user avatar
  • 11.2k
1 vote
Accepted

LR(1) grammar that can not be transformed an LL(1) grammar

$\def\NT#1{{\langle\it #1\rangle}}\def\T#1{{\tt#1}}$ The canonical example of an $LR(1)$ language which is not $LL(k)$ for any $k$ is $L_{\ge} = \{a^i b^j\mid i\ge j\}$. It's easy to show that the ...
user avatar
  • 11.2k
1 vote

Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones

Yes, you can safely modify the rules for $A$. In this particular case, the order ($A1$ vs. $1A$) makes no difference in the language generated by your grammar. The difference is in the way how words ...
user avatar
1 vote

Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$

By your above mentioned grammar $S \to aSb|bSa|abS|baS|Sab|Sba|\epsilon$ has four redundants $abS,baS,Sab,Sba$ and one missing term is $SS.$ Because if you use $S \to aSb|bSa|\epsilon$ only after ...
user avatar

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