Regular Languages

Question

Why is WXW^R a regular language but XWW^R is not? (X,W ϵ (0,1)⁺)

Comments

in case of WXW^R  it can be considered as a language of string 1(0+1)⁺1   & 0(0+1)⁺0

hence a dfa can be drawn

but in case XWW^R      you have to match W ith W^R   for which you need match  and you can't draw a finite automata

Answer 1

https://gatecse.in/identify-the-class-of-a-given-language/

Comments

In WXW^R if we assume that the string start with let's say "a" then it will end also with "a" , similar is the case with start with b too.

Now if you see in the question it is given that X can generate everything expect epsilon  so whatever will be there after first "a" and before last "a" that will be taken care by X. For eg: if your W is aab and X is abab then complete string will be aabababbaa here we can see that start with "a" and also end with "a". Whatever is in between we can generate it by X. So this language is starting and ending with same symbol.

Now you can try similar type of reasoning to check whether it is regular or not.

Answer 2

look here X can be interpreted as any combination of 0's and 1's. so whatever input given to the fm it will interpret it as a language in which string starts and end with same character

for instance if we have 1(01010)1

Here first 1 and last 1 is W

and middle 01010 treated as X

and it is possible to make a Finite Automata for the language which starts and ends with same character

whereas in second language we cannot do the same in any possible way