Test by Bikram | Theory of Computation | Test 2 | Question: 25

Question

Which of the following are regular?

1. $\{aba^R \mid a,b \in \{0,1\}^+ \}$  
2. $\{aba  \mid a,b \in \{0,1\}^* \}$
3. $\{aba^R \mid b,a  \in \{0,1\}^* \text{ and } \mid b \mid = 10 \}$

• A.   (i) and (iii) only
• B.   (i) and (ii) only
• C.   (i) only
• D.   (ii) and (iii) only

Answer 1

aba^R  ,  a ∈ (0,1) *
We have to remember only one thing the strings generated should start and end with a same symbol.

The whole part of a and a^R except the start and end symbol comes in b

(ii) In these expression the FA has to remember where a ends b starts and again where b ends and b starts so it not possible.

(iii) When b is fixed then aba^R is not regular , where a ∈ (0,1) * . Because the whole string does not comes in b of a and a^R.

Comments

B should be correct one here

---

I Think option C should be answer as only (i) is Regular.....and Others Are Not Regular

---

@Sahin

Why not $(ii)\ ?$ Read the first comment.