Which of the following terms describes a technique from automata theory used to prove non-regularity by showing a long string can be pumped?

• A. Pumping Lemma
• B. Closure Property
• C. Regular Grammar
• D. Context-Free Grammar

Answer: (A)

Pumping lemma for regular languages is the technique used to prove non-regularity by showing a long string can be pumped. For any regular language, there exists a pumping length p such that any string s with length at least p can be split into three parts s = xyz, with the conditions that y is not empty and the combined length of x and y is at most p. Then for every i ≥ 0, the string xy^i z must also be in the language. This gives a way to reach a contradiction: assume the language is regular, pick a string that forces a fixed region to be pumped, and show that pumping y any number of times produces a string that should be in the language but isn’t.

For example, to show the language {a^n b^n} is not regular, suppose a pumping length p exists. take s = a^p b^p. The segment y, which lies within the first p a’s, consists only of a’s. Pumping down with i = 0 yields a^{p - |y|} b^p, which has fewer a’s than b’s and thus is not in the language. This contradiction shows the language is not regular.

Other options don’t describe this specific testing method. Closure properties talk about how regular languages behave under operations like union, concatenation, and star. Regular grammar and context-free grammar describe forms of grammatical representation and do not provide the pumping-based test for non-regularity.