# does finite automata have memory?

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?

• It's up to you to find $W$ and $X$. Sep 15, 2022 at 8:11
• An automaton of $s$ states has $\log_2(s)$ bits of memory.
– user16034
Sep 15, 2022 at 18:33
• A memoryless device is a function. The same input constantly returns the same output. Do you think that this holds for automata ?
– user16034
Jan 24 at 8:54

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.

• So, we have the freedom of deciding what W can be, and in this case we take the case where W is null or empty, right?
– h4kr
Sep 28, 2022 at 17:59
• @Gourab In this specific case you can choose it to be empty. In general, no. Consider the language $\{aWbXcW^Rd | W,X ∈ \{0,1\}^*\}$. You have no choice for $W$ - it's whatever is between $a$ and $b$ and a DFA can't recognize that. A DFA can recognize $\{aWbXc | W,X ∈ \{0,1\}^*\}$ because it doesn't have to remember what $W$ is. Sep 28, 2022 at 18:28

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.

• Other ways to determine a regular language is if we can draw a DFA for that particular language, as far I know. And an example for a string which is isn't DFA, I can come up with $\{a^nb^n | n>0\}$
– h4kr
Sep 15, 2022 at 6:34
• @Gourab For the first part – true, but of course one must be aware that one being unable to come up with a DFA for a language doesn't mean one doesn't exist. For the second part, you are correct that no DFA recognizes $\{a^n b^n | n > 0\}$ (though note, it's a language not a string), but D.W. challenged you to think of a string not belonging to the language $WXW^R$ presented in your question. thinking about that might help you realize why the language is regular even if it seems at a glance to require an arbitrary amount of memory for its decider. Sep 15, 2022 at 13:07