Linked Questions
114 questions linked to/from How to prove that a language is not context-free?
1
vote
1answer
76 views
Acceptance problem for CFGs is not regular
Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars.
It ...
21
votes
4answers
2k views
Algorithm to test whether a language is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
0answers
22 views
Need some guidance on CFG pumping lemma proof
I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something ...
14
votes
1answer
478 views
Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)
Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.
Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
0answers
14 views
Having trouble understanding how to prove a language context free? [duplicate]
I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
3
votes
3answers
3k views
Is this language LL(1) parseable?
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.
$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$
Is my hypothesis true ...
26
votes
2answers
32k 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 ...
3
votes
3answers
2k views
Are regular and context free languages closed against making them prefix-free?
For a language L we define:
$\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $
Are regular / context free languages closed under this operation ?
For regular languages I ...
1
vote
2answers
278 views
Is a^mb^n where m=n^2 a CFL?
Is $a^mb^n$ where $m=n^2$ a CFL?
I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right?
On the other hand I ...
8
votes
2answers
4k views
Is Python a context-free language?
From Wikipedia: Off-side_rule#Implementation, there is a statement:
...This requires that the lexer hold state, namely the current
indentation level, and thus can detect changes in indentation ...
85
votes
10answers
137k views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
0
votes
1answer
113 views
$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma
How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
-1
votes
1answer
24 views
Is there any tiny tips to find counter example string for proving some language is not a CFL? [duplicate]
When I prove some language is context free, It is too hard to find example string.
Is there any tips? It takes too many time or eventually give up.
1
vote
1answer
36 views
How to prove that a language is not context-free using pumping lemma
I'm trying to prove that that language isn't a context free:
$ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$
I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...
0
votes
0answers
20 views
How to prove this language is not context-free language by pumping lemma? [duplicate]
Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?