(a) Prove that the language L = {12/3221} is not regular by using the Pumping Lemma....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Prove that the language L₁ = {12/3221} is not regular by using the Pumping Lemma. Use the string 1"2"32" and i = 3 at appropriate points in the proof. (b) Write out the proof of the same result which uses the string 132 and i=0 instead. Which steps are different? Which steps remain the same? (e) There are some errors in the proof below that the language L₂ = {1'2' #32 @2'1'} is not context-free. Find and correct all such errors. The best way to do this is to write out the correct proof, highlighting the differences between the correct proof and the one below. Claim: The language L₂ = {12 #32 @21'} is not context-free. Proof: Assume L2 is regular. Then the Pumping Lemma applics and so for some n1 such that for some w L such that wn, w = xyzuv where • lyzu❘ ≤n ⚫y and uλ ry' zu've L for all i > 0 w= Choose w 12" 32" @2"1" and so we L and w≥n. So by the Pumping Lemma w = xyzuv = 12 #32@2"1" and lyzul <n. This means that y and u can contain at most two of 1, 2 and 3. We will refer to the part of the string before #as zone 1, the part of the string between # and @ as zone 2, and the part of the string after @as zone 3. Now if y or u contains # or @, then clearly ryzuv & L, as this would contain two occurrences of either # or @. Hence neither unor v contains either # or @. Now note that both y and u can only cover at most two of zone 1, zone 2, and zone 3, as yzul <n. This means that ryzuv € L, as one of the zones will have the same string as w, but the other two will have longer strings, and hence ryzuv is not of the form 12 #3202'1'. This is a contradiction, and so L2 is not context-free. (d) Let L be a regular language over the alphabet {0, 1}. Use the Pumping Lemma to show that n≥1 such that for all we L where wn, there is another string such that rЄL and [r] <n. (a) Prove that the language L₁ = {12/3221} is not regular by using the Pumping Lemma. Use the string 1"2"32" and i = 3 at appropriate points in the proof. (b) Write out the proof of the same result which uses the string 132 and i=0 instead. Which steps are different? Which steps remain the same? (e) There are some errors in the proof below that the language L₂ = {1'2' #32 @2'1'} is not context-free. Find and correct all such errors. The best way to do this is to write out the correct proof, highlighting the differences between the correct proof and the one below. Claim: The language L₂ = {12 #32 @21'} is not context-free. Proof: Assume L2 is regular. Then the Pumping Lemma applics and so for some n1 such that for some w L such that wn, w = xyzuv where • lyzu❘ ≤n ⚫y and uλ ry' zu've L for all i > 0 w= Choose w 12" 32" @2"1" and so we L and w≥n. So by the Pumping Lemma w = xyzuv = 12 #32@2"1" and lyzul <n. This means that y and u can contain at most two of 1, 2 and 3. We will refer to the part of the string before #as zone 1, the part of the string between # and @ as zone 2, and the part of the string after @as zone 3. Now if y or u contains # or @, then clearly ryzuv & L, as this would contain two occurrences of either # or @. Hence neither unor v contains either # or @. Now note that both y and u can only cover at most two of zone 1, zone 2, and zone 3, as yzul <n. This means that ryzuv € L, as one of the zones will have the same string as w, but the other two will have longer strings, and hence ryzuv is not of the form 12 #3202'1'. This is a contradiction, and so L2 is not context-free. (d) Let L be a regular language over the alphabet {0, 1}. Use the Pumping Lemma to show that n≥1 such that for all we L where wn, there is another string such that rЄL and [r] <n.
Expert Answer:
Answer rating: 100% (QA)
SOLUTION A To prove that the language L1 1i 2j 32i 2j 1i is not regular using the Pumping Lemma well assume that L1 is regular and then derive a contradiction Here are the steps of the proof Assume th... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
RMC Inc. is a small firm that produces a variety of chemical products and is interested in maximizing its total profit contribution, using the following linear model. where Max 40x30x s.t. 5x + 2x20...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
The property is located at the intersection of two heavily traveled major arteries. It is a new, glass-walled, five-story office building containing 50,000 total square feet-40,000 of which is...
-
A plane wall of thickness 0.1 m and thermal conductivity 25 W/m K having uniform volumetric heat generation of 0.3 MW/m3 is insulated on one side, while the other side is exposed to a fluid at 92C....
-
Determine the total cost for this plan given the following forecast: Use steady regular output of 400 units per month, use overtime as needed for up to 40 units per month, and use subcontracting to...
-
Pick an industry and a product or service. Engage in a creative-thinking process, as outlined in Chapter 11, to generate an improved offering. Do the same to create an entirely new offering that uses...
-
Sandi Scott obtained a patent on a small electronic device and organized Scott Products, Inc., to produce and sell the device. During the first month of operations, the device was very well received...
-
(a) 1. Assume a Heckscher-Ohlin world. The two countries are China and the U.S. The two goods are wheat and cloth and the two factors are labor and capital. Suppose each ton of wheat requires 4 units...
-
Information on Kwon Manufacturings activities for its first month of operations follows: Purchased $100,400 of raw materials on credit. Materials requisitions show the following materials used for...
-
A pilot leaves an airfield heading due east and flies 130 miles. she then turns to face a different direction, at bearing N A W (for some angle A between 0 and 90 degrees). in this new direction, she...
-
Compare and contrast the functions of management accounting and financial accounting in the context of organisational decision - making and financial reporting and discuss how the two affect the...
-
Ed is considering incorporating his T shirt shop. He is concerned with the potential liability for the shop's obligations in case he encounters financial difficulties in the future. Ed realizes that...
-
8. How much force would be required to slide a 525-pound block of steel across a level steel sheet? A. 53 pounds B. 10 pounds C. 578 pounds $25 pounds? 525
-
a) Company ABC's annual sales were $100,000, its variable costs $40,000 and its fixed costs $50,000. Calculate the profit for the year using the marginal cost equation. (5 marks) b) You as the...
-
Multiple Choice Questions: 1. The largest component of aggregate demand is? a. Government purchases. b. Net exports. c. Consumption. d. Investment. 2. A reduction in personal income taxes, other...
-
Deborah purchases a new $30,000 car in 2012 to use exclusively in her business. If Deborah does not elect to expense or take bonus depreciation in 2012 and holds the car until it is fully...
-
William sold Section 1245 property for $25,000 in 2012. The property cost $35,000 when it was purchased 5 years ago. The depreciation claimed on the property was $16,000. a. Calculate the adjusted...
-
Mark owns his home and has a $250,000 mortgage related to his purchase of the residence. When his daughter went to college in the fall of 2012, he borrowed $20,000 through a home equity loan on his...
-
The global market presents firms with more complex ethical issues than they would experience if operations were limited to one country and one culture. Moral standards vary across cultures. In some...
-
Bhopal is a city in central India with a population, in 1984 , of 800,000 . Because it was, at that time, home to the largest mosque in India, Bhopal was a major railway junction. Its main industries...
-
PricewaterhouseCoopers (or PwC, as it is known), one of the United States' "Big 4" accounting firms, has had a tax practice in Russia since the time that country changed from Communist rule. One of...
Study smarter with the SolutionInn App