# Theory Of Computation Test – Question 6

edited

Which of the following is Class of Language is Regular:

A) { wxwR | w,x ∈ {0,1}+ }
B) { wxwR∣w,x∈{0,1}+ and |x|=100 where |x| denotes length of string x }
C) { wxwR∣w,x∈{0,1}* and |x|>=100 where |x| denotes length of string x }
D) { wxwR∣w,x∈{0,1}* and |x|<=100 where |x| denotes length of string x }

• 1. Only A
• 2. A and C Only
• 3. A, B, C Only
• 4. All are regular

+1 vote
Option:1

As the required language is regular, only option-A is valid. All others have a count of x i.e., the length of x which we cannot count for a regular language using FA.

Correct me if I am wrong.!

Thank you.
1st one is regular only because every thing u will write in place of w then obviously then obviously that will be present in w^r also but in middle x is here which can span or cover whole the things which u have written in place of w and w^r except the minimum thing that  the given condition that w and x should atleast one 0 or 1

So it's regular expression is

0(0+1)^+0 + 1(0+1)^+1

So this thing will not happen in option - 2 because the length of x is given finite there so x can take only 100 length combination of a and b other than lets say we have total more than 102 then definitely we will span the covering of x upto 100 length but after that u have to forcibly keep the other symbols into w and w^r also obviously so from here you can't write regular expression for this

Now for the third option we come that x will take more than 100 length definitely means our language should not contain less than 100 length string and another condition is w and x can take minimum (€) AND at most any combination of 0 and 1

So for this we can write the regular expression as (0+1)(0+1)(0+1)(0+1)........ Upto 100 times then concatenated with (0+1)^*

Because every thing that u write in place of w we can bring that into x and place the (€) in place of w and w^r

Same reason for the 4th option here length of x should be less than 100 now here lets say we take more than 100 let's say 102 or 104 length string then we can only expand the covering of x upto 100 length after that the remaining length we have to compare with w and w ^r so here also we can't find any regular expression

So according to me A and C will be correctaas 2nd option

Correct me if I'm wrong