# Tag Info

1

Any word $w$ in $L$ can be split into two words $w$ and $w'$ such that $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$, $w' \in \{c^r d^s \mid r+s > 0\}$ and if the last symbol of $w$ exists and is $d$, then the first symbol of $w$ is $d$. On the other hand, every choice of $w$ and $w'$ that satisfies the above constrains induces a word $w w' \in L$. In ...

2

Let $L$ be a regular language, then $L$ has both a left linear grammar and a right linear grammar. The right linear grammar $G_R$ has axiom $S_L$ and productions of the form $A\to_R aB$ or $A\to_R\varepsilon$, and the left linear grammar has axiom $S_L$ and productions of the form $P\to_L Qa$ or $P\to_L\varepsilon$. Note that the left linear grammar is ...

0

Here is a sketch of an NPDA for $L^{|2|}$ given a regular language $L$. If $L$ is regular then it has a DFA $M$. We assume for simplicity that $M$ has one final state only. Create two NPDA from $M$. One is $M_{push}$ which is $M$ but with a stack such that every time it reads an input it pushes a symbol, say $X$. The other NPDA is $M_{pop}$ that pops the ...

2

Let $\mathcal{A}$ be a DFA for $L$. A direction is to consider a PDA $\mathcal{B}$ for $L^{|2|}$ that is defined on top of the product of $\mathcal{A}$ with itself, that is, the state-space of $\mathcal{B}$ is $(Q_{\mathcal{A}} \cup \{ null\})\times Q_\mathcal{A}$, where $null$ is a special state that is not in $Q_{\mathcal{A}}$, to be explained below. The ...

4

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then $$L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}).$$ Standard ...

2

Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form $$0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w.$$ If $y \geq x$, let $y=x+b$. Then we are interested in words of the form $$0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b ... 1 I don't know if x, y, etc. can be 0, so maybe there's something to fix (e.g., you'll need S\rightarrow \varepsilon etc.), but you can try something like this: S\rightarrow 0S1 \mid 0A0 \mid 1B1  A \rightarrow 0A0 \mid 1C0 B \rightarrow 1B1 \mid 1C0 C \rightarrow 1C0 \mid \varepsilon Suppose w\geq x, then the idea is first generating the ... 4 This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately. How does the \epsilon-removal work? Suppose that we ... 2 You already lost the 010 word when you've removed the A\to \epsilon rule. In G', which is the grammar you got by removing \epsilon-rules, you also need to add the A \to 01 rule. 2 If L_0 in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language$$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}. This language is context-free, but is complement (with respect to $\{a,b,c\}$) is not. Another way to formulate your question is as follows: given a context-free grammar ...

1

The first step is finding a simpler description of the language generated by the grammar $S \to aSbS \mid \epsilon$. The second step is deducing a description of the complement, which is the language you're actually interested in. Finally, in order to show that the language is context-free, you can consult our reference question on this topic.

Top 50 recent answers are included