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

w.

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

do góry

Użytkownik "Wojciech Muła" <w...@p...null.onet.pl.invalid>
napisał w wiadomości
news:20100311174035.d50387e5.wojciech_mula@poczta.nu
ll.onet.pl.invalid...
> 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 :)

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

> w.

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

"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ę.

do góry

Użytkownik "Wojciech Muła" <w...@p...null.onet.pl.invalid>
napisał w wiadomości
news:20100313165516.f33b13dc.wojciech_mula@poczta.nu
ll.onet.pl.invalid...
"Wojciech \"Spook\" Sura" <s...@s...please.op.pl> wrote:

>> 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.

Po pierwsze zastanawiam się, czy backtracking jest realizowany automatem,
czy raczej wchodzi tam już jakieś bardziej wysokopoziomowe programowanie, w
sensie zapamiętanie odnalezionego ciągu i dopasowanie go "ręcznie".

Drugi pomysł - możliwe, że powyższe wyrażenie dałoby się zapisać jakąś
gramatyką bezkontekstową. Wówczas można byłoby zastosować automat skończony
ze stosem lub jakąś sprytną kombinację automatu skończonego i automatu
skończonego ze stosem.

> w.

Pozdrawiam -- Spook.

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



--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

"Wojciech Muła" wypyskował/a:
> "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.
[...]
>> 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 gramatyce potrzebny byłby mechanizm dynamicznego dołączania zdefinio-
wanego na podstawie <wyrażenia regularnego> elementu gramatyki. o ile
coś takiego istnieje lub sobie możesz utworzyć.
--
/ qo |) :@=N%_g=v=a=g_eD_e=c()=d=8! =%!gN@8'Re. w8in/ad
\ _x/ , ;h-%-a'hA'H4,X0'Xo~xo~xO,R`-%EXp01ITed: *-7/+eh
/ | ng `-%__%--'__%--'__%--~__%--^%B`/$qV3r[o; &GooMee
L_._o_O_*_^_"_'_`_ -> http://thereis.notlong.com <- `L"EnOF"

do góry

,normalny' nastolatek i mam Neo! <c...@i...lv> wrote:

> w gramatyce potrzebny byłby mechanizm dynamicznego dołączania zdefinio-
> wanego na podstawie <wyrażenia regularnego> elementu gramatyki. o ile
> coś takiego istnieje lub sobie możesz utworzyć.

Przecież istnieje. Dałem wyżej przykład.

w.

do góry

Wojciech Muła 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
>
> w.
>
automat ze stosem

a co masz na mysli mowiac backtracking?

do góry

Radoslaw Jocz <r...@p...onet.pl> wrote:

> Wojciech Muła 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
>
> automat ze stosem
>
> a co masz na mysli mowiac backtracking?

Wyjaśniłem - odwołania wsteczne, na wikipedii jest opis (ale na polskiej
wiki słaby). I nie, automat ze stosem nie da rady takiego dopasowania
wykonać.

w.

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

do góry

Wojciech Muła pisze:
> Radoslaw Jocz <r...@p...onet.pl> wrote:
>
>> Wojciech Muła 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
>> automat ze stosem
>>
>> a co masz na mysli mowiac backtracking?
>
> Wyjaśniłem - odwołania wsteczne, na wikipedii jest opis (ale na polskiej
> wiki słaby). I nie, automat ze stosem nie da rady takiego dopasowania
> wykonać.

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.

JD

do góry

Jędrzej Dudkiewicz <j...@g...com> wrote:

> 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ć.

Tzn. technicznie to jest osiągalne, jasne - przecież wszyscy tego
używamy w VIM-ie i innych narzędziach. :) Mnie interesuje, czy są
w informatyce teoretycznej rozważane jakiś specjalne struktury związane
z tego typu dopasowaniami.

w.

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

do góry