708 views

### Creating PDA for {xy such that |x|=|y| and x ≠ y} [duplicate]

I'm trying to create a PDA for $\{xy \mid |x|=|y| \text{ and } x \ne y\}$ over the alphabet $\Sigma = \{a, b\}$. But I don't know how the PDA will know if the two strings $x$ and $y$ are not equal. ...
Possible Duplicate: Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free Can anyone prove that the following is a CFL? or not? why? $$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and w_1 ... 1answer 205 views ### CFG for words that are not a concatenation of the same word [duplicate] I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:  L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ... 1answer 214 views ### is this a Context free Language : L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\} [duplicate] L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\} Alphabet = { a , b }* Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a ... 0answers 180 views ### Constructing a Context Free Grammar for checking non-equality of strings [duplicate] I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is ... 0answers 77 views ### Are these two languages context free? [duplicate] Possible Duplicate: Show that \{xy \mid |x| = |y|, x\neq y\} is context-free Do there exist context-free grammars for the following two languages: The set of all strings of the form xx where ... 0answers 44 views ### contextfree? {w1w2 | w1,w2 \in {a,b}* \land |w1| = |w2| \land w1 \neq w2} [duplicate] Is this language contextfree? {w1w2 | w1,w2 \in {a,b}* \land |w1| = |w2| \land w1 \neq w2}. I think it's not but can't prove it. 2answers 24k views ### How to prove that a language is context-free? There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ... 2answers 13k views ### Is the complement of { ww | … } context-free? Define the language L as L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}. In other words, L contains the words that cannot be expressed as some word repeated twice. Is L context-free or not? I'... 1answer 7k views ### Construct a PDA for the complement of a^nb^nc^n I am wondering if this is even possible, since \{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}. Therefore a PDA that can distinguish a word w\in\{a^n b^n c^n \mid n \geq 0\} from the rest of ... 3answers 1k views ### Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free? Is the following language context free?$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$As pointed out by sdcvvc, a word in this language can also be ... 2answers 4k views ### Find a pushdown automaton for { x#y ∣ x ≠ y } I was told to built a PDA that recognizes the following language:$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$My attempt is basically to push x to the stack for every 1 and 0 ... 1answer 5k views ### Pushdown automaton for complement of { ww | … } I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams). So, I already know that L = \{ ww \mid w \text{ in } (0,1)^*\} is not context free. Since CFL are not ... 1answer 1k views ### PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it I know the grammar for the language \{ xy : |x| = |y|, x ≠ y \} if \Sigma=\{a,b\}:$$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*}  I ...
Why does (if so) the seperator $\#$ is making a difference between the two languages ? Let say: $L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$ \$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, ...