View Single Post
Old 09-23-2010, 09:24 AM   #24
Manichean
Wizard
Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.Manichean is the 'tall, dark, handsome stranger' all the fortune-tellers are referring to.
 
Manichean's Avatar
 
Posts: 3,130
Karma: 91256
Join Date: Feb 2008
Location: Germany
Device: Cybook Gen3
Quote:
Originally Posted by chaley View Post
<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.)
Manichean is offline