551 views

1 Answer

Best answer
4 votes
4 votes

As w, x $\in$ { 0 + 1 }*.
By taking any string $\in$ $\sum$* says S examples.
S = 10001010101

We can say that here w = $\in$, so $w^{r}$ is also $\in$. And x = 10001010101.

So any string $\in$ $\sum$* can be accepted like above argument.
Therefore language generated will be $\sum$*, which is a regular language.

Interesting question would be 
L = {w$w^{r}$x  ∣ x,w $\in$ {0,1}^+}

Note here x, w $\in$ {0 + 1}^+.


Here we can't say w = empty string. It should have at least length greater than or equal to 1.

we know that w$w^{r}$ can be accepted by an NPDA (It is a very popular example). NPDA because we can't determine the middle of the string.
Now it is easy to see that w$w^{r}$x can also be accepted by NPDA by some modification. When we are done with w$w^{r}$ part and our stack consisting z(Stack symbol) then if we see either 0 or 1 we can move to the final state.

For More such examples.
http://gatecse.in/identify-the-class-of-a-given-language/

selected by

Related questions

0 votes
0 votes
0 answers
1
Sahil1994 asked Nov 29, 2017
249 views
Hi mates,Difference between 1) xcy {x, y € (0,1)*}2) xcx {x €(0,1)*} and c is a terminal symbol and c is not 0,1
1 votes
1 votes
1 answer
3
practicalmetal asked Mar 20, 2023
372 views
The complement of the languages:i) {ww | w in (0+1)*}ii) {$a^n b^nc^n$ | n>1} area) Context Free b) Not Context Free c)are DCFL’s d)None
0 votes
0 votes
1 answer
4