Linked Questions

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 ...
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 ...
14
votes
1answer
471 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 ...
1
vote
2answers
250 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 ...
0
votes
1answer
109 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
vote
1answer
66 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 ...
-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
34 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
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?
1
vote
1answer
76 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:...
1
vote
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 ...
3
votes
2answers
77 views

Can the pumping lemma for context free languages be extended to any subword?

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 ...
-1
votes
1answer
68 views

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.
0
votes
1answer
246 views

Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
0
votes
0answers
107 views

Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
1answer
77 views

Prove or disprove if L is CFL? [duplicate]

Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks.
1
vote
0answers
122 views

Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]

Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part. $$L=\{a^mb^nc^{mn}\mid m>n\}$$
0
votes
1answer
176 views

Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
2
votes
1answer
779 views

How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help. The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
0
votes
0answers
14 views

Non-context free languages with word degree [duplicate]

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 : $...
0
votes
0answers
14 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 ...
0
votes
1answer
237 views

Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ } is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL i even know the grammar for it ...
1
vote
0answers
83 views

Proof that the language is not regular (Pumping Lemma) [closed]

I have to prove that the following language is not regular: $$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$ I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both ...
0
votes
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 ...
0
votes
1answer
38 views

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.
0
votes
1answer
68 views

Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ ...
0
votes
1answer
172 views

Pumping lemma to show a language is not context free [duplicate]

I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start ...
0
votes
1answer
329 views

Pumping lemma with multiple of prime number + a constant

Given the language $$L = \big\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\} $$ show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be ...
0
votes
1answer
40 views

Is the language in the description context free? [closed]

I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a<= number of b<= number of c. I can solve if there are a and b (...
0
votes
0answers
177 views

How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that $L = \{a^nb^nc^n \mid n > 0\}$ Could you help me to find the ...

15 30 50 per page