TOC :Regular Languages

Question

Which of the following is not a regular language?

a) $\{ w ( w_r )^* \mid w \in \{0,1\}^* \}$

b) $\{w^n w^m  \mid 0\leq n\leq m, w \in \{0,1\} \}$

Comments

i think so anil.

---

Arjun Sir please explain this question..how to think it.

---

In wⁿ w^m  as n can be zero thus, we can treat whole string as a second part i.e. w^m and thus which implies that m will either be zero in case of null string or m>=n as we are considering n=0. Thus it can accept any String which is (0*+1*). Hence it is Regular.

Answer 1

This question is just application of logic and set theory and there are no short cuts or even systematic methods. Only thing one can do is to repeatedly look at the question and deduce the meaning.

a) $L  =\{ w ( w_r )^* \mid w \in \{0,1\}^* \}$

$w$ is any string over $\{0,1\}$ and it must be followed by its reverse repeated 0 or more times. Here, "0" is important as it is enough to ensure all strings are in $L$ $((0+1)^*)$. Hence, $L$ is regular.

b) $\{w^n w^m  \mid 0\leq n\leq m, w \in \{0,1\} \}$

Here, $w$ is either 0 or 1 (not a string but a character. Hence $L$ is nothing but $0^* + 1^*$ which is again regular.

Comments

In the second one, even if $w \in \{ 0, 1\} ^*$, it should be regular.

Because we can consider n = 0, and m = 1, and whole string comes under w. i.e $(0 + 1)^*$

Am I correct??

---

correct..

---

@Rishbah yes.