0

Let A be the set of strings of $0$’s and $1$’s of length $3$ or less. Define the relation of $d$ on $A$ by $xdy$ if $x$ is contained within $y$. For example, $01d101$.

a) Draw a digraph for this relation.

b) Do the same for the relation $p$ defined by $xpy$ if $x$ is a prefix of $y$. For example, $10p101$, but $01p101$ is false.

I don't understand what they are asking here, all I'm asking is to help simplify the question. I hope I haven't been to vague.

mrp
  • 5,086
Daniel Hauptfleisch
  • 11

1 Answers1

0

$A$ is a finite set. At first, you should find out all elements of A. Then find out all pairs $(a,a') \in A \times A$ that satisfy $ada'$.

Now you have to know what a digraph (= directed graph) is. If not, find out on wikipedia. All you have to do then is to write down the elements of $A$ and place the right arrows between the elements.

S. M. Roch
  • 941
  • thank you but why is there a p in the '01p101', that I don't get. And since they said A is made of 0's an 1's less than 3 in length can i say A is 01, then that would be (0,1) and (1,0)? I know what digraphs are just this format of the question being asked is confusing – Daniel Hauptfleisch Aug 18 '16 at 13:06
  • You probably don't understand the set $A$. It contains these elements: $A = {,0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111 }$. Note that the empty string, the string of size $0$, is also an element of $A$. Now, using the relations, you get for example $10d010, 1d11, 00d000, 1d1, 10p100, 11p110$ as true statements. The elements of $A$ are your nodes in the digraph. The edges are given by the relations. If this is helpful, please don't forget to flag it as the answer. – S. M. Roch Aug 18 '16 at 13:43
  • I still dont undertstand why 'd' is between the 1's and 0's – Daniel Hauptfleisch Aug 19 '16 at 07:04
  • This is just an issue of notation. Let $x,y \in A$, now when I write $xdy$ it means that the element $x$ is in $d$-relation with the element $y$. For example $10d010$ means that the element $x=10$ is in $d$-relation with the element $y=010$, since the string "010" contains the string "10" (Because the last two characters of "010" are "10"). Clear now? – S. M. Roch Aug 19 '16 at 17:18
  • yes thank you @S.M. Roch – Daniel Hauptfleisch Aug 21 '16 at 09:08