Week 2 - Pumping Lemma for CFL

Question 1

What is the pumping lemma for context-free languages? Use computional terms.

Answer 1

If L is a context-free language, then there exists a number p>=1 called the pumping length such that for any string w∈L such that |w|>=p, there exists u, v, x, y, z substrings of w satifying the following conditions:

1. w = uvxyz
2. ∀i>=0, u(v^i)x(y^i)z∈L (v and y can be ‘pumped’)
3. |vy| > 0
4. |vxy| <= p

If these are true then the language is context-free.

Question 2

TRUE OR FALSE: Let C be a CFL and R a regular language. Then, R ∩ C is a CFL.

Answer 2

TRUE.

Question 3

TRUE OR FALSE: Let C1 be a CFL and C2 be another CFL. Then, C1 ∩ C2 is a CFL.

Answer 3

FALSE, this isn’t always true.