Wystarczający i niezbędny warunek dotyczący prawidłowości języka

Które z następujących wyrażeń jest poprawne?

1. istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto.

2. Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka.

3. Pompowanie lematu jest niezbędnym warunkiem nieregularności języka.

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

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\subseteq\Sigma^*$

• $L$ jest generowany przez wyrażenie regularne (tj. Definicję języka regularnego).
• $L$ jest rozpoznawany przez niedeterministyczny automat skończony ( Kleene ).
• $L$ jest rozpoznawany przez niedeterministyczny automat skończony bez -transitions.$\varepsilon$
• $L$ jest rozpoznawany przez deterministyczny automat skończony ( Scott i Rabin ).
• ( N , Σ , P , S ) N Σ $L$ jest generowany przez gramatykę , gdzie jest skończonym podzbiorem ( Frazier i Page ).$(N,\Sigma,P,S)$$N$$\Sigma^*$
• $L$ jest generowany przez lewą (lub prawą) regularną gramatykę bezkontekstową.
• Indeks relacji Nerode jest skończony (Anil Nerode, Transformacje automatów liniowych , 1958). Jest to powszechnie (i niepoprawnie) znane jako twierdzenie Myhill-Nerode. to relacja używana do budowy minimalnego DFA zwykłego języka.≡ $\equiv_L$$\equiv_L$
• Indeks relacji Myhill jest skończony (John Myhill, Finite Automata and the Representation of Events , 1957). to relacja używana do budowy dowolnego języka.∼ $\sim_L$$\sim_L$
• Syntaktyczna monoida jest skończona (konsekwencja wyniku Myhill). Zauważmy tutaj, że monoid, oprócz tego, że jest zdefiniowany za pomocą relacji , może być zdefiniowany jako minimalny monoid (pod względem wielkości), który rozpoznaje jako preimage homomorfizmu.∼ L$L$$\sim_L$$L$
• $L$ można rozpoznać po maszynie Turinga tylko do odczytu (trywialne).
• $L$ można zdefiniować wzorem w monadycznej logice drugiego rzędu nad łańcuchami ( Büchi ).

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

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.

$L$$L$

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

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

$L$$\mathbb{K}$$\mathrm{char}(L)$$\mathbb{K}$

$\mathrm{char}(L)$

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

$I_{L}$$x$$y$$x I_{L} y$

1. $z_{x}$$xz_{x} \in L$$yz_{x} \in L$
2. $z_{y}$$yz_{y} \in L$$xz_{y} \in L$

$I_{L}$$L$

$I_{L}$