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

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 $w_1,w_2$$w_1$$w_2$

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?$w_1$$w_2$$L$$w_1$$w_2$

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: $w_1$$w_2$

• zawsze występujez w 2 , odnotowano w 1 ◃ w 2 , iff $w_1$ $w_2$$w_1\triangleleft w_2$

  1. dowolny ciąg takie, że S = x w 2 r z | x | $s$$s=xw_2y$ 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$\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$$|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$$s=x'w_1y'$
     $x$$y$każ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.$w_1=1^i0$$w_2=v1^{i+j}$$y\in1^*$
  2. jest ciąg z ∣ x ∣ $s=xw_2y$ tak, że występuje co najwyżej jeden rozkład s = x ′ w 1 y $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$$s=x'w_1y'$

• zawsze cooccurssię w 2 , znany w 1 ◃ $w_1$ $w_2$ , iff każdy zawsze występuje z drugim,$w_1\triangleleft \triangleright\,w_2$

• i w 2 są niezależne, znany w 1 ▹ $w_1$$w_2$ , jeśli żadne nie występuje zawsze z drugim,$w_1\triangleright \triangleleft\,w_2$

• 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 z ∣ x ∣ , ∣ y ∣ | ≥ ∣ w 1 ∣ + ∣ w 2 ∣ istnieje m innych rozkładów s = x i w 1 y $w_1$ $m$$w_2$$w_1\triangleleft_m w_2$$s$$s=xw_2y$$\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid w_2\mid$$m$$s=x_iw_1y_i$dla tak, że i ≠ j oznacza x i ≠ x j .$i\in[1,m]$$i\neq j$$x_i\neq x_j$

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ń.$w_1$$w_2$

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

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.$w_1\triangleleft \triangleright\,w_2$
   $1^i0$$01^i$$0^i1$$10^i$$w_1=w_2$

2. , ale nie w 2 ◃ w 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:$w_1\triangleleft w_2$$w_2\triangleleft w_1$
   

   • 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 .$w_1$$w_2$$w_1$$w_2$

   • $w_1=1^i0$ and $w_2=v1^j$ for some word $v\in\{0,1\}^*$, $v\neq01^i$: then a finite automaton check as in the previous case that $w_1$ does not occur separated from $w_2$. However, the automaton allows counting one extra instance of $w_1$ that will allow acceptance if $w_2$ 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).$w_1\triangleleft_2 w_2$
   $1^i0$$v$$v1^j$

4. $w_1\triangleright \triangleleft\,w_2$
   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 $w_1$ and $b$ when recognizing an occurrence of $w_2$, and forgets everything else. The language $L$ is regular only if the language $G(L)$ is regular. But $G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$ which is clearly context-free and not regular. Hence $L$ is not regular.
   Actually we have $L=G^{-1}(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.