Question: 14.14 Explain what is wrong with the following proof that the language L of the RE a b is nonregular. Suppose L were regular. Then

14.14 Explain what is wrong with the following "proof" that the language L of the RE a b" is nonregular. Suppose L were regular. Then it would be accepted by a DFA with, say, k states. Consider the string z-1k. Split z = uvw with u = 01, Then uu2w is not in L. This is a contradiction of the Pumping Lemma, and so our supposition is false

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!

5 . [ 4 marks ] Suppose that a DFA M = ( Q , , , q 0 , F ) accepts an infinite number of strings. Prove there is some string = w 1 w 2 wn , where | Q | n 2 | Q | , such that is accepted by M . 6 . [...

For the remaining problems, assume that all of the machines mentioned in the questions are over the alphabet 2a, b) Assume the strings representing machines mentioned in the questions are effective...

2. (7 points) Common Pumping Lemma Misunderstandings (a) (2 points) You are a CS4510 TA, and you are grading the following question: "Is the language L = {w w is a binary string with at least as many...

answer the question clearly You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case...

Please do part b Suppose M = (Q, 2,5,5,A) is a DFA. For states p,q EQ (p can be same as q) argue that Lpq = {w | 8*(p, w) =q} is regular. Recall that PREFIX(L) = {w|wx Lx 2*} is the set of all...

Suppose M = (0,2,5,5,A) is a DFA. For states p, q EQ (p can be same as q) argue that Lp,4 = {w | 8*(p,w) =q} is regular. Recall that PREFIX(L)={w|wx L, X 2*} is the set of all prefixes of strings in...

You are designing a new syntax for a programming language like Java, with the intention of making it more approachable to students by using English words instead of punctuation symbols. (a) How does...

1. (10 points) a. Use Pumping Lemma to prove that DOUBLE(Eo"1 I n 20]) is nonregular. b. Explain the problem in the following attempted proof that STUTTEREO"I" | n 20)) is nonregular: "Proof": In...

ret Electricity consumers are supplied with electricity from an electricity generating station. Electricity is distributed from the station to the various consumers through a network of transformers...

AMB Retail Inc. sells ceramic planters to its customers. Information about the planters stocked in inventory is given below. Purchased. Sold Cost Balance (Units) (Units) Date July 1 (Units) (Per...

Using a continuum with Order taker at one end and Order getter at the other, where would you place each of the following sales jobs? (a) Burger King counter clerk, (b) Automobile insurance...

Use production possibilities curves to explain the distinction between general and specific economic growth.

Moving to another question will save this response

3. List and explain the characteristics of effective 360-degree feedback systems.

4. Mentor-protg matching is based on how the mentors skills can help meet the protgs needs.

9. The mentor program is evaluated. Interviews with mentors and protgs are used to obtain immediate feedback regarding specific areas of dissatisfaction. Surveys are used to gather more detailed...