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

11

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)

Gigili
źródło
2
Raczej powiedziałbym, że (4) jest poprawny: lemat pompowania ma na celu pokazanie, że jakiś język nie jest regularny (stwierdza, że ​​L jest regularny, to ...). Ponadto (3) jest fałszem: en.wikipedia.org/wiki/…
jmad
Zgadzam się z @jmad: lemat pompujący jest wystarczający, nie konieczny.
Patrick87,
@jmad: Artykuł WP, do którego odsyłam w swoim pytaniu, stwierdza, że ​​„zarówno oryginalna, jak i ogólna wersja lematu pompującego dają konieczny, ale niewystarczający warunek, aby język był prawidłowy”.
Gigili,
@Gigli: tak. Regularny. Nie „nieregularny”.
jmad
@jmad: Ups, masz rację. Przeredaguję pytanie, dziękuję.
Gigili,

Odpowiedzi:

18

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Σ

  • 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.ε
  • 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,Σ,P,S)NΣ
  • 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.L.LL
  • 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.L.LL
  • 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 LLLL
  • 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ś.

Janoma
źródło
ω
1
L
@AlextenBrink Nie pamiętam tego! Dzięki, że o tym wspomniałeś. Czy chcesz podać odniesienie?
Janoma,
@Janoma: przepraszam, nie mogę znaleźć żadnego. Dowód jest jednak niezwykle prosty (przejście do NFA iz powrotem).
Alex ten Brink
9

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.

Victor Stafusa
źródło
1
Lemat pompowania, technicznie rzecz biorąc, pokazuje, że DFA nie istnieje dla tego języka.
Patrick87
@ Patrick87: Dzięki. Zredagowałem odpowiedź, aby dodać ten szczegół.
Victor Stafusa,
1
Żeby być pedantycznym: dowody wykorzystujące lemat pompowania nie są dowodem sprzeczności. Ponieważ udowodnisz twierdzenie negatywne (P -> Fałsz), z punktu widzenia intuicjonisty można założyć, że P jest w porządku.
Gallais,
2
pwL
1
Możesz to napisać, ale nie potrzebujesz sprzeczności. O to chodzi.
Janoma
6

LL

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

Alex ten Brink
źródło
6

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

LKchar(L)K

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.

uli
źródło
4

ILxyxILy

  1. zxxzxLyzxL
  2. zyyzyLxzyL

ILL

IL

Patrick87
źródło