Solution to Define a relation on the set S of all strings of letters: two strings are … - Sikademy
Author Image

Archangel Macsika

Define a relation on the set S of all strings of letters: two strings are related if you can get one from the other by reversing one pair of adjacent letters. For example, cow ocw but cow woc.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

A relation \rightleftharpoons is defined on the set of all strings of letters: two strings are related if we can get one string from the other by reversing one pair of adjacent letters.

Consider the letters c, a, and t. The set S of all strings of these three letters is given below.

A relation on a set S is a subset of S \times S . If R is a relation on S, we say that “a is related to b” if (a,b) \in R , and is written as a R b. The pair of strings from set S that represent the \rightleftharpoons relation are (cat, cta), (cat, act), (atc, act), (atc, tac), (tca, tac), and (tca, cta). So, the relation on S is the set {(cat, cta), (cat, act), (atc, act), (atc, tac), (tca, tac), (tca, cta)}.

Note that a relation R is symmetric if it has the property that x R y if and only if y R x. The relation R on S is symmetric because for any x,y \in S , x R y \Leftrightarrow y R x. For example, cat R cta \Leftrightarrow cta R cat.

Since the relation R is symmetric on X, the associated graph is undirected. Draw the graph using the vertex-set as {cat, atc, tca, cta, tac, act} and the edge-set as as shown below.


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3250-qpid-1949