×

Let's log you in.

or

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

×

or

by: Vito Kilback

32

0

5

ComputerScienceFoundations CS520

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

KurtSchmidt

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

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

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

×
Unlock Preview

COURSE
PROF.
KurtSchmidt
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

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

×

×

What is Karma?

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

×

25 Karma

×

×

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

Forbes

"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

STUDYSOUP CANCELLATION 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 support@studysoup.com

STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com