Jak intuicyjnie czuć, że język jest regularny

9

Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?L.={zanbndon}

Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest możliwe?

dawca
źródło
1
Każdy może spojrzeć na dowolny język i po prostu powiedzieć, że to nie jest regularne. Nie jestem pewien, czy intuicja, per se, jest tu tak samo ważna, jak doświadczenie. Jest to dość prosty język (mimo że jest nieregularny) i jest nieuchronnie spotykany w nauce języków formalnych. Gdy dowiesz się, że nie jest to regularne i udowodniłeś, że nie jest to regularne stosowanie jakiejkolwiek ważnej techniki dowodu, zwykle nie potrzebujesz dowodu, aby przekonać innych ludzi, ponieważ wszyscy udowodnili to sami, gdy zostali wprowadzeni do Przedmiot.
Patrick87
tak, ale czasami na wykładach po prostu podążają za suchymi matematycznymi dowodami, ale naprawdę brakuje im intuicyjnych wyjaśnień z prawdziwymi prostymi przykładami
dawca
Zapomnij . Czy kiedykolwiek zdawało ci się, że nie jest regularny? zanbndonzanbn
Uday Reddy,
2
Patrzenie na gramatykę i głoszenie, ponieważ gramatyka nie jest regularna, język nie jest regularny, jest błędem. Istnieje wiele nieregularnych gramatyk dla zwykłych języków. Strzec się! To powiedziawszy, podjęcie decyzji, czy gramatyka jest regularna, jest łatwe; po prostu sprawdź produkcje.
Raphael
Jest to podobne pytanie na math.SE .
Raphael

Odpowiedzi:

11

Główną właściwością DFA / NFA jest brak nieograniczonej pamięci. Jeśli spojrzysz na język i jedyny algorytm (który później powinien zostać przetłumaczony na automat skończony), który wymyślisz, wymaga tej właściwości, to znaczy czujesz, że każdy algorytm, który go rozpozna, będzie musiał zapamiętać dowolną dużą liczbę rzeczy (lubićn w twoim przykładzie), to prawdopodobnie ten język nie jest regularny.

Oczywiście, zawsze powinieneś pamiętać, że intuicja matematyczna może się mylić, a jedynym sposobem, aby być pewnym swojej intuicji, jest jej udowodnienie.

EDYCJA: Odpowiem na ostatnie pytanie w komentarzach tutaj, z powodu braku miejsca.

mówicie o nieograniczonej pamięci, co masz na myśli to, że nie jest ona regularna. ale ^ nb ^ m może również mieć nieograniczoną pamięć, jeśli chcę, prawda? to wciąż nie daje mi spokoju.

Problem nie polega na tym, jak duże mogą być te słowa (zwykle napotykasz nieskończone regularne języki, ponieważ każdy skończony język jest regularny, a to dość nudne), ale ile DFA musi pamiętać.
wzambn na przykład nie trzeba pamiętać m,n. Algorytm musi tylko upewnić się, że są pozytywne i że słowo jest poprawnie uporządkowane. To jest skończona lista, a każdy z elementów na liście wymaga stałej ilości pamięci.
Porównaj to zzanbn, dla których wymagany jest prosty alogrithm, aby pamiętać, że liczba zajest równa liczbie b„s. Będzie to wymagało nieograniczonej pamięci. Kiedy patrzę na język i widzę, że każdy algorytm, o którym mogę myśleć, potrzebuje nieograniczonej pamięci, moja intuicja, że ​​język nie jest regularny, staje się silniejsza. Jeśli nie uda mi się znaleźć „inteligentnego” algorytmu (wymagającego stałej ilości pamięci) w rozsądnym czasie (ile rozsądnego czasu zależy od ciebie), spróbuję udowodnić, że język nie jest regularny.
Mam nadzieję, że to czyni to nieco jaśniejszym.

