New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Vito Kilback

ComputerScienceFoundations CS520

Marketplace > Drexel University > ComputerScienence > CS520 > ComputerScienceFoundations
Vito Kilback
GPA 3.88


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




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.

Similar to CS520 at Drexel

Popular in ComputerScienence


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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.