789 views
6 votes
6 votes
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\} \}$

1 Answer

Best answer
3 votes
3 votes
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.
selected by

Related questions

4 votes
4 votes
3 answers
2
2 votes
2 votes
2 answers
3
Na462 asked Sep 13, 2018
670 views
Is the given Grammer represent a regular language ?S->AaBA->aC | epsilonB->aB | bB | epsilonC->aCb | epsilon
1 votes
1 votes
1 answer
4
Na462 asked Sep 11, 2018
1,550 views
Is Language L = {0(n+m) 1(k+l) | m = l, and m,n,k,l ≥ 1 } a regular language ? explain