Recursive Definitions for LanguagesNot only can we use regular expressions to define a language,but we can also define languages recursively. Here is anexample of such a definition:1) L2) if w L, then awb L3) A string w L only if it can be obtained from the basis(1) by finite number of applications of the recursive step.From this definition, it’s fairly easy to see that L = {anbn | n N}. However, just because we can “see it” doesn’t constitute a proof. We will use induction to prove this result for L, and thenlook at a few other similar examples.First, we will show that all strings of the form anbn L. We will use induction on n. Base case n=0 : a0b0 = L.Inductive Hypothesis : Assume for an arbitrary n=k that akbkL.Inductive Step : Under this assumption, we must prove for n=k+1 that ak+1bk+1L.ak+1bk+1 = a(akbk)b. (Let w = akbk.) = awb.By our inductive hypothesis, wL. Furthermore, step 2 tells us that if wL, then awb wL as well. Thus, we have deduced thatak+1bk+1 n L, as desired.It remains to be shown that all strings in L fit this form.Assume to the contrary that there exists a string in L NOT ofthe form anbn. We know that all strings in L (except for theempty string) start with a and end with b. (Why?) Let w be thesmallest string in L that is NOT of the form anbn. But, we knowthat w = axb, for some string x because w must start with a andend with b. By definition, for w to be in L, x must also be in L.BUT, if x is in L, we KNOW that x is NOT of the form anbneither. This contradicts the fact that w was the smallest suchstring in L. Thus, the string w does not exist, and all strings inL fit the form anbn.Here’s another problem:Let A = {a,b}Let L = {w | wA*, w either contains no occurrences of symbolb, or if w contains symbol b, then each occurrence of symbol bis followed immediately by at least one occerrences of thesymbol a.}Prove that L is a subset of the language whose regularexpression is a*((ba)a*)*.Let Nb(w) be the number of bs in the string w. We will proveour result using induction on Nb(w).Base case: Nb(w) = 0. This means that the string MUST be ofthe form a*. Notice that all strings of this form are part of thelanguage described by the regular expression above. (Why?)Inductive hypothesis. For an arbitrary value of Nb(w) = k,prove that w is an element of the language described bya*((ba)a*)*.Inductive Step: Prove for Nb(w) = k+1, that w is an element ofthe language described by a*((ba)a*)*.Let w L such that Nb(w) = k+1. That means that we canpartition w = xy where Nb(x) = k and Nb(y) = 1. By ourinductive hypothesis, we know that x L. Furthermore, we canassume that y= baa* since each b must be followed by at leastone a, and this is the last b. Thus, we have that w is a subset ofthe language denoted by the regular expressiona*((ba)a*)*baa*. But, using our rules of simplification, we findthat w is a subset of the langauage a*((ba)a*)*, thus w IS in L.Here’s another question:Let A = {a,b} denote an alphabet of two distinct symbols.Define a function g: A* A* by the following recursive rules:1) g() = 2) g(a) = b3) g(bu) = bg(u) for an u A*.4) g(aau) = g(au) for an u A*.5) g(abu) = bg(bu) for an u A*.Prove by induction that g(anb) = b2, for all integers n > 0.Use induction on n.Base Case: n=1. g(ab) = g(ab) = bg(b), using rule #5 = bbg() = bb = bb.Inductive Hypothesis: Assume for an arbitrary n=k, that g(akb)= b2.Inductive Step: Prove for n=k+1 that g(ak+1b) = b2.g(ak+1b) = g(aakb)= g(akb), using rule number 4. = b2 , using the inductive hypothesis.Here’s one more:Let A = {a,b}.Let C = {a}*{b}*, this is alternate notation describing the set ofstrings C directly.D = { w | w A*, and the number of occurrences of the symbola is the same as the number of occurrences of b.}Prove that C D = {anbn | n N}.Clearly {anbn | n N} C and {anbn | n N} D, just based onthe description of the sets C and D. Thus, in order to establishequality between the two sets, we must show thatC D {anbn | n N}.We will use proof by contradiction. Assume that there exists anx C D such that x{anbn | n N}. Since we have that x C,that means that x = yz, where y = ak and z = bl, for some non-negative integers k and l. Since we are assuming that x{anbn |n N}, we must have that kl. But, that contradicts the factthat xD. Thus, we can conclude that no such x exists and thatin fact, C D {anbn | n N}. Coupling that with our earlierobservation that {anbn | n N} C D, we can conclude that C D = {anbn | n N}.One Last ExampleLet W, T and Y denote 3 sets of strings over an alphabet A.Answer the following questions:a) Prove that (WT)* (WY)* (W(T Y))*.b) Use a counterexample to show that (W(T Y))* (WT)* (WY)*.We will prove the first by showing the following two facts:1) (WT)* (W(T Y))* and2) (WY)* (W(T Y))*.To show (1), note that WT W(T Y) because any string w =xy, where xW and yT will certainly be an element of W(T Y) because we have xW and yT Y. Now, using the rule thatif X Y, then X* Y*, we can deduce that (WT)* (W(T Y))*. We can show (2) in a similar fashion.Here is a counter example to show (W(T Y))* (WT)* (WY)* :Let A = {a,b}.W = {a}T = {a}Y = {b}Then we have aaab (W(T Y))* but aaab(WT)*
View Full Document