Boris Trayvas
źródło
dziękuję, matematyka dowodzi, że przynosi intuicję, ale spójrz na tę zasadę produkcji: S -> ab | aSb. dotyczy to ^ nb ^ n, który mówi, że to także nie jest regularne. ale ^ mb ^ n jest regularne z m, n> = 1. dlaczego to? są to w rzeczywistości ta sama forma, prawda? nie rozumiem różnicy między tymi dwoma językami
dawca
1
W przypadku ^ nb ^ n musisz śledzić 2 rzeczy: po pierwsze, że liczba a jest równa liczbie b (jest to część niemożliwa dla DFA), a po drugie, że po „b” nie następuje „a” „. Dla ^ mb ^ n nie obchodzi cię wartość m, n. Dbasz tylko o to, że jest co najmniej jeden „a” i co najmniej jeden „b” oraz że po „b” nie następuje „a”. Mówiąc nieoficjalnie, musisz pamiętać tylko 3 rzeczy.
Boris Trayvas
och, okej, teraz to rozumiem.
doniyor
więc kolejność jest również kluczowa, prawda? jak aabbcc akceptowane, ale nie aabcbc tylko dlatego, że zamówienie nie jest w porządku. dobrze?
doniyor
1
„Główną właściwością zwykłych języków jest brak nieograniczonej pamięci”. - Wiem, co masz na myśli, ale zdanie to nie ma sensu. „czujesz, że każdy algorytm, który go rozpozna, będzie musiał zapamiętać dowolną dużą liczbę rzeczy” - to rzeczywiście jedyna intuicja, jaką znam, ale jej rodzaj jest bardzo, bardzo niebezpieczny; patrz tutaj .
Raphael
5

Mógłbym użyć lematu pompującego

Dokładnie. Kiedy użyjesz lematu Pumping lub dowolnej innej techniki kilka (kilkadziesiąt) razy, zaczniesz widzieć wzorce w językach, które zabraniają ich regularności.zanbnjest bardzo podstawowy, który prawdopodobnie już opanowałeś. Jest to więc kwestia doświadczenia, nie tylko intuicji.

Dobrym sposobem na sprawdzenie intuicji jest spojrzenie na te języki:

  1. {xyyzx,y,z{za,b}+}
  2. {xyyzx,y,z{a,b}}
  3. {xyyzx,y,z{a,b,c}+}
  4. {xyyzx,y,z{za,b,do}}

Które są pozbawione kontekstu?

Raphael
źródło
1
Jeśli ktoś zna podobnie miłe przykłady granic zwykłych języków, proszę to powiedzieć. Nie psuj odpowiedzi w komentarzach.
Raphael
Raphael - świetna robota! dziękuję za podanie przykładów i za wyraźne przetestowanie mnie.
doniyor
4

Możesz faktycznie zdecydować, czy język jest regularny, używając dość prostych obliczeń, zamiast robić pełny dowód. Musisz po prostu zastosować jedno bardzo silne kryterium: język jest regularny wtedy i tylko wtedy, gdy ma skończenie wiele ilorazów.

Intuicyjnie iloraz jest tym, czego potrzebujesz, aby uzupełnić słowo po przeczytaniu już części danych wejściowych. Bardziej formalnie, lewy iloraz językaL. sznurkiem x, napisane xL. jest zbiorem ciągów w takie, że xwL.. Na przykład jeśliL.={zanbn}, następnie zaL.={zan-1bn|n1}, podczas bL.=. Możemy to łatwo zobaczyćzakL.={zan-kbn|nk}. Istnieje nieskończenie wiele ilorazów formularza, więc natychmiast po tym następujeL. nie jest regularny.

Jeśli zbudujemy DFA re zdecydować L, i re będzie w stanie S. po przeczytaniu za, następnie zaL. jest językiem ustalonym przez re zmodyfikowany tak, aby miał stan początkowy S.. Ten sam pomysł można wykorzystać do bezpośredniej budowy minimalnego DFA, który decyduje o zwykłym języku na podstawie jego definicji.

James Koppel
źródło
b \ L oznacza: jeśli podzielę L przez b, to dostanę pusty zestaw ?. czy to dlatego, że tak naprawdę muszę zacząć czytać to słowo od samego początku? a nie z tyłu?
doniyor
1
bL.= ponieważ w L nie ma ciągów rozpoczynających się od B. Możesz zdefiniować odpowiedni iloraz L./bpodobnie, co odpowiada „czytaniu od tyłu”. Język jest również regularny, jeśli ma skończenie wiele poprawnych ilorazów, ponieważ odwrócenie zwykłego języka jest regularne. (Łatwo to pokazać za pomocą NFA.)
James Koppel
1
Oto dobra talia slajdów, która wyjaśnia iloraz i jak konstruować z nich DFA
James Koppel
och ok, wielkie dzięki. teraz dostaję trochę. mmm ... pozwólcie, że jeszcze raz przestudiuję to ...
dawca