Prove that l is not regular using pumping theorem

Assignment Help Theory of Computation

Reference no: EM1357376

Define a color word to be an English word that is the name of a color. So some example color words are red, fuschia, and ochre. Define an animal word to be an English word that is the common name of an animal. So some example animal words are cow, cats, and hippopotamus. Let L = {w : w is a sentence with legal English syntax and the number of color words in w equals the number of animal words in w}. As examples, observe that red cats like catnip ∈ L, but red cats like blue green balls ∉ L. Note that, to be in L, w must satisfy the syntactic rules of English. It is not necessary for w to make sense. So, for example, red red blue red cats like dogs and dogs and dogs ∈ L. Prove that L is not regular. (Be particularly careful if you use the Pumping Theorem. You must choose a w that is actually in L.)

Reference no: EM1357376

Questions Cloud

Find magnitude of acceleration of the boy toward the girl : A hunter aims directly at a target (on the same level) 113 m away. If the bullet leaves the gun at a speed of 255 m/s, by how much will it miss the aim.

Show what you want to be measured by analyzing ksao : you should show what you want to be measured by analyzing KSAO's from the job description and the information on organizational culture in the case.

Self-performance appraisal - human resources : Accomplishments: Explain any accomplishments achieved by the employee since the last review. What contributions did the employee make this year? Did employee meet goals set forth during last review?

Find out the magnitude of the electrostatic force : An airplane flies 200 km due west from city A to city B and then 300 km in the direction of 30 degrees North of West from city B to city C. In straight-line distance, how far is city C from city A.

Prove that l is not regular using pumping theorem : Prove that L is not regular. (Be particularly careful if you use the Pumping Theorem. You must choose a w that is actually in L.)

Calculate financial ratios : I have several things to accomplish for an indepth corporation analysis on GM for three years. I am having difficulty with collecting the information and doing the ratios. I then have to answer the following questions.

Illustrate what is the cost of an extra minute on the phone : Your demand for minutes of calling is given by the equation: Q_d = 150-50*P, where P is the price of a minute. illustrate what is the cost of an extra minute on the phone.

Negotiations- influencing decision making : Under what conditions would someone readjust their "no" position to a "yes? in negotiation" What are the influences? How can you "stay with no? In negotiations"

Development of phobias and mate selection : Do you feel that one's environment can also affect development of phobias and mate selection?

User Account

All Pages