### Create a StudySoup account

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

Already have a StudySoup account? Login here

# THEORY CS 150

UCR

GPA 3.88

### View Full Document

## 46

## 0

## Popular in Course

## Popular in ComputerScienence

This 1 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 150 at University of California Riverside taught by Staff in Fall. Since its upload, it has received 46 views. For similar materials see /class/231755/cs-150-university-of-california-riverside in ComputerScienence at University of California Riverside.

## Reviews for THEORY

### 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: 10/29/15

CS 150 Discussion Notes 1 Eliminating Useless Symbols Theorem Let G V T P S be a CFG and assume that LG 1 ie G generates at least one string Let Gl V 1 T1 Pl S be the grammar we obtain by the following steps 1 First eliminate nongenerating symbols and all production s involving one or more of those symbols Let G2 V2 T2 P2 S be this new grammar Note that S must be generating since we assume LG has at least one string so S has not been eliminated 2 Second eliminate all symbols that are not reachable in the grammar G2 Then G1 has no useless symbols and LGl LG Example Consider the grammar S gt AB l a A gt b All symbols but B are generating a and b generate themselves S generates a and A generates b If we eliminate B we must eliminate the production S gt AB leaving the grammar S gt a A gt b Now we nd that only S and a are reachable from S Eliminating A and b leaves only the production SA a That production by itself is a grammar whose language is a just as is the language of the original grammar Note that if we start by checking for reachability rst we nd that all symbols of the grammar S gt AB l a A gt b are reachable If we then eliminate the symbol B because it is not generating we are left with a grammar that still ahs useless symbols in particular A and b 2 Eliminating kProductions Example Consider the grammar S gt AB A gt aAA l A B gt bBB l 7 First let us nd the nullable symbols A and B are directly nullable because they have production with 7 as the body Then we nd that S is nullable because the production S gt AB has a body consisting of nullable symbols only Thus all three variables are nullable Now let us construct the productions of grammar Gl First consider S gt AB All symbols of the body are nullable so there are four ways we could choose present or absent for A and B independently However we are not allowed to choose to make all symbols absent so there are only three productions S gt AB l A l B Next consider production A gt aAA The second and third positions hold nullable symbols so again there are four choices of presentabsent In this case all four choices are allowable since the nonnullable symbol a will be present in any case Our four choices yield productions A gtaAAl aAl aAl a Note that the two middle choices happen to yield the same production since it doesn t matter which of the A s we eliminate if we decide to eliminate one of them Thus the nal grammar Gl will only have three productions for A Similarly the production B yields for G1 B gt bBB l bB l b The two Xproduction of G yield nothing for G1 Thus the following productions S gt AB l A l B A gtaAAl aAl aAl a B gt bBB l bB l b Constitute G1 3 Eliminating Unit Productions Algorithm To eliminate unit productions we proceed as follows Given a CFG G V T P S construct CFG G1 V T Pl S 1 Find all the unit pairs of G 2 For each unit pair A B add to P1 all the productions A gt a where B gt a is nonunit production in P Note that AB is possible in that way Pl contains all the nonunit productions in P

### 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

#### "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."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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

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.