Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are there any examples of pumping lemmas with "real" languages?

The pumping lemma is a property of regular languages and context-free languages. But all the examples I've seen are things like:

L = {0n1n2n : n ≥ 0}

(which, incidentally, is not a context-free language).

But what I'm interested in is this: are there any examples of its use with any remotely real or useful languages? I haven't been able to find any. Is this one of those things or purely theoretical value with absolutely no practical application?

like image 999
cletus Avatar asked Jan 26 '10 01:01

cletus


People also ask

What are the applications of pumping lemma for regular languages?

Applications of Pumping Lemma Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular. If L is regular, it satisfies Pumping Lemma. If L does not satisfy Pumping Lemma, it is non-regular.

Can you prove a language is regular with pumping lemma?

Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular. The opposite of this may not always be true.

Do all finite languages satisfy the pumping lemma?

Question Do finite languages really satisfy the condition in the pumping lemma? Answer Yes, they do.

Where is pumping lemma used?

The pumping lemma is often used to prove that a particular language is non-regular. Pumping lemma for regular language is generally used for proving a given grammar is not regular. Hence the correct answer is a given grammar is not regular. Pumping Lemma is to be applied to show that certain languages are not regular.


2 Answers

L = {0n1n : n ≥ 0} being a context-free language.

Parenthesis matching in an expression can be considered to be of similar form i.e.

L = { (n )n : n ≥ 0}

like image 169
Arnkrishn Avatar answered Oct 17 '22 09:10

Arnkrishn


this python program is valid:

print ((((((((((((((((((((((((1))))))))))))))))))))))))

as well as all other equivalent statements with an equal amount of ( on the left and ) on the right side.

You cannot build a regular expression to verify that, thus you have to use a parser.

It is not at all theoretical. It is the reason why you cannot use regex to parse HTML.

like image 24
Otto Allmendinger Avatar answered Oct 17 '22 07:10

Otto Allmendinger