Linked Questions

0 votes
1 answer

How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? [closed]

How are these Context-Free Pumping Lemma Approaches differ? Maybe this might help understand pumping lemma better $(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$} $(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$} ...
Iancovici's user avatar
  • 665
3 votes
1 answer

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 ...
user avatar
0 votes
1 answer

Proving the language of words with equal numbers of symbols non-context-free [duplicate]

Possible Duplicate: How to prove that a language is not context-free? I'm having a hard time figuring this out, any help is appreciated. Let EQUAL be the language of all words over $\Sigma = \{...
user avatar
3 votes
3 answers

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\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
fuz's user avatar
  • 911
8 votes
1 answer

Is this language Context-Free?

Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
Andrés Felipe Téllez Crespo's user avatar
4 votes
1 answer

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 ...
user1494's user avatar
4 votes
4 answers

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 ...
BrotherJack's user avatar
  • 1,115
1 vote
2 answers

Proof that a language involving $gcd$ is not context-free

How would you prove that the following language is not context-free? $$ L= \{a^n b^m |\, gcd(n,m)=1 \}$$ I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.
user avatar
97 votes
10 answers

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 ...
Raphael's user avatar
  • 72.3k
5 votes
6 answers

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 ...
Gigili's user avatar
  • 2,193
11 votes
2 answers

How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
justausr's user avatar
  • 435

15 30 50 per page
4 5 6 7