Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I've learned that finite automata doesn't have memory and hence languages, where there are comparison within the string, can't be considered regular.
In our university there was a question where the following language was considered as regular in the solutions: $\{WXW^R | W,X ∈ \{0,1\}^*\}$
here, $W^R$ is the reverse of $W$.
To compare $W^R$ and $W$ wouldn't we have to store $W$ in memory which I know doesn't exist in finite automata machines. Or what actually happens?
A finite automaton has no memory other than which state is the current state.
The strings in the language consist of some substring, then another substring, then the reverse of the first substring. One way to recognize this language would be to check whether the end of the string matches the start of the string, which requires storing it.
However, the way the language is described is meant to trick you. The first substring may be empty (0 chars long). Every string starts with an empty string and ends with the reverse of it! So every string is in the language. Can you make a DFA that recognizes every string? Of course you can.
Even if we said that W must contain at least 1 character, the language would contain every string that starts and ends with the same character, which is also recognizable by a DFA. If W must contain at least 2 characters, it's still recognizable by a more complicated DFA as the DFA can branch off for each combination of characters, and then each branch can check for those characters at the end. Only if there's some rule that allows W to be infinitely complex (e.g. any number of $a$ followed by a $b$) can it not be recognized by a DFA.
The "and hence..." is incorrect. There might be other ways to determine whether a string is in the language, that doesn't require comparison.
For the particular language you cite, try to come up with an example of a string that is not in that language. That might make it clearer why it is regular, and why the "and hence" is faulty.
