DOC PREVIEW
UCF COT 3100 - Recursive Definitions for Languages

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 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 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 | wA*, 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 kl. But, that contradicts the factthat xD. 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 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 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

UCF COT 3100 - Recursive Definitions for Languages

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download Recursive Definitions for Languages
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursive Definitions for Languages and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursive Definitions for Languages 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?