Quote:
Originally Posted by chaley
<professorial_mode>
The general case cannot be solved with regular expressions because REs don't have the notion of 'stack'. Said another way, and getting a bit formal, all REs by definition can be translated into a deterministic finite state machine. The important part here is that the number of states is known from the RE, and is fixed for all utterances (text to be matched). Parsing utterances in a palindromic language requires a state for each letter up to the center point so the machine can match the right letter after the center point. Such a machine requires len(utterance)/2 states. Thus the number of states is unbounded, meaning that the grammar for the language cannot be described using an RE.
|
So, if I understand you correctly, the regular expression would be something like the starting state, each matching string would be it's own (end?) state, and the matching operation would provide transitions between the end states, yes? And because the number of states a regular expression can describe is finite, and, in the general case, len(utterance) is unknown, presumed to be in the range [0,\infty], a palindrome could not be described using a regular expression? If that's correct, I don't think I understand how the * and + quantifiers work, because they, as far as I understand, describe an utterance with len(utterance) \in [0,\infty] and len(utterance) \in [1,\infty], respectively.
(Sorry, I lapsed into some LaTeX there, but, seeing your background, I assume you understand.)