Popular in Course
Popular in ComputerScienence
This 5 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS520 at Drexel University taught by KurtSchmidt in Fall. Since its upload, it has received 32 views. For similar materials see /class/212442/cs520-drexel-university in ComputerScienence at Drexel University.
Reviews for ComputerScienceFoundations
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
Exercise 1125 Partial Solution This solution differs a bit from the one provided earlier that solution inducted over the of productions applied rather than the height of the expression tree They are very similar however We are to show that the following grammar generates the balanced pro le strings as de ned in section 26 o ltBalancedEgt gt s o ltBalancedEgt gt ltBalancedEgt lt1 I 11quot lt1 I 11quot lt1 I 11quot Part I Show that all strings in LltBaIancedEgt are pro lebalanced We will use induction on the height of the expression tree that produces strings 3 LltBaIancedEgt Our base case is simple We have only one possible tree of height one ltBalancedEgt Trivially s the empty or null string is balanced So by the inductive hypothesis we may assume that any such tree of height lt n produces a pro lebalanced string 2 Section 26 de nes a pro le balanced string 3 so Set ctr0 scan 3 from left to right For each character that is encountered increment ctr For each that is encountered decrement ctr If and only if after the entire string 3 is scanned ctr is 0 and it at no time was negative then s is pro lebalanced We now need to show that any string 3 represented by an expression tree of height n1 is also balanced There are 2 productions in the grammar that allow us to build on existing expressions Lets consider ltBalancedEgt n I 11quot n I 11quot n I JT lt gt lt lt ltBalancedEgt ltBalancedEgt I l i g i I l Represented 39 v s1 52 If the tree rooted at the red node has height n1 then the 2 blue and green have height lt n so by our hypothesis 3 and 32 are pro le balanced We need to show that the string s 31 32 is pro le balanced Start on the left ctr 0 After we scan 31 ctr is 0 and was never negative We then scan 32 and again by our hypothesis ctr is 0 and was never negative We scanned s ctr is 0 and was never negative so by the de nition from 26 s is pro le balanced We have another possible tree of height n1 that we need to consider given to us by the production ltBalancedEgt ltBalancedEgt gt ltBalancedEgt ltBalancedEgt v s We need to show that s s is pro le balanced Same game ctr 0 start at the left ctr 1 By the hypothesis 3 is balanced so after parsing it ctr is still 1 and further was never less than I speci cally was never negative Hit that last ctr is back to 0 By de nition 3 is pro le balanced Done We would now want to show that all possible pro lebalanced strings of parenthesis can by generated from ltBalancedEgt I can offer no improvement over the solution previously provided Show that any pro lebalanced string 3 is an element of L ltBalancedEgt We will induct over the length of s We are using strong induction We need to get away from the n n1 thing it ll bog us down since think about it parenthesis need to be added in pairs We start with s a balanced string of length 0 We verify that it is in L ltBalancedEgt We may now assume that all strings of length lt n are elements of the language We then need to consider strings of length n Are they balanced We use the de nition from 26 our ctr from above Start it at 0 When we re done we know ctr is 0 We have 2 cases to consider ctr reached 0 sometime before we reached the end of s so we have a concatenation 2 strictly smaller strings which by the hypothesis are both in the language 2 ctr didn t reach 0 until the very last character in which case have a strictly smaller string of length n2 nested inside parenthesis You simply need to verify that in each case the grammar takes a valid string or strings and can produce 3 of length n tart 5144 quot 714 I to A quotV 4 n 124 l 4 01 I A 5 I r b 4 04 n I 4 I 4 IrI I u Azidg39z by 010 p277 T 4 a 010 i 59 731m MB erB F catmtwwmJ l N019 Tii39 In Xwatiik 8 1032005 I W 5 1 48 7 512 AI3157 5AM 74 CWT2m 2 an2 1b2quot 1rr v CinZ39 r5 2quot 7 TV 42
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'