Dwuznaczność w zwykłych i pozbawionych kontekstu językach

Rozumiem następujące twierdzenia, które są prawdziwe:

Dwie różne pochodne łańcucha w danym CFG mogą czasem przypisywać to samo drzewo parsowania łańcuchowi.
Kiedy w danym CFG występują pochodne jakiegoś łańcucha, które przypisują różne drzewa parsowania, CFG jest niejednoznaczny.
Niektóre języki bezkontekstowe generowane przez niejednoznaczne CFG są również generowane przez jednoznaczne CFG.
Niektóre języki są takie, że jedyne CFG, które mogą je generować (i są takie), są niejednoznaczne.

Pytanie 1 Rozumiem również, że nierozstrzygalne jest, czy arbitralne CFG jest dwuznaczne, w rozumieniu pkt 3 powyżej. A może raczej nie można rozstrzygnąć, czy język bezkontekstowy jest dwuznaczny w rozumieniu punktu 4? Czy oba są nierozstrzygalne?

Q2 Który z punktów 1-4 stanie się fałszywy, gdy zamienimy „bezkontekstowy” na „zwykły”? Czy regularne gramatyki i języki są zawsze jednoznaczne?

fl.formal-languages regular-language context-free dubiousjim
źródło

Języki wymienione w punkcie 4 są „z natury dwuznaczne”. W przypadku pierwszego kwartału uważam, że nie można rozstrzygnąć, czy GRAMMAR jest niejednoznaczny. Zatem zarówno 3, jak i 4 są nierozstrzygalne.

Lamine,

Tak, języki punktu 4 nazywane są „z natury niejednoznacznymi”.

dubiousjim

P1: oba nierozstrzygalne. Pytanie 2: 1 nie jest możliwe, ponieważ co najwyżej jeden nie-terminal pojawia się w dowolnej formie sentymentalnej, dlatego dowolne wyprowadzenie jest zarówno skrajnie lewe, jak i prawostronne; 2 to wciąż prawda; 3 nadal prawda, jeśli usuniesz bit `` również ''; 4 nie jest już prawdą, na przykład poprzez określenie gramatyki otrzymasz jednoznaczny.

Sylvain,

@Sylvain to odpowiedź?

Yuval Filmus

@Sylvain, dzięki i tak, to odpowiedź. Czy mogę potwierdzić, że zrozumiałem? re 2: Czy istnieje regularna gramatyka, która może generować ten sam ciąg znaków z różnymi drzewami analizy? (Od tamtej pory natrafiłem na odniesienie do „dwuznacznych NFA”, ale nie jestem pewien, czy używa „ambig” w tym sensie, że jestem). Re 3 i 4, myślę, że mówisz, że niektóre zwykłe języki mogą być generowane przez dwuznaczne regularne gramatyki, ale zawsze będą również generowane przez niedwuznaczną regularną gramatykę?

dubiousjim

Odpowiedzi:

O Q1: Zarówno problem niejednoznaczności (biorąc pod uwagę CFG, czy jest niejednoznaczny), jak i nieodłączny problem niejednoznaczności (biorąc pod uwagę CFG, czy jego język jest z natury niejednoznaczny, tj. Czy jakikolwiek równoważny CFG jest niejednoznaczny) są nierozstrzygalne. Oto oryginalne odniesienia:

Nierozstrzygalność dwuznaczności udowodnili Cantor (1962) , Floyd (1962) oraz Chomsky i Schützenberger (1963) . Dowody w podręcznikach zwykle zmniejszają się z problemu z korespondencją pocztową.
Nierozstrzygalność wrodzonej dwuznaczności udowodnili Ginsburg i Ullian (1966) .

O Q2: Gramatyka regularna jest bezkontekstową gramatyką „jednostronną liniową”, w której co najwyżej jedna nieterminala pojawia się w dowolnej prawej części reguły i gdzie ta nieterminala jest na końcu (w prawej gramatyce liniowej ) lub na początku (w pozycja lewej gramatyki liniowej ). Takie gramatyki można łatwo przetłumaczyć na równoważne automaty skończone (z grubsza biorąc pod uwagę każdy nieterminal jako stan), które są jednoznaczne, jeśli zwykła gramatyka jest jednoznaczna. Klasa jednoznacznych gramatyk regularnych i jednoznacznych automatów była badana w szczególności przez Stearnsa i Hunta (1985) , którzy wykazują, że lubią algorytmy rozwiązywania problemu integracji.

