Linked Questions
116 questions linked to/from How to prove that a language is not context-free?
0
votes
0
answers
39
views
How to determine class of formal language in Chomsky Hierachy
I recently started learning about the chomsky hierarchy and I am preparing myself for an upcoming exam. Often there are tasks to specify the smallest classification of a given formal language. How ...
0
votes
2
answers
106
views
Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$
Description
This is an exercise for Formal Language course, I'm asked to find a grammar for language:
$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$
As an example: 01c0011 can be generated using this language, ...
- 3
0
votes
1
answer
105
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 ...
- 1
15
votes
2
answers
855
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
2
answers
779
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 ...
- 1,210
0
votes
1
answer
420
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?
- 29
1
vote
1
answer
189
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 is ...
- 225
-1
votes
1
answer
29
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
1
answer
52
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 ...
- 11
0
votes
0
answers
21
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?
- 19
1
vote
1
answer
126
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:...
- 111
1
vote
0
answers
13
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 ...
- 33
3
votes
2
answers
256
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 ...
- 133
-1
votes
1
answer
88
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.
- 53
0
votes
1
answer
526
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-...
- 53
0
votes
0
answers
222
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 ...
- 21
0
votes
1
answer
148
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.
- 85
1
vote
0
answers
247
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\}$$
- 11
0
votes
1
answer
223
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 ...
- 329
2
votes
1
answer
2k
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
0
answers
15
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 : $...
- 1
0
votes
0
answers
16
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
1
answer
759
views
Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $ [duplicate]
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 ...
- 750
1
vote
0
answers
100
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 ...
- 139
0
votes
0
answers
13
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
1
answer
44
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.
- 9
0
votes
1
answer
104
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$ ...
- 41
0
votes
1
answer
253
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 ...
- 153
0
votes
1
answer
379
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 ...
- 551
0
votes
1
answer
41
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 (...
- 23
0
votes
0
answers
235
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 ...
- 175
0
votes
0
answers
177
views
A push down automaton that recognize exponential strings
How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$?
My approach
I know that the language can be described by a Turing Machine, but how i can the stack ...
- 169
0
votes
1
answer
206
views
Proving this language is not context free using the pumping lemma
I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages.
To prove something with the pumping lemma, ...
- 3
0
votes
0
answers
27
views
Is this language a context-free language? [duplicate]
I'm currently trying to figure out whether this language is context-free using the pumping lemma.
$\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$
I'm having trouble ...
- 3
0
votes
1
answer
4k
views
PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
Can someone help with this
$L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
12
votes
4
answers
7k
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 ...
- 285
0
votes
1
answer
218
views
Closure of context-free languages under "removal of a regular language from the right"
I have a homework that I can't solve can somebody help me?
If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for ...
1
vote
1
answer
84
views
Is regular expression syntax regular?
Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?
My guess is that the original syntax (concat, | and *) ...
- 113
0
votes
1
answer
663
views
Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG
Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language?
I've tried applying the pumping lemma for CFGs and proving case by case (taking ...
- 303
0
votes
0
answers
29
views
Generate a Grammar from a language(Non-CFL) [duplicate]
I tried to solve this question,
We have this Language, L(g)={AA|A={0+1}*}
The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side..
...
0
votes
1
answer
435
views
Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language [duplicate]
I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having ...
- 1
-1
votes
1
answer
71
views
using pumping lemma prove this language is not a context-free-language [duplicate]
How can one prove that the language below is not context-free using the pumping lemma?
$$\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \}$$
- 101
1
vote
4
answers
4k
views
Existence of non-context free but decidable languages
I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-...
- 11
2
votes
1
answer
1k
views
Is the language $\{a^n b^n c^i | i \leq n\}$ context free?
I'm trying to apply the CFL pumping lemma.
And, I've already tried words $a^pb^p$ and $a^pb^pc^p$.
Not sure where to go from here.
- 189
0
votes
1
answer
761
views
Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?
I cannot go on with this exercise:
Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free.
Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > ...
- 11
0
votes
0
answers
150
views
Why does $L=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} \notin CFL$ [duplicate]
Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma.
So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I ...
- 286
0
votes
1
answer
216
views
Push-down Automata Construction
Construct a push-down automata to recognize the language $ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here, $v^{\complement}$ is the bit-complement of v.
I don't see how to perform ...
- 25
0
votes
1
answer
595
views
Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL
Assuming $L$ is defined as follows:
$$ L = \{ 0^n1^{n^2} | n \ge 0 \} $$
I'm trying to either prove/disprove whether $L$ is CFL or not.
My intuition tells me its not CFL since I cannot express the ...
- 11
1
vote
1
answer
363
views
Is $\{u u^R u : u \in \Sigma^*\}$ context-free?
Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)
I tried to show it wasn't context-free by using the ...
- 13