Czy jest rozstrzygalne, jeśli język opisany przez liczbę wystąpień jest regularny?

14

Wiadomo, że język słów o równej liczbie 0 i 1 nie jest regularny, podczas gdy język słów o równej liczbie 001 i 100 jest regularny ( patrz tutaj ).

Biorąc pod uwagę dwa słowa , czy jest rozstrzygalne, czy język słów zawierający taką samą liczbę i jest regularny?w 1 w 2w1,w2w1w2

sdcvvc
źródło
Czy możesz podać inne przykłady tak zdefiniowanych języków zwykłych, inne niż 1i0 i 01i , lub 0i1 i 10i ? Co powiesz na przykład na alfabecie złożonym z 3 symboli?
babou
Jeśli w1 jest ścisłym pod-słowem w2 , istnieje duża szansa, że ​​język jest pusty, a zatem regularny. Nie znam innych przykładów.
sdcvvc
Podejrzewam, że powyższe przykłady są jedynymi, które sprawią, że problem będzie rozstrzygalny. Jeśli podasz tylko dwa podciągi, domyślam się, że jest to CF ... w zależności od tego, co możesz określić w odniesieniu do zdarzeń. Nie precyzujesz wystarczająco, co rozumiesz przez „opisany przez liczbę wystąpień”.
babou
Pytanie jest wystarczająco precyzyjne IMO.
sdcvvc,
1
dotychczasowe rozwiązania dla przypadków szczególnych wydają się zależeć od idei, że występowanie podłańcuchów gwarantuje tylko pojedyncze wystąpienia interwencji w 2 . więc jakoś zakładając, że aktualne odpowiedzi są poprawne [nie jest dla mnie jeszcze jasne] wydaje się, że istnieje pewna zależność między w 1 , w 2, która gwarantuje w trakcie skanowania łańcucha, że ​​można być w obu stanach „równym” lub „nierównym” ”, ale tylko w przypadku maksymalnej liczby skończonej w przypadku„ nierównego ”przypadku. w1w2w1w2
vzn

Odpowiedzi:

3

Biorąc pod uwagę dwa słowa , w 2 , czy jest rozstrzygalne, czy język L słów zawierających taką samą liczbę w 1 i w 2 jest regularny?w1w2Lw1w2

Najpierw kilka definicji:
można je uczynić bardziej zwięzłymi, a notacje można ulepszyć, jeśli mają być użyte w dowodach. To tylko pierwszy szkic.

Biorąc pod uwagę dwa słowa i w 2 , mówimy, że: w1w2

  • zawsze występujez w 2 , odnotowano w 1w 2 , iff w1 w2w1w2

    1. dowolny ciąg takie, że S = x w 2 r z | x | ,ss=xw2y i | x | 0 , | x | 1 | , | y | 0 , | y | 1 | 1 występuje inny rozkład s = x w 1 y . Uwaga: Warunkiem, że X i Yx,y ≥∣w1+w2|x|0,|x|1|,|y|0,|y|1|1s=xw1y
      xykażdy z nich zawiera co najmniej 0 i 1 jest to wymagane przez patologicznego przypadku (znaleziona przez @sdcvvc) , W 2 = v 1 I + j i r 1 * i jego symetryczny warianty.w1=1i0w2=v1i+jy1
    2. jest ciąg z x ,s=xw2y tak, że występuje co najwyżej jeden rozkład s = x w 1 y x,y ≥∣w1+w2s=xw1y
  • zawsze cooccurssię w 2 , znany w 1w1 w2 , iff każdy zawsze występuje z drugim,w1w2

  • i w 2 są niezależne, znany w 1w1w2 , jeśli żadne nie występuje zawsze z drugim,w1w2

  • zawsze występuje m razy lub więcejniż w 2 , odnotowano w 1 m w 2 , iff dla dowolnego ciągu s, taki że s = x w 2 y zx , y | w 1+ w 2 istnieje m innych rozkładów s = x i w 1 y iw1 mw2w1mw2ss=xw2yx, y| ≥∣w1+w2ms=xiw1yidla tak, że i j oznacza x ix j .i[1,m]ijxixj

Te definicje są skonstruowane, abyśmy mogli zignorować to, co dzieje się na końcach ciągu, w którym powinny wystąpić i w 2 . Efekty brzegowe na końcu łańcucha muszą być analizowane osobno, ale reprezentują one skończoną liczbę przypadków (tak naprawdę myślę, że zapomniałem jednego lub dwóch takich pod-przypadków granicznych w mojej pierwszej analizie poniżej, ale to tak naprawdę nie ma znaczenia). Definicje są zgodne z nakładaniem się wystąpień.w1w2

