= {a,b,c}, L = { s : #a (s) = max ( #b (s), #c (s) ) }. Use the pumping theorem
ID: 3743089 • Letter: #
Question
= {a,b,c}, L = { s : #a (s) = max ( #b (s), #c (s) ) }. Use the pumping theorem to show that L is not a regular language. For example, cab L, but abbc L.
Points to remember when constructing this proof: • Start by expressing w in terms of k, where w L, and |w| k.
• The goal is to show that for every possible value y, where w = xyz, q(q 0, xyqz L).
† For each equivalence class for y, state if you are pumping in or out, and if pumping in how many times.
† Do not propose literal values for k, y, or |y|. For example, you cannot assume that |y| is 1, or say something like "let y = ab", or "let k = 1".
• Formulas for x and z (the non-pumpable parts of w) are rarely useful. Please do not use them in your proofs.
Explanation / Answer
L={S:#a(S)=max(#b(s),#c(s))}
L is also not regular. To prove this, we need first to prove a lemma, which we’ll call EQAB: s, s
L => #a(s) = max(#b(s),#c(s)). To prove the lemma, we first observe that any string s in L must be able to be
decomposed into at least one finite sequence of strings, each element of which is in L. Some strings will have
multiple such decompositions. In other words, there may be more than one way to form s by concatenating
together strings in L. For any string s in L, let SQ be some sequence of elements of L that, when concatenated
together, form s. It doesn’t matter which one. Define the function HowMany on the elements of L.
HowMany(x) returns the length of SQ. Think of HowMany as telling you how many times we went through the
Kleene star loop in deriving x. We will prove EQAB by induction on HowMany(s).
Base case: If HowMany(s) = 0, then s = . #a(s) = max(#b(s),#c(s)).
Induction hypothesis: If HowMany(s) N, then #a(s) = max(#b(s),#c(s)).
Show: If HowMany(s) = N+1, then #a(s) = max(#b(s),#c(s)).
If HowMany(s) = N+1, then w,y,z such that s = wyz, w L, HowMany(w) = N, and y L. In other words,
we can decompose s into a part that was formed by concatenating together N instances of L plus a second part
that is just one more instance of L. Thus we have:
(1) #a(y) = max(#b(y),#c(z)). Definition of L
(2) #a(w) = max(#b(w),#c(z)). Induction hypothesis
(3) #a(s) = #b(w) + #b(y) +#b(z).
or
(4)#a(s)=#c(w)+#c(y)+#c(z).
(4) #b(s)= #b(w) + #b(y)+#b(z).
(5) #b(s)= #a(w) + #b(y) + #c(z).
(6) #c(z)= #a(w) + #a(y) + #c(z).
(7) #c(z) = #a(s) + #a(y)+ #a(z).
s = wy z
s = wy z
4, 2
5, 1
6, 3
Q. E. D.
Now we can show that L isn’t regular using the pumping lemma. Let w = aN bM c L. Since y must occur within the
first N characters of w, y = a p for some p > 0. Thus when we pump y in, we will have a string with more a’s
than b’s and c's. By EQAB, that string cannot be in L.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.