Linked Questions
115 questions linked to/from How to prove that a language is not context-free?
0
votes
0
answers
149
views
Why does $L=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} \notin CFL$ [duplicate]
Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma.
So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I ...
- 256
0
votes
1
answer
216
views
Push-down Automata Construction
Construct a push-down automata to recognize the language $ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here, $v^{\complement}$ is the bit-complement of v.
I don't see how to perform ...
- 25
0
votes
1
answer
582
views
Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL
Assuming $L$ is defined as follows:
$$ L = \{ 0^n1^{n^2} | n \ge 0 \} $$
I'm trying to either prove/disprove whether $L$ is CFL or not.
My intuition tells me its not CFL since I cannot express the ...
- 11
1
vote
1
answer
333
views
Is $\{u u^R u : u \in \Sigma^*\}$ context-free?
Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)
I tried to show it wasn't context-free by using the ...
- 13
0
votes
3
answers
2k
views
Is it possible to prove Language L context-free? [duplicate]
Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.
If the answer is yes, can I use the following PDA to prove it?
Since {a^n b^(n+m) a^m}={a^n b^n ...
0
votes
0
answers
125
views
Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]
In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
- 31
0
votes
0
answers
91
views
Proving that $L = \{a^m b^n | m \% n = 0 \}$ is not context-free [duplicate]
For language $L = \{a^m\, b^n\: |\: m \:\%\: n = 0 \}$, that is, $m$ is a multiple of $n$, I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ...
- 179
0
votes
1
answer
1k
views
Showing that u#v with u a substring of v is not context-free
I need to find whether this language is context-free or not:
{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}
I suspect that it'...
- 133
2
votes
3
answers
2k
views
Structure of a Pumping Lemma proof: contradiction or counterexample?
This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
- 123
1
vote
4
answers
13k
views
How to prove {a^(n^2) | n>0} is not context-free?
So I have a language:
$$
L = \{a^{n^2} \mid n > 0\}
$$
I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
- 119
6
votes
1
answer
458
views
Why do we study closure properties of formal languages?
In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
- 509
-1
votes
2
answers
15k
views
How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is? [duplicate]
$L_1 = \{a^mb^nc^{m+n}: n,m>1\}$
I know $L_1$ is CFL and works with a pushdown automata.
$L_2 = \{a^nb^nc^{2n}: n>1\}$
The language $L_2$ should also be a CFL because it looks similar, but ...
- 141
-3
votes
1
answer
158
views
Showing that $\mathscr{L}$ is not context-free-grammar language
Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leqslant i\leqslant |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$.
Prove ...
- 449
3
votes
1
answer
2k
views
Use the pumping lemma to prove that {www} is not context-free
Use the pumping lemma to prove that the following language is not context-free.
$\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$
I am studying for an exam and really trying to understand this question. ...
- 31
0
votes
1
answer
240
views
Show Language is not context free without pumping lemma [duplicate]
Can we show that following language is not context free using Push down automata approach?
L = {a^i b^i a^i : i>=1}
For every a we will Push 'A' onto stack, ...
- 1