Let ∑ = {0,1, 2, 3, 4, 5, 6, 7, 8, 9, +, =} and consider the language L of all strings over ∑ that constitute a valid equation of the form a + b = c where a, b, and c are non-negative integers represented in base 10, without leading zeros. Some elements of L include 13 + 17 = 30 and 90 + 0 = 90, but not 13 + 17 = 29 or 90 + 01 = 100. Use the Pumping Lemma to prove that L is not regular
To prove that the language L = {a + b = c | a, b, and c are non-negative integers in base 10} is not regular using the Pumping Lemma, we will assume that L is regular and derive a contradiction.
The Pumping Lemma states that for any regular language L, there exists a constant p (the pumping length) such that any string s in L with |s| ≥ p can be divided into three parts, s = xyz, satisfying the following conditions:
1. |xy| ≤ p
2. |y| > 0
3. For all k ≥ 0, xy^kz is also in L.
Let's assume that L is regular and choose a pumping length p.
Consider the string s = p + p = 2p, where p is a prime number greater than or equal to p. The string s is clearly in L, as the equation p + p = 2p is valid for non-negative integers.
Now, let's consider all possible ways of dividing the string s = xyz subjected to the three conditions of the Pumping Lemma.
First, let's consider the case where y contains only digits (0-9). Since |xy| ≤ p and y must contain at least one digit (condition 2), then y consists of digits from the first p digits of s, which represent the number p. Therefore, by pumping y, we would be increasing the number p. However, this would result in a string that is no longer of the form a + b = c, as the equation p + p ≠ 2p would be violated. Hence, xy^kz would not be in L for some k ≥ 0, contradicting condition 3 of the Pumping Lemma.
Next, let's consider the case where y contains only the symbols "+" and "=" of the equation. Again, since y must contain at least one symbol (condition 2), then y consists of only the symbols "+=" from s. If we pump y, adding more occurrences of "+=", it would cause the equation to be unbalanced and not valid anymore. Hence, xy^kz would not be in L for some k ≥ 0, contradicting condition 3 of the Pumping Lemma.
Finally, let's consider the case where y contains both digits and symbols "+=". Similarly, pumping y would lead to an unbalanced equation, violating the condition a + b = c.
In all possible cases, pumping y leads to a string that is not in L. Thus, we have reached a contradiction, proving that L is not regular.
Therefore, according to the Pumping Lemma, the language L = {a + b = c | a, b, and c are non-negative integers in base 10} is not regular.