Recursive Definitions for Languages Not only can we use regular expressions to define a language but we can also define languages recursively Here is an example of such a definition 1 L 2 if w L then awb L 3 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 then look 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 akbk L Inductive Step Under this assumption we must prove for n k 1 that ak 1bk 1 L ak 1bk 1 a akbk b Let w akbk awb By our inductive hypothesis w L Furthermore step 2 tells us that if w L then awb w L as well Thus we have deduced that ak 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 of the form anbn We know that all strings in L except for the empty string start with a and end with b Why Let w be the smallest string in L that is NOT of the form a nbn But we know that w axb for some string x because w must start with a and end 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 a nbn either This contradicts the fact that w was the smallest such string in L Thus the string w does not exist and all strings in L fit the form anbn Here s another problem Let A a b Let L w w A w either contains no occurrences of symbol b or if w contains symbol b then each occurrence of symbol b is followed immediately by at least one occerrences of the symbol a Prove that L is a subset of the language whose regular expression is a ba a Let Nb w be the number of bs in the string w We will prove our result using induction on Nb w Base case Nb w 0 This means that the string MUST be of the form a Notice that all strings of this form are part of the language 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 by a ba a Inductive Step Prove for Nb w k 1 that w is an element of the language described by a ba a Let w L such that Nb w k 1 That means that we can partition w xy where Nb x k and Nb y 1 By our inductive hypothesis we know that x L Furthermore we can assume that y baa since each b must be followed by at least one a and this is the last b Thus we have that w is a subset of the language denoted by the regular expression a ba a baa But using our rules of simplification we find that 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 b 3 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 of strings C directly D w w A and the number of occurrences of the symbol a 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 on the description of the sets C and D Thus in order to establish equality between the two sets we must show that C D anbn n N We will use proof by contradiction Assume that there exists an x C D such that x anbn n N Since we have that x C that means that x yz where y a k and z bl for some nonnegative integers k and l Since we are assuming that x anbn n N we must have that k l But that contradicts the fact that x D Thus we can conclude that no such x exists and that in fact C D anbn n N Coupling that with our earlier observation that anbn n N C D we can conclude that C D anbn n N One Last Example Let 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 and 2 WY W T Y To show 1 note that WT W T Y because any string w xy where x W and y T will certainly be an element of W T Y because we have x W and y T Y Now using the rule that if 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 WY
View Full Document
Unlocking...