in Theory of Computation edited by
206 views
0 votes
0 votes
Which of the following is/are Regular?

A] $\left \{ XWYW^{R} \space\ | \space\ W,X,Y \in \left \{ a,b \right \}^{+} \right \}$

B] $\left \{ WXW^{R}Y \space\ | \space\ W,X,Y \in \left \{ a,b \right \}^{+} \right \}$

C] $\left \{ WXYW^{R} \space\ | \space\ W,X,Y \in \left \{ a,b \right \}^{+} \right \}$

D] None

 R => Reverse

Please describe your answer.
in Theory of Computation edited by
206 views

11 Comments

0
0
Hi,
Just now I have seen the page you have given and found that the formats I have asked are not present there.
In fact I want to confirm my answer as answer given with this question is not matching with mine.

According to me, all are regular but answer is option C.

Could you please explain how?
0
0
can you explain your logic why option a,b are regular ?
0
0

@anupamsworld

Looking for the formula is not going to help for GATE. Instead if you focus on the explanations given you should be able to answer new questions yourself. If you study 100 questions, 101th one will be coming for GATE.

0
0

A) take minimum string and try it's regular language 

$\left ( a+b \right )^{^{+^{}}}a\left ( a+b \right )^{+}a+\left ( a+b^{^{}} \right )^{^{+}}b\left ( a+b \right )^{^{+}}b$

1
1

@Kabir5454     @Arjun

According to me,

A] $(a+b)^{+}.(a(a+b)^{+}a+b(a+b)^{+}b)$

B] $(a(a+b)^{+}a+b(a+b)^{+}b).(a+b)^{+}$

C] $a(a+b)^{+}a+b(a+b)^{+}b$

Please correct where I am going wrong.

1
1

@anupamsworld LGTM. What’s the issue?

0
0

@Arjun sir what is LGTM ?

0
0

@Kabir5454 Google should help :)

1
1

@Kabir5454

Could you please confirm any answer?
I have also replied the supporting expressions for my answer(all are regular).

0
0
Seems correct to me bro.
0
0

2 Answers

0 votes
0 votes
C is the regular

we don’t know about XY, but it belongs to Σ. So we can consider whatever as XY,

let's take a string abbababbaba. We can consider bbababbab as XYZ and string w = “a”  and w reverse also “a”

so we can take this grammar as regular a(a+b)*a or b(a+b)*b

1 comment

What about options A and B?
0
0
0 votes
0 votes
i think we can try this problem by applying pumping lemma . So that we can check the above options easily
by

1 comment

Pumping lemma for checking irregularity of a language. If a language satisfies pumping lemma then it may or may not be regular.

you are getting confused.
0
0

Related questions