Question: Let = {0, 1}. Prove that the following languages are not regular. (a) The set of strings that are palindromes. Note that a string

Let = {0,1}. Prove that the following languages are not regular. (a) The set of strings that are

Let = {0, 1}. Prove that the following languages are not regular. (a) The set of strings that are palindromes. Note that a string is a palindrome if it reads the same both forwards and backwards. For instance, the strings 0, 010, 1001 are palindromes, while the strings 01, 100 are not. (b) {01 | the greatest common divisor of i and j is 1 }.

Step by Step Solution

★★★★★

3.36 Rating (159 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

To prove that the given languages are not regular we will use the Pumping Lemma for Regular Languages Language a The set of binary palindromes Statement Let L w in 01 mid w wR the set of all palindromes over 01 Proof Using Pumping Lemma Assume L is regular Then by the Pumping Lemma there exists a pumping length p such that any string s in L with s geq p can be written as s xyz with the following conditions xy leq p y 0 xyiz in L for all i geq 0 Choose the string s 0p10p This is a palindrome and s 2p 1 geq p By the lemma split s xyz where xy leq p so y consists only of 0s from the first block of 0p Let x 0a y 0b with b 0 z 0pab10p Pumped string xy0z 0a000pab10p 0pb10p This is not a palindrome asymmetry around the middle 1 Conclusion Contradiction L is not regular Language ... View full answer

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 Programming Questions!

A substance X shows a weight of 100.00 g when weighed in air. If the density of air is 0.0012 g/ml; density of calibration weights 8.0 g/ml.; and density of X is 1.33 g/ml., find the true mass.

The Task In this project, you will be writing a program that receives a string of characters via the UART, checks if this string is a palindrome, and then uses a print function to print either Yes or...

Solve the equation below, algebraically where 180 0 360. 2cos20 + 5sin0+1 = 0 Make sure to show/explain all steps to reach your answer.

A six inch thick one-way RC slab (hf =6 inch) is made of fc =4000.0 psi concrete with Gr. 60 #4 bars spaced 8 inch on center for longitudinal reinforcement. The bottom side of the slab has 3/4 inch...

1. (Non-regular languages) Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, complement,...

hen we contrive an assumption that the existence of primitive recursive functions pair N 2 N, fst N N and snd N N satisfying for all x, y N fst(pair (x, y)) = x snd(pair (x, y)) = y prove by...

DFAs and NFAs, pumping lemma, and regular expressions. please help with these provlems. Let {} (recall that = ). Prove that there is a DFA M having n accepting states that accepts L. (Assume an...

1456HHSC attend all (a) In the quantum teleportation protocol, Alice and Bob are every in possession of one qubit of a couple in the joint country00i + statei. Explain how the protocol works. In...

Question 5 0 / 1 point When designing a class, what is one of the first tasks that need to be done? Question options: Defining the instance variables Writing the method headers Specifying the public...

ABC Companys CFO has provided a long-term forecast for ABC as follows: EBIT Net Income Discount Factor 2020 $42,000,000 $20,000,000 0.91 2021 $44,000,000 $21,000,000 0.83 2022 $46,000,000 $22,000,000...

Find the spectral factorization, as in Exercise 8.4.32, of the following Hermitian matrices: (a) (b) (c) 6 2 (12 17) 6 1-2i 1+2i2 I 5i -4 -4 -4i 8

to solve for the length of the right triangle sides, which equation is correct. x 5 x - 7 5 x + 1 1

In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and end with #/...

The 0 particle is a neutral nonstrange meson that can decay to a positive pion, a negative pion, and a neutral pion. Write the reaction for this decay, and verify that it conserves charge, baryon...

You are considering buying the bonds of a very risky company. A bond with a $100 face value, a 1-year maturity, and a coupon rate of 22% is selling for $95. You consider the probability that the...

A shallow foundation measuring 1 m 2 m in plan is to be constructed over a normally consolidated sand layer. Given: D f = 1 m, N 60 increases with depth, N 60 (in the depth of stress influence) =...

Refer to Exercises 28 and 30. a. Verify that the conditions for inference are met. b. Use Table C to find the P-value. Then use your calculators 2 cdf command. c. Interpret the P-value from the...

Which of the following is a true statement about the process of delegating work?It begins with the creation of an obligation.It involves randomly assigning jobs.It reduces employee empowerment.It...

Write a complete program for the problem described in Exercise 10. Exercise 10. Write statements that can be used in a Java program to read two integers and display the number of integers that lie...

Write a program that reads a string for a date in the format month / day / year and displays it in the format day . month . year, which is a typical format used in Europe. For example, if the input...

Consider the boolean expression((x > 10) || (x

Given that the market for smartphones is inefficient, explain why consumers of smartphones might not want the price to be regulated.

Suppose Warner Music and Universal Music are in a duopoly and currently limit themselves to 10 new artists per year. One artist sells 2 million songs at $1.25 per song. However, each label is capable...

Oil Giant and Local Oil are the only two producers in a market, as shown in Figure 15P-5. They have an agreement to restrict oil output in order to keep prices high. a. What is the dominant strategy...