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

regular-languages undecidability

— sdcvvc
źródło

Czy możesz podać inne przykłady tak zdefiniowanych języków zwykłych, inne niż

1^{i} 0

$1^i0$ i

01^{i}

$01^i$ , lub

0^{i} 1

$0^i1$ i

10^{i}

$10^i$ ? Co powiesz na przykład na alfabecie złożonym z 3 symboli?

— babou

Jeśli

w_{1}

$w_1$ jest ścisłym pod-słowem

w_{2}

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

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

. 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

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.

w_{1}

$w_1$

w_{2}

$w_2$

w_{1}

$w_1$

w_{2}

$w_2$

— vzn

Biorąc pod uwagę dwa słowa , , czy jest rozstrzygalne, czy język słów zawierających taką samą liczbę i 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 , mówimy, że: $w_1$ $w_2$

zawsze występujez , odnotowano , iff $w_1$ $w_2$ $w_1\triangleleft w_2$
1. dowolny ciąg takie, że z $s$ $s=xw_2y$ i występuje inny rozkład . Uwaga: Warunkiem, że 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) , i i jego symetryczny warianty. $w_1=1^i0$ $w_2=v1^{i+j}$ $y\in1^*$
2. jest ciąg z $s=xw_2y$ tak, że występuje co najwyżej jeden rozkład $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ $s=x'w_1y'$
zawsze cooccurssię , znany $w_1$ $w_2$ , iff każdy zawsze występuje z drugim, $w_1\triangleleft \triangleright\,w_2$
i są niezależne, znany $w_1$ $w_2$ , jeśli żadne nie występuje zawsze z drugim, $w_1\triangleright \triangleleft\,w_2$
zawsze występuje razy lub więcejniż , odnotowano , iff dla dowolnego ciągu taki że z istnieje innych rozkładów $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 oznacza . $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 . 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_1$ $w_2$

Oba słowa łączą się koniecznie razem, chyba że na końcach łańcucha. Dotyczy to tylko par postaci i lub 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 : 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$
, ale nie 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 : wtedy automat skończony może po prostu sprawdzić, czy nie występuje poza wystąpieniem . $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).
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 nigdy nie występuje, chyba że jako część w większym występuje jako przyrostek ciągu (i 3 inne przypadki symetrycznie). $w_1\triangleleft_2 w_2$
$1^i0$ $v$ $v1^j$
$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.

— 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

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

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

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

0^{i} 1 ◃ ▹ 1 0^{i}

$0^i 1 \triangleleft \triangleright 1 0^i$ . This does not satisfy condition 1. of the definition of "

w_{1}

$w_1$ always occurs with

w_{2}

$w_2$ ", since there is no occurrence of

1 0^{i}

$1 0^i$ in

s = 0^{M} 0^{i} 1 1^{M}

$s=0^M 0^i 1 1^M$ .

— 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

0^{M}

$0^M$ or

1^{M}

$1^M$ 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