Prove that the following languages are not regular. You may use the pumping lemma and the closure
Question:
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, and complement.
a. {0n1m0n| m, n ≥ 0}
Ab. {0m1n| m ≠ n}
c. {w| w ∈ {0,1}* is not a palindrome}8
*d. {wtw| w, t ∈ {0,1}+}
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 66% (12 reviews)
a To prove that the language 0n1m0n m n 0 is not regular we can use the pumping lemma for regular languages Assume for the sake of contradiction that ...View the full answer
Answered By
Mubarak Ali
I am serving as a Computer Science lecturer at different Colleges for more then 5 years. I delivered lectures to different Class Like:-
1:- Intermediate
2:-BS-Program(Subject)
3:-B.Sc
4:-Master Classes.
My teaching method is to simple that's way students get information in the easy way
0.00
0 Reviews
10+ Question Solved
Related Book For
Question Posted:
Students also viewed these Computer science questions
-
Use the pumping lemma to show that the following languages are not context free. a. {0 n 1 n 0 n 1 n | n 0} Ab. {0 n #02 n #03 n | n 0} Ac. {w#t| w is a substring of t, where w, t {a, b} * } d. {t...
-
Use the pumping lemma to show that the following languages are not regular. A a. A 1 = {0 n 1 n 2 n | n 0} b. A 2 = {www| w {a, b} * } A c. A 3 = {a 2n | n 0} (Here, a 2n means a string of 2 n as.)
-
Consider the language B = L(G), where G is the grammar given in Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34, states the existence of a pumping length p for B. What is...
-
Raner, Harris & Chan is a consulting firm that specializes in information systems for medical and dental clinics. The firm has two offices-one in Chicago and one in Minneapolis. The firm classifies...
-
The figure shows a scatter plot and a linear regression model for the annual revenue data in Table 13. (A) Interpret the slope of the model. (B) Use the model to predict the annual revenue (to the...
-
Suppose interest rates on Treasury bonds rose from 5% to 9% as a result of higher interest rates in Europe. What effect would this have on the price of an average companys common stock? AppendixLO1
-
1 Why was the sales manager wrong to cancel the rest of his tour? What other kind of actions could he have taken to reduce the problem?
-
How is EDI more than technology? What unique control problems may it pose?
-
Che Homework Carly each of the costs as either a product or period cost. Then, classify each of the product costs as either direct materials, direct obot or factory overhead and each of the period...
-
Identify the background facts in the following cases: Flowers v. Campbell (presented in this chapter) Lucero v. Sutten (presented at end of Chapter 10)
-
Let A/B = {w| wx A for some x B}. Show that if A is regular and B is any language, then A/B is regular.
-
Let = {1, #} and let Y = {w| w = x 1 #x 2 # #xk for k 0, each x i 1 * , and x i xj for i j}. Prove that Y is not regular.
-
For the situation in Exercise 14, suppose the cost of catching a fish is the same for each fish in the first and second samples, and you have enough resources to catch a total of n1 + n2 = C fish...
-
Nequired information Exercise 5-17 (Static) Notes receivable-interest accrual and collection LO 5-6 (The following information applies to the questions displayed below) Agrico Incorporated accepted...
-
Case 14-3 Sarin Pharmaceuticals Ltd. Alan Mannik, director of procurement for the Sarin Phar- maceuticals Ltd. (Sarin) Animal Health Division plant in Vancouver, British Columbia, was planning for...
-
CL727 LEGAL ANALYSIS AND WRITING Module 11 Assignment: Brief Answer, Analysis, and Conclusion This assignment will be due in Module 11. Your assignment is to write the Brief Answer, Analysis, and...
-
Question 11 (0.5 points) l) Listen } As a drug manufacturer, you expect your latest wonder drug to lower cholesterol. It has been successful with a limited group of participants so far, so you have...
-
Redfern Audio produces audio equipment including headphones. At the Campus Facility, it produces two wireless models, Standard and Enhanced, which differ both in the materials and components used and...
-
What is the output of code corresponding to the following pseudocode if the users name is Sammy? Declare Dash As Character Declare Count As Integer Declare Number As Integer Declare Name As String...
-
If the joint cost function for two products is C(x, y) = xy2 + 1 dollars (a) Find the marginal cost (function) with respect to x. (b) Find the marginal cost with respect to y.
-
Consider the following code fragment, taken from some package:
-
Consider the inheritance of classes from Exercise R-2.12, and let d be an object variable of type Horse. If d refers to an actual object of type Equestrian, can it be cast to the class Racer? Why or...
-
Give an example of a Java code fragment that performs an array reference that is possibly out of bounds, and if it is out of bounds, the program catches that exception and prints the following error...
-
Los datos de la columna C tienen caracteres no imprimibles antes y despus de los datos contenidos en cada celda. En la celda G2, ingrese una frmula para eliminar cualquier carcter no imprimible de la...
-
Explain impacts of changing FIFO method to weighted average method in inventory cost valuations? Explain impacts of changing Weighted average method to FIFO method in inventory cost valuations?...
-
A perpetuity makes payments starting five years from today. The first payment is 1000 and each payment thereafter increases by k (in %) (which is less than the effective annual interest rate) per...
Study smarter with the SolutionInn App