# Tag Info

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 ...
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(...
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 ...

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$
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 ...
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 ...
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\}^*\}$ ...
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 ...
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$,...
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 ...
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 ...
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 ...

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