epsilon$ while read LINE; do echo \>"$LINE"; done < "Michoo"
>>>>> Wydaje mi się, że "wystarczy" zarezerwować miejsce w automacie na
>>>>> dodatkowe stany i dołożyć je, kiedy ciąg już jest znany. Wszak to "\1"
>>>>> to nic innego, jak ustalony ciąg znaków.
>>>> Nic podobnego, \1 może być dowolnym ciągiem. Nie wiesz, ile będziesz
>>>> potrzebował zarezerwować.
>>> A ile musisz zarezerwować na [a-z]+
>>> ?
>> W automacie skończonym? Zero. Nie ma żadnego "bufora" - automat zmienia
>> stan na podstawie funkcji przejść.
>W automacie - nie (no chyba, że ze stosem), ale automat ma jakieś
>"wejście" i ono musi zadbać o odpowiednie buforowanie.

Nie ma żadnego buforowania. Czytasz po znaku z wejścia i zmieniasz stany
zgodnie z funkcją przejść. Nie masz żadnej wiedzy odnośnie znaków
wcześniejszych/późniejszych. W przypadku backrefów musisz tę wiedzę
mieć.

>>> Skoro dopasowałeś ten tekst do miejsca wystąpienia backrefa to znaczy,
>>> że gdzieś go masz w buforze na wypadek gdybyś się wycofywał.
>> Ja mogę mieć wszystko, ale który automat rozumie pojęcie "bufora"? :)
>> O to się cały czas rozchodzi - nie o algorytm, tylko o nazwę konstrukcji
>> teoretycznej.
>Automat ze stosem? - Ma "bufor". Inaczej (bez bufora) chyba nie da się
>zapewnić samego _zapamiętania_ dopasowanych ciągów. A to jest pierwszy
>etap do ich późniejszego dopasowania. Teorii niestety nie znam na tyle,
>żeby coś więcej powiedzieć.

Nie chce mi się za bardzo wgłębiać (a niewiele pamiętam ;->), ale
wikipedia twierdzi, że:
"Many features found in modern regular expression libraries provide an
expressive power that far exceeds the regular languages. For example,
many implementations allow grouping subexpressions with parentheses and
recalling the value they match in the same expression (backreferences).
This means that a pattern can match strings of repeated words like
"papa" or "WikiWiki", called squares in formal language theory. The
pattern for these strings is (.*)\1.

However, the language of squares is not regular, nor is it
context-free."

Czyli backrefy wychodzą poza języki bezkontekstowe, a więc PDA nie
wystarczy.

--
d'`'`'`'`'`'`'`'`'`'`'`'`'Yb
`b K...@e...eu.org d'
d' http://epsilon.eu.org/ Yb
`b,-,.,-,.,-,.,-,.,-,.,-,.d'