Menu
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?
999
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.
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.
Question Do finite languages really satisfy the condition in the pumping lemma? Answer Yes, they do.
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.
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}
169
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.
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
