„Osadzanie” języka jako takiego

Pytanie główne / ogólne

Niech $L$ będzie językiem. Zdefiniuj języki $L_i$ pomocą $L_0 = L$ i

L_{i} = {x w y : x y \in L_{i - 1}, w \in L}

$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$ dla

i \geq 1

$i \geq 1$ . Rozważmy

. Tak więc wielokrotnie „osadzić”

w siebie, aby uzyskać

\hat{L} = ⋃ L_{i}

$\hat{L} = \bigcup L_i$

L

$L$

\hat{L}

$\hat{L}$

Czy badano? Czy to ma imię? $\hat{L}$

Przykłady / Motywacja

Zgodnie z wnioskiem w komentarzach oto kilka przykładów, aby lepiej zilustrować, co jest. Skoro nikt (do tej pory) nie widział tego pojęcia, omówię moją motywację do patrzenia na to. $\hat{L}$

Klaus Draeger pobił mnie, dodając przykłady. Umieszczę te przykłady z komentarzy tutaj, aby zwiększyć widoczność, ponieważ są to dobre przykłady.

Jeśli $L$ jest językiem jednoskładnikowa , a następnie (a więc jest regularny). $\hat{L} = L^+$

Jeśli $L = {ab}$ , a jest język Dyck . $\hat{L}$

Oto alternatywny sposób myśleć . Biorąc pod uwagę język nad alfabetem , gramy w następującą grę. Bierzemy dowolny z starają się zmniejszyć celu pusty łańcuch kilkakrotnie usuwania subwords które są w . (W tym miejscu musimy trochę ostrożnie potraktować sam pusty ciąg, aby upewnić się, że jest to równoważne z powyższą definicją, ale jest to moralnie poprawne). $\hat{L}$ $L$ $A$ $w \in A^*$ $w$ $\epsilon$ $L$

Początkowo ja przyszedł zdefiniować rozważając usuwanie uprawnień w słowach. Weź aby być językiem sześcianów nad binarnym alfabetem . Następnie i możemy rozważyć następującą " -deletion" $\hat{L}$ $L = \{w^3 : w \in A^*\}$ $A = \{a,b\}$ $aaabaabaabbabab \in \hat{L}$ $L$

za (za za b za za b za za b) b za b za b \to za b za b za b \to ϵ .

$a(aabaabaab)babab \to ababab \to \epsilon.$

Zauważ, że nie wszystkie usunięcia będą działać

(za za za) b za za b za za b b za b za b \to b za za b za za b b za b za b

$(aaa)baabaabbabab \to baabaabbabab$

i utknęliśmy ze słowem bez kostki. Tak więc, nie ma innej oznaczenie „zdecydowanie -deletable”, który w ogóle nie pokrywa się z . $L$ $\hat{L}$

Jedna końcowa przykład, jeżeli w języku kwadratów na binarnym alfabetu , a jest łańcuchy o zarówno numeru nawet „S i numer nawet ” s. Oczywiście ten warunek jest konieczny. Jednym ze sposobów, aby przekonać się, że wystarczy, jest rozważenie usunięcia kwadratów i przywołanie każdego słowa binarnego o długości 4 lub wielkiej ma kwadrat. Tutaj jest regularny. $L$ $A = \{a,b\}$ $\hat{L}$ $a$ $b$ $\hat{L}$

W przypadku większych alfabetów ten typ argumentu kończy się niepowodzeniem, ponieważ istnieją dowolnie długie słowa bez kwadratów . Z alfabetów o rozmiarze Mogę pokazać nie jest regularny użyciu Myhill-Nerode oraz fakt istnieją dowolnie długo kwadratowych darmowych słowa, ale nie byłem w stanie powiedzieć wiele więcej. Miałem nadzieję, że spojrzenie na to w bardziej abstrakcyjny sposób może rzucić nieco światła na sytuację (i ta bardziej abstrakcyjna definicja wydaje się interesująca sama w sobie). $k \geq 3$ $\hat{L}$

reference-request fl.formal-languages

— John Machacek
źródło

Czy możesz podać kilka ilustrujących przykładów?

— phs,

Przykładowo: jeśli

jest językiem pojedyncza

, a

jest językiem Dyck zbilansowanych ciągów nawiasach; dla języka

nad alfabetem singleton otrzymujemy

(tak jest zawsze regularny w tym przypadku).

L

$L$

{()}

$\{()\}$

\hat{L}

$\hat{L}$

L = {a^{i} | i \in I}

$L=\{a^i|i\in I\}$

\hat{L} = L^{+}

$\hat{L}=L^+$

— Klaus Draeger,

@phs Zmodyfikowałem pytanie z (dużo) większą ilością szczegółów.

— John Machacek,

Jednym z bardziej stosunkowo proste Powoduje to, że jeśli

jest wolna od kontekstu, a następnie tak jest

L

$L$

\hat{L}

$\hat{L}$

— Klaus Draeger,

Dzięki za przykłady i motywację. Teraz łatwiej jest zapamiętać problem i przekazać go innym. Aktualizuj swoje pierwotne pytanie, jeśli masz nowe rozwiązania.

— phs

To pytanie dotyczy tak zwanych systemów wprowadzania .

Układ wstawiania jest specjalnym typem systemu, którego zasady są postaci przepisywania dla wszystkich w danym języku . Napiszmy jeśli i dla pewnego . Oznaczmy przez zwrotnej domknięcie przechodnie relacji . Zamknięcie języka z $1 \rightarrow r$ $r$ $R$ $u \rightarrow_R v$ $u = u'u''$ $v = u'ru''$ $r \in R$ $\buildrel{*}\over\rightarrow_R$ $\rightarrow_R$ $L$ pod to język Przypomnij sobie, żequasi-porządekna zbiorze jest zwrotny i relacja przechodnia taka, że dla dowolnej nieskończonej sekwencji elementów $A^*$ $\buildrel{*}\over\rightarrow_R$

[L]_{{\overset{*}{\to}}_{R}} = {v \in A^{*} ∣ there exists u \in L such that u {\overset{*}{\to}}_{R} v}

$[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}$

E

$E$

⩽

$\leqslant$

x_{0}, x_{1}, \dots

$x_0, x_1, \ldots$

E

$E$ , istnieją dwie liczby całkowite

takie, że

. W [1] udowodniono następujące twierdzenie:

i < j

$i < j$

x_{i} ⩽ x_{j}

$x_i \leqslant x_j$

Jeśli jest skończonym zbiorem słów, tak że język jest skończony, to relacja jest quasi-porządkiem na i jest regularna. $H$ $A^* \setminus A^*HA^*$ $\buildrel{*}\over\rightarrow_R$ $A^*$ $[L]_{\buildrel{*}\over\rightarrow_R}$

[1] W. Bucher, A. Ehrenfeucht i D. Haussler, O wszystkich regulatorach generowanych przez relacje derywacji, Theor. Comput. Sci. 40 , 2-3 (1985), 131–148.

— J.-E. Kołek
źródło

Jak J.-E. Pin wskazał, że moje pytanie dotyczy wstawiania . Znalazłem inne źródło, które opublikuję tutaj dla wszystkich zainteresowanych.

L.Kari. W sprawie wstawiania i usuwania w językach formalnych. Doktorat Praca magisterska, University of Turku, 1991.

Oto część I i część II rozprawy.

Z tego, co mogę powiedzieć, jest to oryginalne źródło badań nad wprowadzaniem.

— John Machacek
źródło