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 ...
2k views

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 \... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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? 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. 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 ... 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?

15 30 50 per page