"Wojciech \"Spook\" Sura" <s...@s...please.op.pl> wrote:

> > Automat skończony jest równoważny "zwykłym" wyrażeniom regularnym.
> > A jaki automat (jeśli w ogóle) odpowiada WR z backtrackingiem?
> > Szukam od jakiegoś czasu bez efektu. TIA
>
> Maszyna Turinga :)

Automat skończony wyrazisz też maszyną Turinga, więc nie o to chodzi. :)

> Nie jestem obeznany z pojęciem backtrackingu - napisz proszę w dwóch słowach
> co to jest, to pokombinuję.

Odwołania wsteczne (tak to chyba jest po polsku), to fragment uprzednio
dopasowanego tekstu i wyrażnie z czymś takim nie definiuje już języka
regularnego. Np. "([a-z]+)\1" oznacza 'dopasuj ciąg literek, a następnie
to samo (\1)' - czyli słowa języka są zawsze postaci XX, gdzie X to dowolny
ciąg literek.

w.

--
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.