Palindromes are Regular Language

Explain L={wxwr|w,xϵΣ+} is regular language.

k.nikhil kumar @nikhilkolla 22 Jan 2017 06:40 pm

As the language the starts and end with same symbol

example :w=abaXaba .

x can be anything.

so it is regular language

Shraddha @shraddhagami 22 Jan 2017 07:07 pm

We can't remember the previous string in FA. then how it's possible?

Ashish Kumar Goyal @dashish 22 Jan 2017 08:03 pm


what is ∑ set here??

Shraddha @shraddhagami 22 Jan 2017 08:18 pm

Sry I didn't mention {a,b}

Ashish Kumar Goyal @dashish 22 Jan 2017 08:21 pm


no matter ∑ is always finite. now as per the definition of the language, it would accept all strings having it's sufix as reverse of some prefix of any length.

now consider string abbabbabaa.. now seeing this on first sight we feel it is not in language... but have a look at the prefix and corresponding suffix a. Reverse of a is a, so the language accepts it.

So, our problem may be broken as a language having strings that starts and ends with same symbol. this language would contains all strings in given language and reject every string that is not in given language.

And as this language is regular, hence given language is regular...:) 

Shraddha @shraddhagami 22 Jan 2017 08:28 pm

Thanks dude...:)

Shobhit @sudsho 23 Jan 2017 03:14 am

expand x and cover everything leaving first and last symbol
a(a+b)*a +b(a+b)*b is the regular expression..

Antonio Anastasio Bruto da Costa @antonio 23 Jan 2017 08:35 pm

Dear @shraddhagami, understand that the key trick here is that the language is \(w~x~w^r\) and \(wx\) cannot be the empty string. Every non-empty string starts and ends with the empty string. Do you agree with this? If you do, then you will see, that for the empty string \((w = \epsilon)\) is equivalent to  \((w^r = \epsilon)\). Therefore, any string between the epsilon can be matched to the pattern \(x\) and therefore, the language if studied is actually going to be the language  \(L = \Sigma^+\)

Shraddha @shraddhagami 23 Jan 2017 09:56 pm

Thank you

Got it :)

Ashish Kumar Goyal @dashish 23 Jan 2017 10:14 pm

@antonio You got to read the question again... w∈ ∑so it can't be ∈. Pls read the replies above u will understand what u missed.. But still your analysis is partially correct. U approached the correct way.

Antonio Anastasio Bruto da Costa @antonio 23 Jan 2017 11:44 pm

@dashish @shraddhagami : Oh yeah, so basically that still works. Even if \(w \in \Sigma^+\), you would simply need to ensure that the beginning and ending letter is the same, which an FA (Finite Automaton) can remember to do.