Przecięcie kontekstu bez użycia zwykłych języków

Mówi się, że przecięcie języka L bez kontekstu z językiem zwykłym M jest zawsze wolne od kontekstu. Zrozumiałem dowód na konstrukcję wielu produktów, ale wciąż nie rozumiem, dlaczego nie zawiera kontekstu, ale nie jest regularny.

Język generowany przez takie skrzyżowanie ma ciągi znaków, które są akceptowane zarówno przez PDA, jak i DFA. Skoro jest akceptowany przez DFA, to czy nie powinien to być zwykły język? Ponadto, jeśli skrzyżowanie jest regularne, oznacza to również brak kontekstu, ponieważ wszystkie zwykłe języki są również pozbawione kontekstu.

Czy ktoś może mi wyjaśnić, dlaczego język uzyskany przez takie skrzyżowanie nie jest regularny?

regular-languages context-free finite-automata formal-grammars sanjeev mk
źródło

Rozważ. * Jako zwykły język i jego przecięcie z kontekstowym.

AProgrammer

Byłyby to ciągi kontekstowe. Ale te ciągi są również generowane przez zwykły język, więc byłby to język bezkontekstowy, który jest również regularny.

sanjeev mk

Język może być regularny. Ale zwykle tak nie jest. Pomyśl jeszcze raz o kontrprzykładzie podanym przez AProgrammer. To prawdopodobnie powinna być odpowiedź. Każdy język bezkontekstowy jest podzbiorem zwykłego języka. To prawda, że przecięcie języków CF i REG zostanie zaakceptowane przez DFA REG, ale ma to również znaczenie, co zostanie odrzucone.

Karolis Juodelė

cs.stackexchange.com/q/59886/755

@DW Trafne, ale ktoś zaproponował to jako dupek i to nie tak. To pytanie nasuwa pytanie, dlaczego skrzyżowanie nie zawsze jest regularne; drugi pyta, dlaczego skrzyżowanie nie zawsze jest nieregularne. Konkretna konfiguracja tego pytania (mówiąc o ciągach znaków, które są akceptowane zarówno przez DFA, jak i PDA, więc są akceptowane przez DFA, więc język jest prawidłowy, prawda?) Oznacza, że odpowiedzi na drugie pytanie nie są „ Naprawdę dobrze na to odpowiedzieć.

David Richerby

Odpowiedzi:

Jeśli jest pozbawiony kontekstu, to PDA to akceptuje. Jeśli jest regularne, to DFA to akceptuje. Językiem przecięcie składa się ze słów, które są rozpoznawane przez i . $L$ $\mathscr{P}$ $M$ $\mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$

Każde słowo, które jest na skrzyżowaniu jest akceptowana przez , ale nie wszystkie słowa, które zostały zaakceptowane przez są na skrzyżowaniu: tylko te, które są również akceptowane przez . $\mathscr{F}$ $\mathscr{F}$ $\mathscr{P}$

Dowód krzyżowy polega na zbudowaniu automatu który zawiera mechanikę zarówno jak i , i który akceptuje tylko słowa, za które obie strony akceptują. Automat międzyplatformowy to PDA (a zatem rozpoznany język jest pozbawiony kontekstu) - intuicyjnie, ponieważ iloczyn krzyżowy z stanowym DFA polega na pobraniu kopii i dodaniu strzałki między pasujące członkowskie w gdzie DFA $\mathscr{P} \otimes \mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$ $n$ $n$ $\mathscr{P}$ $(q,a,[q])$ $\mathscr{P}$ $a$ strzały. Rezultatem nie jest ogólnie automat skończony (nawet niedeterministyczny), ponieważ część opiera się na stosie, a ta zależność nie w w ogóle. $\mathscr{P}$ $\mathscr{P} \otimes \mathscr{F}$

Trywialna przykładem jest jest regularny, i jeżeli jest kontekst wolny, ale nieregularny, a następnie jest kontekst wolny, ale nieregularny. $\mathscr{A}^*$ $L$ $L \cap \mathscr{A}^* = L$

Gilles „SO- przestań być zły”
źródło

+1 Prawie opublikowałem odpowiedź, która odpowiada Twojemu ostatniemu zdaniu. Szczerze mówiąc, reszta odpowiedzi wydaje się niepotrzebna. :)

Patrick87,

nie dostał „dodawania (q, a, [q]) strzałek między pasującymi stanami w P, gdzie DFA ma strzałki.”. Nie można zwizualizować, jak będzie wyglądał produkt PDA.

anir