$\beta A\gamma\Rightarrow \beta\alpha\gamma$ $A\to\alpha$ $A$ $X_1,\dots,X_m$ $A\to X_1\cdots X_m$

$\gamma A\eta B\theta$ $A$ $B$ $A\to\alpha$ $\gamma\alpha\eta B\theta$ $B\to\beta$ $\gamma A\eta\beta\theta$ $\gamma\alpha\eta\beta\theta$ (zawsze wyprowadzając lewostronną nieterminal w dowolnej formie sentymentalnej) lub prawostronne pochodne narzucają stały porządek odwiedzania drzew pochodnych, a następnie jest jedno pochodne dla danego drzewa pochodnych.

W liniowej gramatyce bezkontekstowej nie ma takiego wyboru, ponieważ istnieje co najwyżej jeden nieterminal w dowolnej formie sentymentalnej, a dla danego drzewa pochodnego istnieje jedna pochodna, która jest zarówno skrajna lewa, jak i skrajna prawa.
$w$ $w$ $w$
oraz 4. Jeśli weźmiesz widok automatów skończonych, wystarczy określić twój dwuznaczny automat, aby otrzymać jednoznaczny automat dla tego samego języka: dla każdego słowa będzie jeden przebieg. Ten deterministyczny automat jest równoważny jednoznacznej regularnej gramatyce. $~$

$S\to A\mid B,\,A\to a,\,B\to a$ $a$ $S\Rightarrow A\Rightarrow a$ $S\Rightarrow B\Rightarrow a$ $S\to a$

$O(|G|^2)$ $(q,q')$ $q\neq q'$

Sylvain
źródło

$G$ $\Sigma^*$

Nie do końca wiedziałem, w jakim języku mówisz w 4. Każdy język CF ma niejednoznaczną gramatykę.

Q2 Wszystko jest rozstrzygalne, jeśli masz do czynienia ze zwykłą gramatyką. Po prostu powinieneś zbudować minimalny DFA, a używając go, możesz zbudować jednoznaczną gramatykę. Jeśli masz do czynienia ze zwykłym językiem zdefiniowanym przez gramatykę CF, odpowiedź brzmi nie - patrz Q1.

Alexander Rubtsov
źródło

Dzięki, dobre wyjaśnienia do Q2. Pytania dotyczące zwykłego języka mogą być rozstrzygane, jeśli język jest określony przez zwykłą gramatykę; ale to nie znaczy jeszcze, że można je rozstrzygać, jeśli język jest określony przez CFG --- to właśnie mówisz, prawda? Czy wiemy zatem, że pytania dotyczące dwuznaczności i tak dalej, które są nierozstrzygalne w przypadku dowolnych CFG, są również nierozstrzygalne, gdy są ograniczone do tych CFG, które generują zwykłe języki?

dubiousjim

Być może nie, ale zawsze są rozstrzygalne. Mam na myśli, gdy masz do czynienia z językiem opisanym zwykłą gramatyką - podklasą CFG, każde pytanie, które lubisz, jest rozstrzygalne. Ale niektóre nieregularne CFG mogą produkować zwykły język i nie można rozstrzygnąć nawet, czy CFG produkuje zwykły język.

Alexander Rubtsov,

@ alexandr-rubtsov „Kiedy masz do czynienia z językiem opisanym przez zwykłą gramatykę, każde pytanie, które lubisz, jest rozstrzygalne”. To wygląda na zbyt optymistyczne stwierdzenie ...

J.-E.

Dzięki, miałem na myśli „może być” w swojej retorycznej funkcji, a nie w znaczeniu „kto wie?”

dubiousjim

@ J.-E.Pin tak, powinienem był być bardziej delikatny i powiedzieć coś w stylu „wszystkie naturalne pytania, takie jak dwuznaczność”.

Alexander Rubtsov,

Zależy to od tego, czy „bez kontekstu” zastąpisz „zwykłym” tylko przed „językiem (językami)”, czy też przed „gramatyką”.

Wszystkie zwykłe języki są generowane przez gramatykę regularną , w szczególności przez jednoznaczne gramatyki regularne, np. Gramatyki prawostronne LL (1) , które wszystkie są jednoznaczne.

reinierpost
źródło