2. Let L be the set of all finite strings over A = {a,b} and let...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. Let L be the set of all finite strings over A = {a,b} and let R be the following binary relation on L (num(a, x) denotes the number of occurrences of a in the string x): xRy num(a, x) = num(a, y) ^ num(b, x) = num(b, y). Observe that R is an equivalence relation on L. (a) What is the number of strings in the equivalence class which contains ababa? Explain why. (b) What is the number of equivalence classes of R which contain strings of length k? Explain why. (c) Are there any equivalence classes which contain just one string? If the answer is YES, give the number of such classes and provide some examples; if it is NO, explain why all equivalence classes contain more than one string. 2. Let L be the set of all finite strings over A = {a,b} and let R be the following binary relation on L (num(a, x) denotes the number of occurrences of a in the string x): xRy num(a, x) = num(a, y) ^ num(b, x) = num(b, y). Observe that R is an equivalence relation on L. (a) What is the number of strings in the equivalence class which contains ababa? Explain why. (b) What is the number of equivalence classes of R which contain strings of length k? Explain why. (c) Are there any equivalence classes which contain just one string? If the answer is YES, give the number of such classes and provide some examples; if it is NO, explain why all equivalence classes contain more than one string.
Expert Answer:
Answer rating: 100% (QA)
1 Sure I can help you with this problem a What is the number of strings in the equivalence class which contains ababa Explain why The number of string... View the full answer
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date:
Students also viewed these programming questions
-
re Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
The adjusted trial balance of Silver Sign Company follows: Requirements 1. Assume Silver Sign Company has a January 31 year end. Journalize Silvers closing entries at January 31. 2. How much net...
-
Juanita maintains the only greenhouse in isolated Point Barrow, Alaska, and therefore has a monopoly on the sale of fresh flowers. Her hired-gun statistician estimates that the elasticity of demand...
-
A hydraulic lift is to be used to lift a 2500 kg weight by putting a weight of 25 kg on a piston with a diameter of 10 cm. Determine the diameter of the piston on which the weight is to be placed....
-
The rod has a circular cross section with a moment of inertia \(I\). If a vertical force \(\mathbf{P}\) is applied at \(A\), determine the vertical displacement at this point. Only consider the...
-
Rockwell Wholesalers, Inc. has just completed its fourth year of business in 20X1. A set of financial statements was prepared by the principal stockholders eldest child, a college student who is...
-
Research your destination about New York City, USA and using secondary data and facts from a variety of sources, and will present this information using the following structure: Title Page Executive...
-
The Architect total contract fee for the project is: $235,000. The Basic Services will be performed in four phases as described below. The services shall be rendered in the following phases:...
-
(i) Make a neat sketch of a general cargo ship and label fifteen (15) parts? (ii) . What type of ship is used for the transport of both containers and Ro-Ro ONLY? (iii) What does the following...
-
Vibration in a car can create concentric ripples on the surface of a cup of coffee sitting on the dashboard. What kind of waves are the ripples, and why are they circular?
-
Three equally spaced, coherent sources of water waves of frequency \(f\) are in a line with a distance \(d\) separating each adjacent pair. All three sources have the same amplitude. Nodal lines...
-
A rod of mass \(m\) and length \(\ell\) is rigidly connected at a right angle to the midpoint of one face of a uniform cube of mass \(m\) and side length \(\ell\) (Figure P15.56). The other end of...
-
A block of inertia \(m\) is attached to a light string wound around a uniform disk also of inertia \(m\) (Figure P11.74). The disk has radius \(R\) and rotates on a fixed horizontal axle through its...
-
A uniform disk of mass \(m\) and radius \(R\) lies in a vertical plane and is pivoted about a point a distance \(\ell_{\mathrm{cm}}\) from its center of mass (Figure P15.58). When given a small...
-
A spherical hollow, thin conducting shell of radius 2m and Has zero potential , if q=12-6 C Is distanced from t by 6 m from the center, therefore find the electrostatic potential at any point (x,y,z)...
-
Data on weekday exercise time for 20 females, consistent with summary quantities given in the paper An Ecological Momentary Assessment of the Physical Activity and Sedentary Behaviour Patterns of...
-
Let A = {0, 2, 4, 6, 8, 10}, B = {0, 1, 2, 3, 4, 5, 6}, and C = {4, 5, 6, 7, 8, 9, 10}. Find a) A B C. b) A B C. c) (A B) C. d) (A B) C.
-
Draw the directed graph of the reflexive closure of the relations with the directed graph shown. 1. 2. b d
-
How many of the 16 different relations on {0, 1} contain the pair (0, 1)?
-
The following are types of active surveillance except a. National household surveys gathering information on the social status and health status of people in a particular country b. Notifcation of...
-
What can be used for a velocity output without the negative aspects of a seismic transducer?
-
More and more Japanese companies are moving in on what once was an exclusive U.S. preserve: making and selling the complex equipment that makes semiconductors. World sales are between \($3\) billion...
Study smarter with the SolutionInn App