×

### Let's log you in.

or

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

×

or

by: Jerry H.

98

1

8

# CSE 355 Fall 2015 HW1 CSE 355

Jerry H.
ASU

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

×
Unlock Preview

Homework for reference
COURSE
Intro Theoretical Computer Sci
PROF.
Colbourn
TYPE
Test Prep (MCAT, SAT...)
PAGES
8
WORDS
KARMA
75 ?

## Popular in Computer Science and Engineering

This 8 page Test Prep (MCAT, SAT...) was uploaded by Jerry H. on Monday January 18, 2016. The Test Prep (MCAT, SAT...) belongs to CSE 355 at Arizona State University taught by Colbourn in Winter 2015. Since its upload, it has received 98 views. For similar materials see Intro Theoretical Computer Sci in Computer Science and Engineering at Arizona State University.

×

## Reviews for CSE 355 Fall 2015 HW1

×

×

### 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: 01/18/16
CSE 355 HOMEWORK ONE DUE 16 SEPTEMBER 2015, START OF CLASS (1) Give a state diagram and the table specifying the transition function, for a DFA to recognize (a) L 1 fw 2 f0;1g : w either starts with 10 or ends with 01, but not bothg ? (b) L 2 fw 2 f0;1g : w contains 00 as a substring an odd number of timesg Note: 000 contains two occurrences of 00 as a substring. ? (c) L 3 fw 2 f0;1;2g : w is the ternary (base 3) representation of a number that is divisible by 2g ? (d) (not to be graded) L = fw42 f0;1;2;3g : w is the quaternary (base 4) representa- tion of a number that is divisible by 4g (e) (not to be graded) L = fw 2 f0;1g : w is the binary representation of a number 5 that is not divisible by 3 or 7g (2) Give a state diagram for an NFA with as few states as you can to recognize ? (a) L 6 fw 2 f0;1g : w starts with a 1 or ends with a 1g (b) L = fw 2 f0;1g : w contains the substring 010101g 7 (c) L 8 L 6 (d) (not to be graded) L = fw 2 f0;1g : w has odd length and an odd number of 1s, 9 or starts with a 0g (e) (not to be graded) L 10= fw 2 f0;1g : w has more occurrences of the substring 01 than of the substring 10g. (3) Using the languages from Question 1 and the method of Theorem 1.25, give a state diagram and/or the table specifying the transition function, for a DFA to recognize (a) L 1 L 2 (b) L 1 L 3 (c) L 1 L3 (d) L 3 L 3 Do not simplify the DFA produced. ? rev (4) If w = w 1▯▯w (wk2 ▯ifor 1 ▯ i ▯ k) is a string in ▯ , the string w , the reversal of w, is the string wk▯▯▯w .1The reversal of language L is L rev = fw rev : w 2 Lg. I think that rev whenever L is regular, L is also regular. My friend tells me that showing this is easy: Just take a DFA M that recognizes L and reverse all of the transitions to get a DFA that rev recognizes L . Does my friend’s idea work? Answer yes or no, and explain. (5) A subsequence of a string w is de▯ned to be a string obtained 0 or more symbols (not necessarily consecutive) from w. For example, copter is a subsequence of computers. You are given a DFA M to recognize a regular language L. You want to make an NFA that recognizes all subsequences of strings in L, that is subseq(L) = fw 2 ▯ : w is a subsequence 0 of x for some x 2 Lg. Devise (and explain) a general method for producing an NFA M that recognizes subseq(L), given only the description of M. Justify why your method works. 1

×

×

### BOOM! Enjoy Your Free Notes!

×

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!"

Kyle Maynard Purdue

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made \$280 on my first study guide!"

Bentley McCaw University of Florida

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