Do rozważenia są 4 główne przypadki (ignorowanie symetrii między i w 2 ):w1w2

  1. Oba słowa łączą się koniecznie razem, chyba że na końcach łańcucha. Dotyczy to tylko par postaci 1 i 0 i 01 i lub 0 i 1 i 10 i . Można to łatwo rozpoznać poskończonym automacie,który sprawdza tylko pojedyncze zdarzenia na obu końcach łańcucha, aby je rozpoznać, aby upewnić się, że występuje pojedyncze wystąpienie na obu końcach lub na żadnym końcu. Istnieje również przypadek zdegenerowany, gdy w 1 = w 2 : wtedy język L jest oczywiście regularny.w1w2
    1i001i0i110iw1=w2

  2. , ale nie w 2w 1 Jedno z 2 słów nie może wystąpić bez drugiego, ale odwrotność nie jest prawdziwa (chyba że na końcu łańcucha). Dzieje się tak, gdy:w1w2w2w1

    • jest podciągiem w w 2 : wtedy automat skończony może po prostu sprawdzić, czy w 1 nie występuje poza wystąpieniem w 2 .w1w2w1w2

    • w1=1i0 and w2=v1j for some word v{0,1}, v01i: then a finite automaton check as in the previous case that w1 does not occur separated from w2. However, the automaton allows counting one extra instance of w1 that will allow acceptance if w2 is a suffix of the string. There are three other symetrical cases (1-0 symmetry and left-right symetry).

  3. Jedno z dwóch słów występuje dwa razy w drugim. Można to rozpoznać po skończonej automatyzacji, która sprawdza, czy mniejsze słowo nigdy nie występuje w ciągu. Jest to również nieco bardziej złożony wariant, który łączy dwie odmiany przypadku 2. W tym przypadku automat sprawdza, czy mniejszy ciąg 1 i 0 nigdy nie występuje, chyba że jako część v w większym v 1 j występuje jako przyrostek ciągu (i 3 inne przypadki symetrycznie).w12w2
    1i0vv1j

  4. w1w2
    The 2 words can occur independently of each other. We build a generalized-sequential-machine (gsm) G that output a when it recognizes an occurrence of w1 and b when recognizing an occurrence of w2, and forgets everything else. The language L is regular only if the language G(L) is regular. But G(L)={w{a,b} wa=∣wb} which is clearly context-free and not regular. Hence L is not regular.
    Actually we have L=G1(G(L)). Since regular languages and context-free languages are closed under gsm mapping and inverse gsm mapping, we know also that L is context free.

One way to organize a formal proof could be the following. First build a PDA that recognizes the language. Actually it can be done with a 1-counter machine, but it is easier to have two stack symbols to avoid duplicating the finite control. Then, for the cases where it should be a FA, show that the counter can be bounded by a constant that depends only on the two words. For the other cases show that the counter can reach any arbitrary value. Of course, the PDA should be organized so that the proofs are easy enough to carry.

Representing the FA as a 2-stack-symbols PDA is probably the simplest representation for it. In the non-regular case, the finite control part of the PDA is the same as that of the GSM in the proof sketch above. Instead of outputting a's and b's like the GSM, the PDA counts the difference in number with the stack.

babou
źródło
I had a question about context-freeness in the case of three words. I deleted it when I realised it could be analyzed similarly. I had first thought that proving non-CFness would make an original exercise, but the GSM ruins it.
babou
2
It is not clear what do you mean by "occur independently of each other", "come necessarily together" etc. Please write formal definitions instead, and prove that they cover all cases.
sdcvvc
1
I am not sure what you are asking, and what level of formalization you need, for what purpose. I realized that analyzing by hand possible relations of the two words is not garanteed to be correct, and does not matter anyway. What matters is whether an occurence of one word can exist without creating at the same time an occurence (or several) of the other word. The details do not matter as it will always be localized and thus manageable finitely. The two ends do not matter either as tey are localized too. Even overlaps of occurrences do not matter since they can only be finitely many in 1 place
babou
1
I asked you about precise definitions of the terms mentioned in the comment. Thank you for writing them. Was I supposed to guess them previously? Anyway, you seem to claim that 0i110i. This does not satisfy condition 1. of the definition of "w1 always occurs with w2", since there is no occurrence of 10i in s=0M0i11M.
sdcvvc
Sorry, I did not mean to make you guess. It only took me time to understand what exactly you wanted. My failing only. Regarding your counter example, you are correct. But for me it only means that I have to be a little bit more careful about telomeres, in the definition of the relations. I defined them too quickly, but 0M or 1M do not convey much information in this context. This is really a boundary pathological example within a pathological case, that actually cannot occur when more than 2 symbols are used. I just do not believe it changes anything.
babou