CSE 355 Fall 2015 HW1
CSE 355 Fall 2015 HW1 CSE 355
Popular in Intro Theoretical Computer Sci
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
Report this Material
What is Karma?
Karma is the currency of StudySoup.
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