Które z następujących wyrażeń jest poprawne?
- istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto.
Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka.
Pompowanie lematu jest niezbędnym warunkiem nieregularności języka.
- Pompowanie lematu jest wystarczającym warunkiem nieregularności języka.
Wiem, że # (4) jest poprawne, a # (3) jest fałszywe, ponieważ „odwrotność tego stwierdzenia nie jest prawdziwa: język, który spełnia te warunki, może nadal być nieregularny”, ale co można powiedzieć o (1) i (2)
Odpowiedzi:
Oto niektóre niezbędne i wystarczające warunki, aby język był regularny.
Twierdzenie. Niech . Następujące warunki są równoważne:L⊆Σ∗
Jeśli język nie nie spełniają warunki lematu pompowania dla języków regularnych , to nie regularna. Oznacza to, że pompowanie lematu jest wystarczającym warunkiem nieregularności języka.
Podsumowując, stwierdzenia 1, 2 i 3 są fałszywe, a stwierdzenie 4 jest prawdziwe, jak wspomniałeś.
źródło
Wystarczy (i konieczne) wykazać istnienie DFA, NFA lub wyrażenia regularnego, aby udowodnić, że język jest regularny, co obala (1) i (2). Aby pokazać, że język nie jest regularny, należy pokazać, że DFA, NFA lub wyrażenie regularne nie istnieje.
Lemat pompowania jest użytecznym narzędziem do pokazania (być może w sprzeczności), że język nie jest regularny, pokazując, że nie istnieje DFA.
źródło
Ten warunek nie ułatwia jednak udowodnienia nieregularności języka. Nie znam żadnych łatwych do sprawdzenia warunków, które zawsze dowodzą nieregularności nieregularnego języka.
Istnieją jeszcze dwa „testy”, które mogą udowodnić nieregularność języka (choć mogą nie działać): możesz spróbować podać jakiś regularny język, taki że ich związek / przecięcie / różnica / konkatenacja / iloraz jest nieregularny ( takich operacji jest więcej) i możesz spróbować policzyć, ile słów generuje, i sprawdzić, czy jest sprzeczne z wyrażeniem liczby słów w zwykłym języku (jak można znaleźć na stronie w Wikipedii, do której linkowałeś).
źródło
Istnieje cudowny związek między formalną teorią języka a formalną serią potęg potwierdzoną przez Chomsky'ego i Schützenbergera [CS63] . W formie znajdującej się w [SS78] Rozdz. II, Twierdzenie 5.1
[SS78] Arto Salomaa i Matti Soittola. Automaty-teoretyczne aspekty formalnej serii mocy. Springer-Verlag, New York, 1978.
[CS63] Noam Chomsky i Marcel P. Schützenberger. Algebraiczna teoria języków bezkontekstowych. W P. Braffort i D. Hirschberg, redaktorzy, Programowanie komputerowe i języki formalne, strony 118–161. Północna Holandia, 1963.
źródło
źródło