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$

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

Odpowiednie opcje to:

Zwykłe języki są zamknięte pod resp. , dla dowolnego języka $A_l$ $A_r$ $L_2$
W przypadku niektórych języków zwykłe języki są zamknięte pod resp. , a dla niektórych języków , zwykłe języki nie są zamknięte pod resp. . $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 , mogę zbudować automat, który może odgadnąć, gdzie zwraca się do , ale wtedy musi zweryfikować że należy do 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?

formal-languages regular-languages closure-properties

— Józef
źródło

Co to jest

? Czy masz na myśli „ nie są zamknięte” w drugiej części (b)? Co to jest

A

$A$

L

$L$

— Alex ten Brink

Nadal nie zdefiniowałeś

L

$L$

— Gopi

@Gopi

jest językiem wejściowym.

jest operatorem języków w obu przypadkach.

L

$L$

A (\cdot)

$A(\cdot)$

— Lucas Cook

@Gopi:

jest parametrem

jest stały.

L

$L$

A

$A$

L_{2}

$L_2$

— Raphael

O mój Boże, jak tego nie widziałem.

— Gopi

Odpowiedzi:

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

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

(moralność: Zawsze sprawdzaj „skrajności”: puste , i ...) $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$

— Ran G.
źródło

Wygląda na to, że jednocześnie opublikowałeś odpowiedź na problem. :]

— Lucas Cook

no cóż ... moja odpowiedź zawiera spoilery ... może powinienem umieścić alert spoilera, aby zacząć od twojej odpowiedzi, a jeśli to nie wystarczy - zdobądź szczegóły ...

— Ran G.

Wow, cudowna odpowiedź, bardzo pomocna. Wielkie dzięki Ran!

— Józef

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$

— Lucas Cook
źródło