Question: 1. Prove countable by finding the 1-1 and onto correspondence with the natural number N a. Strings over {a,b). that begin with a b. Strings

1. Prove countable by finding the 1-1 and onto correspondence with

1. Prove countable by finding the 1-1 and onto correspondence with the natural number N a. Strings over {a,b). that begin with a b. Strings over {a,b} with even number of a's C. How many languages over {a,b} are there that only contain strings with an even number of a's and an even number of b's? 2. Write (1) DFA and (ii) smallest NFA you can think of for strings over {0,1} a. Begin and end with 00 b. Contain the substring 00 C. Do NOT contain the substring 00 3. Some regular expressions are easy to write; some hard./ a. Write a regular expression for strings over {a,b} that end "aab b. In class we wrote this expression for stings NOT containing the substring aab a* b*a*|(b*ab*aa*)* The a* is not needed -- can just be dropped. Why? Can you think of a string that should be generated and is not? If so, what? Can you think of a string that this generates which is not legal? If so, what? = d. Can you find a correct expression for string NOT containing "aab? If so, what is it? 4. (Old Capstone) Give regular expressions describing each of the following languages over { = {0, 1}: a. {w: the fourth symbol of wis a 0} b. {w: wis odd} C. {w: w contains either substring 000 or substring 111} d. {w: every 0 in w is immediately followed by a 1} e. {w:w+2} 5. Write simpler NFAs for these languages a. (aa)*(bb)* b. (aba)* | (bab)* c. (aa | bb)* aab d. a*bb ba* al b 42 6. Convert the NFA to a DFA (Sipser algorithm Th 11.39)

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

On January 1, 2024, the general ledger of Dynamite Fireworks includes the following account balances: Accounts Cash Accounts Receivable Supplies Land Accounts Payable Common Stock Retained Earnings...

1. Prove countable by finding the 1-1 and onto correspondence with the natural number N a. b. Strings over {a, b). that begin with a Strings over {a,b} with even number of a's c. How many languages...

1. Prove countable by finding the 1-1 and onto correspondence with the natural number N Strings over {a, b). that begin with a Strings over {a,b} with even number of as How many languages over {a,b}...

1. [10pt] Prove by induction the following claims (5pt each): (a) For an arbitrary fixed string w, prove that w" = n w for any natural number n E N. (b) (WC) R = RUR for all strings w and 2 in *. (WR...

Induction (#1-3, 24 pts) #1 . Prove by induction that8 + 15 + 22 + 29 + ... +(7 n + 1) = n (7 n + 9)/2for all n N . #2. Prove the summation formula for the following particular finite geometric...

201609 Math 122 Assignment 4 Due: Monday, November 14 or Tuesday, November 15, in class, before the lecture starts There are five questions (40 marks), and one bonus question (4 marks), on the two...

Please use C++ for this program. Please read the problem and follow the instruction in main.cpp for this program. Problem: - Design an abstract class called Shape: - Private variables double x and...

1) Find all real solutions of: 4 2 2 x + x =3 2 x 4 + x23=0 4 2 2 2 x 2 x +3 x 3=0 x ( 21)=0 2 x 2 ( x 21)+ 3 ( 2 x2 +3 ) ( x 21 ) =0 ( 2 x2 +3 ) =0 2 2 x =3 3 x 2= 2 3 x= 2 3 x= i 2 2) Given the...

\f\f\f\f\f\f\f\f\f\fSequences, Mathematical Induction and Recursion 1 5.1 Sequences 2 Sequences Sequences represent ordered lists of elements. A sequence is defined as a function from a subset of N...

Please solve all of this as soon as possible. QUESTION 7 Given the function f:Z - Z, defined by f (n) = = 1) Graph the function. 2) Determine if the function is a bijection (or one-to-one...

tP" 99951539" IO 11, 12. 13. 14, MEMORIAL UNIVERSITY OF NEWFOUNDLAND DEPARTMENT OF MATHEMATICS AND STATISTICS Assignment 7 Mathematics 2320 Winter 2017 Due: March 17 , 2017 . SHOW ALL WORK . Find q...

A problem often discussed in the engineering economy literature is the "oil-well pump problem."} Pump 1is a small pump; Pump 2 is a larger pump that costs more, will produce slightly more oil, and...

The following accounts are applicable to Dales Lawn Service, a company that maintains condominium grounds: 1. Cash 2. Accounts Receivable 3. Supplies 4. Equipment 5. Accounts Payable 6. Lawn Services...

large international firms deal in considerable volumes of goods, they often need to obtain specific requirements. What is the name of the requirement obtained from a of banks known as a syndicate? A...

Seved Help 14 Wisconsin Snowmobile Corp. is considering a switch to level production Cost efficiencies would occur under level production, and aftertax costs would decline by $31,500, but inventory...

3. [From your subordinates] We really think that we deserve more money for doing this job. a. Thats silly. Youre really not worth what were paying you now. b. You know that the legislature wont give...

5. [From a citizen] Can you tell me who to talk with about a junk car that Id like to have removed from the vacant lot next door? a. Thats not my department. b. Ask the secretary over there. c. That...

3. How would you advise Anita to proceed if she wants to stay in the organization and be successful? How can she increase her influence and power in the organization?