Zamknięcie przed właściwym ilorazem za pomocą ustalonego języka

Naprawdę chciałbym pomóc w następujących kwestiach:

W przypadku każdego stałego muszę zdecydować, czy nastąpi zamknięcie w ramach następujących operatorów:$L_2$

1. $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$

2. .$A_l(L)=\{x \mid \exists y \in L : xy \in L_2\}$

Odpowiednie opcje to:

1. Zwykłe języki są zamknięte pod resp. A r , dla dowolnego języka L $A_l$$A_r$$L_2$

2. W przypadku niektórych języków zwykłe języki są zamknięte pod A l resp. A r , a dla niektórych języków L 2 , zwykłe języki nie są zamknięte pod A l resp. A r .$L_2$$A_l$$A_r$$L_2$$A_l$$A_r$

Wierzyłem, że odpowiedź na (1) powinna brzmieć (2), ponieważ kiedy dostanę słowo w i w = x y , mogę zbudować automat, który może odgadnąć, gdzie x zwraca się do y , ale wtedy musi zweryfikować że y należy do L 2, a jeśli nie będzie regularny, jak by to zrobił? Odpowiedź na to pytanie to (1).$w \in L$$w=xy$$x$$y$$y$$L_2$

Co powinienem zrobić, aby poprawnie przeanalizować tych operatorów i ustalić, czy zwykłe języki są pod nimi zamknięte, czy nie?

Aby odpowiedzieć na to pytanie, musimy zezwolić na dowolne . Pomyślmy więc, że L 2 jest bardzo złożonym językiem (powiedzmy, niezdecydowanym językiem).$L_2$$L_2$

Zacznijmy od łatwej pytania: l ( l ) (część pytanie 2). Weź L 2 za nierozstrzygalne i L = { ε } . Co się dzieje?$A_l(L)$$L_2$$L=\{\varepsilon\}$

(moralność: Zawsze sprawdzaj „skrajności”: puste , L = { ε } i L = Σ ∗ ...)$L$$L=\{\varepsilon\}$$L=\Sigma^*$

$A_r$$A_r$$L_2$$L_2$

$A_r(L)$$L_2$

$L_2$$A(L)$

$L$$DFA_L$$x$$q$$y\in L_2$$q$$y$$DFA_L$$y$$L_2$$q$$DFA_{A_L}$$y\in L_2$$q$$y$$DFA_L$

$DFA_{A_L}$$DFA_L$$q$$y\in L_2$$y$$q$$DFA_L$

$L_2$$L_2$

Nie jestem pewien, czy szukasz odpowiedzi na problem, czy nie, więc nie udzielam go bezpośrednio. (Mogę, jeśli chcesz).

Zapytałeś:

Co powinienem zrobić, aby poprawnie przeanalizować tych operatorów i ustalić, czy zwykłe języki są pod nimi zamknięte, czy nie?

$L_2$

• $L$
• $L$$L_2$$A_x$

(a jeśli jedno podejście nie działa, zawsze możesz wypróbować inne).

Dla samego problemu:

$A_l(L) = L_2 / L$$A_r(L) = L / L_2$$L_2$

$A_r$$A_l$$A_l$$L_2$$L_2$$A_l$$L_2$$A_l$$A_l$ $L_2$