Linked Questions

3 votes
1 answer
949 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 ...
eeKat88's user avatar
  • 31
1 vote
0 answers
1k 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. ...
problemZzz's user avatar
2 votes
1 answer
585 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 ...
Richard Jones's user avatar
0 votes
1 answer
211 views

Could anyone prove that this is a context free language or not? [duplicate]

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$ ...
user avatar
2 votes
0 answers
202 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 ...
Milind Hegde's user avatar
1 vote
0 answers
94 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 ...
user avatar
26 votes
2 answers
31k 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'...
Evgeny Eltishev's user avatar
28 votes
2 answers
47k 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 ...
D.W.'s user avatar
  • 160k
17 votes
1 answer
12k 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 $...
hauptbenutzer's user avatar
26 votes
3 answers
2k 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 ...
Robert777's user avatar
  • 747
4 votes
3 answers
9k 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$ ...
Stupid's user avatar
  • 51
3 votes
1 answer
9k 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 ...
redundant6939's user avatar
3 votes
2 answers
1k views

Is this language a context-free language or not?

I try to determine if the following statement is true: for any given language $L \subseteq A^*$ if $L$ is a context-free language then $L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$ is also a context-...
pblass's user avatar
  • 55
11 votes
1 answer
701 views

How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

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\}^{*},\ ...
limitless's user avatar
  • 266
1 vote
2 answers
1k views

How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$

We know that $L = \{ xy | x, y \in (0 + 1)^*, |x| = |y|, x≠y\}$ is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
S. M.'s user avatar
  • 317

15 30 50 per page