# Linked Questions

0answers
19 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?
0answers
18 views

### Pumping Lemma for CFG - How to do it? [duplicate]

I'm literally so confused on how to even start this problem of proving that the given language is not Context Free. L = {a^i b^j c^k d^l | i = k and j = l} I ...
1answer
21 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.
0answers
13 views

### How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]

This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
0answers
13 views

I have stumbled across these 2 problems $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha$ has exactly 2 b's$\}$ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free Given : $... 0answers 12 views ### Context free/Non Context free Language [duplicate] Let L = { uv composed of {0,1} | |u| = |v| and u = v } Do we agree that this language is not a Context Free Language ? If not, why ? Can you give me a pushdown automata that recognizes it or the ... 0answers 10 views ### Choose a specific regular language to prove a language is not regular [duplicate] I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ... 10answers 102k 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 ... 6answers 14k views ### Are Turing machines more powerful than pushdown automata? I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ... 2answers 23k 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 5k views ### Example of a non-context free language that nonetheless CAN be pumped? So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma). 4answers 4k views ### Prime number CFG and Pumping Lemma So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ... 2answers 4k views ### How can I prove this language is not context-free? I have the following language$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-... 2answers 981 views ### Are context-free languages in$a^*b^*$closed under complement? The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of$a^*b^*$for some letters$a,b$are closed under ... 2answers 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 ...

15 30 50 per page