Linked Questions

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
468 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
219 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
0answers
13 views

Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...
0
votes
1answer
106 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
63 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
73 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
71 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
223 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
105 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
73 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
118 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
175 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
708 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
226 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
66 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
173 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 ...
0
votes
0answers
109 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 ...
0
votes
1answer
147 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, ...
0
votes
0answers
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 ...
0
votes
1answer
2k 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\}$
7
votes
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 ...
0
votes
1answer
147 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
1answer
66 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 *) ...
0
votes
1answer
552 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 ...
0
votes
0answers
28 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
1answer
334 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
votes
1answer
59 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 \}$$
0
votes
2answers
2k 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-...
2
votes
1answer
524 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.
0
votes
1answer
275 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 > ...
0
votes
0answers
126 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 ...
0
votes
1answer
201 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 ...
0
votes
1answer
410 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 ...
1
vote
1answer
189 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 ...
0
votes
3answers
1k views

Is it possible to prove Language L context-free? [duplicate]

Give a question: Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not. If the answer is yes, can I use the following PDA to prove it? Since {a^n b^(n+m) a^m}={a^n b^n ...
0
votes
0answers
94 views

Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]

In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...

15 30 50 per page