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...
Suppose a new process was developed that could be used to make oil out of seawater. The equipment required is quite expensive; but it would, in time, lead to low prices for gasoline, electricity, and...
The professor mentions several aspects of Japanese communication that frustrate foreigners. How should a foreign business visitor who is looking for straight answers and clear information deal with...
Journalize the entry for Hot Rod Service using the following data from the payroll register: Regular earnings $16,370 Overtime earnings 903 Federal income tax withheld 2,268 Social Security tax with...
Multiple Choice Question 67 On January 1, 2018, Coronado Industries granted stock options to officers and key employees for the purchase of 21600 shares of the company's $1 par common stock at $22...
Zippy Cola is studying the effect of its last advertising campaign. People chosen at random were called and asked how many cans of zippy cola they hand bought and advertisements they had either read...
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...
More and more healthcare institutions seek to reduce costs while increasing the quality of care. Accurate forecasts of the use of medical supplies represent an important element of this effort....
Listed below are the lead concentrations (in ug/g) measured in different Ayurveda medicines. Ayurveda is a traditional medical system commonly used in India. The lead concentrations listed here are...
The assignment states to use a movie and talk about 2 scenes where physics ideas are used. The rubric is shown and 6 big ideas that can be talked about are also attached. Background Information...
A series of computer and backup system failures caused the loss of most of the company records at Stotter, Incorporated. Information technology consultants for the company could recover only a few...
Future value of an annuity Using the values below, answer the questions that follow. (Click on the icon here in order to copy the contents of the data table below into a spreadsheet.) Deposit period...
Mercury, Incorporated, produces cell phones at its plant in Texas. In recent years, the company's market share has been eroded by stiff competition from overseas. Price and product quality are the...
What is the output of the code corresponding to the following pseudocode? Declare Dash As Character Declare A, B, C As Integer Set Dash For (A = 1; A
A bar of a steel alloy that exhibits the stress-strain behavior shown in Figure 6.22 is subjected to a tensile load; the specimen is 375 mm (14.8 in.) long and has a square cross section 5.5 mm (0.22...
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...
ABC Corporation has an activity - based costing system with three activity cost pools - Machining, Setting Up , and Other. The company's overhead costs, which consist of equipment depreciation and...
Consolidated Balance Sheets - USD ( $ ) $ in Thousands Dec. 3 1 , 2 0 2 3 Dec. 3 1 , 2 0 2 2 Current assets: Cash and cash equivalents $ 9 8 , 5 0 0 $ 6 3 , 7 6 9 Restricted cash 2 , 5 3 2 Short -...
How does corporate governance contribute to investor confidence and stakeholder trust? Accounting

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