Week 1 - Pumping Lemma

Question 1

TRUE OR FALSE: All languages are regular.

Answer 1

FALSE, some languages don’t have NFA’s.

Question 2

What is the pumping lemma?

Answer 2

A rule that states that any regular language satifies a certain property - the pumping property.

Question 3

What is the property that a regular language satifies called?

Answer 3

The pumping property.

Question 4

How can you prove that a language is not regular without having to go through all possible NFAs?

Answer 4

You can use the pumping lemma rule to demonstrate that language does not have a pumping property.

Question 5

How do you prove that a regular expression has a pumping property? Use computational terms.

Answer 5

If L is a regular language, then there exists a number p∈N (Natural numbers), called the pumping length such that for any string w∈L with |w| >= p, there exists substrings x,y,z of w that satify the following conditions:
w = xyz
∀i > = 0
xy^iz ∈ L
|y| > 0
|xy| <= p

If this is true, then the language is not regular.