34 views

### Prove that $\{w \in \{a\}^* | \nexists n >0: |w| = n^{2}\}$ is not context-free [duplicate]

I've to prove that: $\{w \in \{a\}^* | \nexists n >0: |w| = n^{2}\}$ is not context-free with the Pumping Lemma. Any clues?
56 views

### Proof that $\{a^ib^jc^k\mid i,j,k\in\mathbb{N}, i<k<j\}$ is not context-free using the Pumping Lemma

$$L=\{a^ib^jc^k \;| \;i, j, k \in \mathbb{N} \; \text{and} \; i <k<j\}$$ I need to show that this language is not context-free with the help of the Pumping Lemma. My first intuition is, that ...
25 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 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 ...
537 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 ...
373 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 ...
146 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?
98 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 ...
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.
38 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 ...
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?
87 views

### Is this language is Context-free language or not?

Is anybody can help me please to determine is this language is Context-free language or not? L={wvw | w,v∈{a,b,c}+} for example: part of the language: acbac, abcab, bbcbb not part of the language:...
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 ...
It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
### How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.