a. Let B = {1 k y| y {0, 1} * and y contains at least

Question:

a. Let B = {1^ky| y ∈ {0, 1}^* and y contains at least k 1s, for k ≥ 1}.

Show that B is a regular language.

b. Let C = {1^ky| y ∈ {0, 1}^* and y contains at most k 1s, for k ≥ 1}.

Show that C isn’t a regular language.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Introduction to the theory of computation

ISBN: 978-0470530658

3rd edition

Authors: Michael Sipser

See More Books

Question Posted: Sep 02, 2020 04:12 AM

See More Questions

Let = {0,1}. Let C 1 be the language of all strings that contain a 1 in their middle third. Let C 2 be the language of all strings that contain two 1s in their middle third. So C 1 = {xyz| x, z *...
Let Here, 2 contains all columns of 0s and 1s of height two. A string of symbols in 2 gives two rows of 0s and 1s. Consider each row to be a binary number and let C = {w * 2 | the bottom row of w...
Let 3 contains all size 3 columns of 0s and 1s. A string of symbols in 3 gives three rows of 0s and 1s. Consider each row to be a binary number and let B = {w * 3 | the bottom row of w is the sum...
A contractor has the opportunity to choose between building a house or doing two extension works in the next 6 months. If you build the house and sell it, you can make $25,000. However, if the...
Dr. J. D. Robinson also published the following estimate of the ideal body weight of a man: 52 kg + 1.9 kg for each inch over 5 ft (A) Find a linear model for Robinson's estimate of the ideal weight...
Define, discuss, and give one example (problem with solution). 1. What is LCM 2. What is GCF
The following table summarizes visits to emergency departments at four hospitals in Arizona. People may leave without being seen by a physician, and those visits are denoted as LWBS. The remaining...
An experiment was conducted to investigate leaking current in a SOS MOSFETS device. The purpose of the experiment was to investigate how leakage current varies as the channel length changes. Four...
a. What resources are shared among different threads in a multithreaded process? (10 points) b. Describe two differences between user-level and kernel-level threads. In what circumstances is one...
Minesweeper, the well-known computer game, is closely related to the wumpus world. A minesweeper world is a rectangular grid of N squares with M invisible mines scattered among them. Any square may...
Let = {0,1} and let D = {w|w contains an equal number of occurrences of the substrings 01 and 10}. Thus 101 D because 101 contains a single 01 and a single 10, but 1010 D because 1010 contains two...
Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output w R for every input w if the input and output alphabets are {0,1}. Exercise 1.24. A...
Why might more competition in financial markets be a bad idea? Would restrictions on competition be a better idea? Why or why not?
Define and provide examples of the conformity, nonconformist, and learning perspectives of human nature.
Briefly explain the difference between psychological criminology and sociological criminology. How do these differ from a psychiatric approach to the study of criminal behavior?
What is the primary advantage of buying an automobile versus leasing? A. Income tax deduction. B. Insurance costs. C. Ownership. D. Size of down payment.
Describe the factors associated with the brain that are involved in regulating aggressive and violent behavior.
Which of the following investment vehicles are most appropriate for an emergency fund for a family with discretionary income of $12,000 a year? I. Balanced index ETF. II. CD ladder with maturities...
The following data relate to direct labor costs for the production of smart tablets. Actual: ......... 6,300 hrs. at $23.00.............. $144,900 Standard: ...... 6,300 hrs. at $24.50 .................
Use the graphs of f and g to graph h(x) = (f + g) (x). To print an enlarged copy of the graph, go to MathGraphs.com. 1. 2. y 24 8. 2. -2 -2 4 6
Write a program that consists of three classes, A, B, and C, such that B extends A and that C extends B. Each class should define an instance variable named x (that is, each has its own variable...
Explain the changes that would have to be made to the program of Code Fragment 3.8 so that it could perform the Caesar cipher for messages that are written in an alphabet-based language other than...
The removeFirst method of the SinglyLinkedList class includes a special case to reset the tail field to null when deleting the last node of a list (see lines 51 and 52 of Code Fragment 3.15). What...
The sheet Inventory lists a grocery store's inventory for two months. Calculate the percent change for each item to two decimal places. If the formula gives an error, put "Initial Stock" in the cell....
A local manufacturer produces two different products on the same production line. Product A requires .5 hours of labor while product B requires .8 hours of labor. The total labor available in any one...
Hampton Company reports the following information for its recent calendar year. Income Statement Data Sales Expenses: Cost of goods sold Salaries expense Depreciation expense Net income Required:...

a. Let B = {1 k y| y {0, 1} * and y contains at least

Question:

Step by Step Answer:

a To show that B is a regular language we can construct a finite automaton FA that recognizes it A s...View the full answer

Introduction to the theory of computation

Students also viewed these Computer science questions