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?
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?
Odpowiedzi:
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.
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ć.ambn 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. anbn , dla których wymagany jest prosty alogrithm, aby pamiętać, że liczba a jest 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.
w
Porównaj to z
Mam nadzieję, że to czyni to nieco jaśniejszym.
źródło
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.zan…bn jest 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:
Które są pozbawione kontekstu?
źródło
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 x ∖ L. jest zbiorem ciągów w takie, że x w ∈ L. . Na przykład jeśliL = {zanbn} , następnie a ∖ L = {zan - 1bn| n≥1} , podczas b ∖ L = ∅ . Możemy to łatwo zobaczyćzak∖ L = {zan - kbn| n≥k} . Istnieje nieskończenie wiele ilorazów formularza, więc natychmiast po tym następujeL. nie jest regularny.
Jeśli zbudujemy DFAre zdecydować L, i re będzie w stanie S. po przeczytaniu za , następnie a ∖ L. 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.
źródło