# Linked Questions

10answers
114k 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 ...
2answers
25k 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
1k views

2answers
964 views

### Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
2answers
2k 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 ...
2answers
352 views

### Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
6answers
15k 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 ...
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
2k views

### Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar? I don't believe this has a context-free grammar, but please correct me if I'm wrong.
1answer
586 views

### A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
3answers
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 ...
2answers
47 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 ...
1answer
2k views

### Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
1answer
137 views

### Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
1answer
470 views

### Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
3answers
2k views

### Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{a^nb^m|n,m\in\mathbb N\land n\ge m\}$$ Is my hypothesis true or is ...
3answers
1k views

### Structure of a Pumping Lemma proof: contradiction or counterexample?

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
2answers
1k views

1answer
2k views

### Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language. Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$. So how do I ...
2answers
99 views

### Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma. I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but ...
2answers
296 views

### Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\}$ Can you find such a ...
1answer
328 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 ...
1answer
345 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.
0answers
40 views

1answer
42 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 ...
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
98 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\}$$
0answers
70 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 ...
1answer
162 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 ...

15 30 50 per page