Czy język słów zawierający równą liczbę 001 i 100 jest regularny?

Zastanawiałem się, kiedy języki zawierające taką samą liczbę wystąpień dwóch podciągów będą normalne. Wiem, że język zawierający taką samą liczbę 1 i 0 nie jest regularny, ale jest językiem takim jak , gdzie = liczba wystąpień podłańcucha „001” jest równa liczbie wystąpień podłańcucha „ 100 " zwykły? Zauważ, że ciąg „00100” zostanie zaakceptowany. $L$ $L$ $\{ w \mid$ $\}$

Moja intuicja mówi mi, że tak nie jest, ale nie jestem w stanie tego udowodnić; Nie mogę go przekształcić w formę, którą można pompować za pomocą lematu pompującego, więc jak mogę to udowodnić? Z drugiej strony próbowałem zbudować DFA lub NFA lub wyrażenie regularne i nie udało mi się również na tych frontach, więc jak mam postępować? Chciałbym to ogólnie zrozumieć, nie tylko w przypadku proponowanego języka.

formal-languages regular-languages pumping-lemma Ben Elgar
źródło

Czy widziałeś Jak udowodnić, że język nie jest regularny ?

Juho

Dlaczego nie możesz odpowiedzieć na własne rozwiązanie?

Yuval Filmus

@YuvalFilmus Użytkownicy o niskiej reputacji mogą odpowiedzieć na własne pytanie (8 godzin, jeśli przedstawiciel <100).

Gilles „SO- przestań być zły”

Prawdopodobnie powinna istnieć dodatkowa pętla na ?

0

$0$

q 5

$q5$

Hendrik,

Podobny przykład tego zjawiska, ale dla podciągów „01” i „10” omówiono na naszej siostrzanej stronie. Udowodnienie, że język jest regularny lub nieregularny . Odpowiedź ma podobną uwagę, jak wece w swoim komentarzu: „To znaczy, że przejście 01 nie może nastąpić po innym przejściu bez przejścia ”.

01

$01$

10

$10$

Hendrik,

Odpowiedzi:

Odpowiedź pochodzi z pytania.

Jak zauważył Hendrik Jan, w q5 powinna być dodatkowa pętla samoistna 0.

automat

Juho
źródło

to konstrukcja, a nie dowód

w klasach CS dla prostych problemów czasami podaje się tylko DFA, ale to nie dowodzi, że dokładnie akceptuje język. musisz [jakoś] pokazać, że dla każdego łańcucha wejściowego działa poprawnie. "jak to działa?"

vzn

Myślę, że możesz połączyć i . Czy to prawda?

q_{5}

$q_5$

q_{2}

$q_2$

J.-E.

To podchwytliwe pytanie. Spróbuj zbudować ciąg, który zawiera dwa 001 i nie zawiera 100, i zobacz, dlaczego nie możesz tego zrobić. Jeśli X = „liczba 001”, a Y = „liczba 100”, to X = Y lub X = Y ± 1.

Kiedy zdasz sobie sprawę z podstępu, staje się mało prawdopodobne, aby język był nieregularny, a następnie zbudowanie DFA jest dość proste. Istnieje tylko 8 stanów z ich przejściami, jeśli następnym symbolem jest 0/1:

State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0

Stan początkowy to S0, a S0, S1, C0, C1, C2 akceptują stany.

gnasher729
źródło