Question

Find all pairs of sets of strings A and B for which AB= {10, 111, 1010, 1000, 10111, 101000}.

Short answer

All possible pairs are given below:

First case:

\(\begin{array}{c}{\bf{A = \{ \lambda \} }}\\{\bf{B = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{A = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{B = \{ \lambda \} }}\end{array}\)

Second case:

\(\begin{array}{c}{\bf{A = \{ \lambda ,10\} }}\\{\bf{B = \{ 10,111,1000\} }}\end{array}\)

Third case:

\(\begin{array}{c}{\bf{A = \{ 1,101\} }}\\{\bf{B = \{ 0,11,000\} }}\end{array}\)

Step-by-step solution

 Step 1: Find the strings

Here AB= {10, 111, 1010, 1000, 10111, 101000}.

Here AB represents the concatenation of A and B.

\({\bf{AB = \{ xy|x}} \in {\bf{A}}\,{\bf{and}}\,{\bf{y}} \in {\bf{B\} }}\)

First case- one of the sets could contain only the empty string\({\bf{\lambda }}\), then the other set will contain all strings in AB itself.

\(\begin{array}{c}{\bf{A = \{ \lambda \} }}\\{\bf{B = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{A = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{B = \{ \lambda \} }}\end{array}\)

Solve for second case.

Second case- one of the sets contains the empty sets and at least one other string. Then there is only one possible case. Then

\(\begin{array}{c}{\bf{A = \{ \lambda ,10\} }}\\{\bf{B = \{ 10,111,1000\} }}\end{array}\)

X	Y	XY
\({\bf{\lambda }}\)	10	10
10	10	1010
\({\bf{\lambda }}\)	111	111
10	111	10111
\({\bf{\lambda }}\)	1000	1000
10	1000	101000

Third case.

Third case-there is also one possible pair of sets A and B where never contain empty string\({\bf{\lambda }}\).

\(\begin{array}{c}{\bf{A = \{ 1,101\} }}\\{\bf{B = \{ 0,11,000\} }}\end{array}\)

X	Y	XY
1	0	10
101	0	1010
1	11	111
101	11	10111
1	000	1000
101	000	101000

Therefore pairs are:

\(\begin{array}{c}{\bf{A = \{ \lambda \} }}\\{\bf{B = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{A = \{ 10,111,1010,1000,10111,101000\} }}\\{\bf{B = \{ \lambda \} }}\end{array}\)

\(\begin{array}{l}{\bf{A = \{ \lambda ,10\} }}\\{\bf{B = \{ 10,111,1000\} }}\end{array}\)

\(\begin{array}{l}{\bf{A = \{ 1,101\} }}\\{\bf{B = \{ 0,11,000\} }}\end{array}\)