edited by
125 views
0 votes
0 votes

Use the $CFL$ pumping lemma to show each of these languages not to be context-free$:$

  1. $\left\{a^{i}b^{j}c^{k}|i<j<k\right\}.$
  2. $\left\{a^{n}b^{n}c^{i}|i\leq n\right\}.$
  3. $\left \{0^{p}| \text{p is a prime} \right \}.$
  4. $\{0^{i}1^{j}|j=i^{2}\}.$
  5. $\{a^{n}b^{n}c^{i}|n\leq i\leq 2n\}.$
  6. $\{ww^{R}w|\text{w is a string of $0's$ and $1's$}\}.$ That is the set of strings consisting of some string $w$ followed by the same string in reverse, and then the string $w$ again ,such as $001100001.$
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
4