regular expression "not match"

[Apollon Oikonomopoulos]

On 08:33 Fri 05 Sep     , Christos Ricudis wrote:
> Gia recursive domes, 8a prepei na xrhsimopoihseis ena... katse twra, 
> pws  to leme sta ellhnika ayto... a, nai. Ena katwzmprwxniko aygomato.
>
> Ayto pou de 8ymamai ap'eksw, einai poia klash glwsswn den anagnwrizetai  
> apo to katwzmprwxniko aygomato alla apo th mhxanh tou pousth.
>
To Κατωζμπρωχνικό Αυγόματο δεν αναγνωρίζει τις Αναδρομικά Απαριθμήσιμες 
(??) (= Recursively Enumerable) γλώσσες αν δεν απατώμαι, για τις οποίες 
χρειάζεται μια Τουριστική Μηχανή.

Γενικά οι regular expressions δεν έχουν «μνήμη» (πέρα από ό,τι είναι 
κωδικοποιημένο στην κατάσταση του αυγόματου), οπότε δεν μπορούν να 
χειριστούν πράγματα της μορφής «κάνε match όσες λέξεις έχουν οποιοδήποτε 
αριθμό από Α ακολουθούμενα από τον ίδιο αριθμό Β» (σύμφωνα με το Λήμμα 
Απάντλησης Υδάτων [0]), γενικά δεν μπορούν να «θυμηθούν» τι έχουν δει αν 
αυτό δεν έχει κάποια εκ των προτέρων καθορισμένα όρια.

[0] http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

/Απόλλων