Question

We are given two languages P and Q over the alphabet {0, 1} such that P = {1,01} and Q = P $\cup \left\{Q^0\right\}$. Now consider the following strings.

I. $(01{)}^{63}$
II. $(01{)}^{64}$
III. $(10{)}^{63}$ 1
IV. $(01{)}^{65}$

Let X denote the number of strings from above, belonging to $P^{64}$. Similarly let Y denote the number of strings present in $Q^{64}$. Then the value of 10X + 4Y will be equal to ________.

• A. 32

Answer 1

The correct option is A 32
Given, $P=[0,01],Q=P\cup Q^0$
Since $Q^0=q,Q=[1,01,\in ]$

Now let's first find the value of X.
The strings I and IV don't belong to $P^{64}$.
Its quite easy to see that the seoond string i.e. $(01{)}^{64}$ belongs to $P^{64}$.
Lets see why $(01{)}^{63}$ 1 belongs to $P^{64}$ as well:
$(10{)}^{64}$ 1 is same as $1(01{)}^{64}$ [using $(pq{)}^{n}p=p(qp{)}^n$ ]

So clearly we can see that the $3^{rd}$ string - $1(01{)}^{64}$ belongs to P as we can break down the string into 64 pieces (each of these pieces must belong to the language); the first piece being '1' and the remaining 63 piece's being 01.

Since $1(01{)}^{63}$ belongs to $(P{)}^{64}\Rightarrow$ $(10{)}^{63}$ 1 also belongs to $P^{64}$.
Therefore X = 2
Now let's find Y

Since Q is a superset of P, II and III will automatically become a member of $Q^{64}$ . Because of the presence of epsilon in Q the string 1 i.e.$(01{)}^{64}$ $(01{)}^{63}$ will also belong to $Q^{64}$ as the presence of epsilon allows a breakdown of pieces less than 64 as well. So we can make the first 63 pieces equal to 01, and the last piece as $\in$. But even here IV cannot be generated, as null string allows its to cut down on the number of pieces used, but can't increase them.

So y = 3
Therefore 10X + 4Y =10(2) + 2(3) = 32