Czy istnieją z natury niejednoznaczne i deterministyczne języki bezkontekstowe?

36

Nazwijmy bezkontekstowy język deterministyczny wtedy i tylko wtedy, gdy może on zostać zaakceptowany przez deterministyczny automat odpychający, a niedeterministyczny inaczej.

Nazwijmy język bezkontekstowy z natury dwuznacznym wtedy i tylko wtedy, gdy wszystkie bezkontekstowe gramatyki, które generują ten język, są dwuznaczne, a jednoznaczne inaczej.

Przykładem deterministycznego, jednoznacznego języka jest język: Przykładem niedeterministycznego, jednoznacznego języka jest język:

{{za}^{n} b^{n} \in {za, b}^{*} | n \geq 0}

$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$

{w \in {za, b}^{*} | w = w^{R}}

$\{w \in \{a, b\}^{*} | w = w^{R}\}$

Z Wikipedii przykładem z natury niejednoznacznego języka bezkontekstowego jest następujący związek języków bezkontekstowych, który również musi być pozbawiony kontekstu:

L. = {{za}^{n} b^{m} {do}^{m} {re}^{n} \in {za, b, do, re}^{*} | n, m \geq 0} \cup {{za}^{n} b^{n} {do}^{m} {re}^{m} \in {za, b, do, re}^{*} | n, m \geq 0}

$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$

Teraz pytania:

Czy wiadomo, czy istnieje deterministyczny, z natury dwuznaczny, pozbawiony kontekstu język? Jeśli tak, to czy istnieje (łatwy) przykład?
Czy wiadomo, czy istnieje niedeterministyczny, z natury niejednoznaczny język bezkontekstowy? Jeśli tak, to czy istnieje (łatwy) przykład?

Oczywiście, ponieważ istnieje z natury niejednoznaczny język bezkontekstowy ( jest przykładem), odpowiedź na jedno z tych pytań jest łatwa, jeśli wiadomo, czy jest deterministyczny czy niedeterministyczny. Zakładam również, że to prawda, że jeśli jest deterministyczny, to na pewno też będzie niedeterministyczny ... ale wcześniej byłem zaskoczony. Referencje są mile widziane i z góry przepraszamy, jeśli jest to dobrze znany, znany wynik (w takim przypadku jestem całkowicie nieświadomy tego). $L$ $L$

— Patrick87
źródło

30

Jeśli język jest deterministyczny, jest akceptowany przez jakiś deterministyczny automat odpychający, co z kolei oznacza, że istnieje pewna gramatyka LR (1) opisująca język, a ponieważ każda gramatyka LR (1) jest jednoznaczna, oznacza to, że nie może z natury być dwuznacznym. Knuth udowodnił to w swoim artykule, w którym przedstawił LR (1) ( O tłumaczeniu języków od lewej do prawej ). $L$ $L$

Język może być opisany przez gramatykę bezkontekstową wtedy i tylko wtedy, gdy może zostać rozpoznany przez jakiś niedeterministyczny automat. Jako szczególny przypadek tego, z natury niejednoznaczne gramatyki bezkontekstowe mogą zostać przeanalizowane przez jakiś niedeterministyczny automat.

W ostatecznym rozrachunku, każdy deterministyczny automat odpychający jest również niedeterministyczny (dotyczy to niemal wszystkiego, co może być niedeterministyczne, w przypadku rozsądnej definicji niedeterminizmu).

— Alex ten Brink
źródło

+1 za odniesienie dla faktu, że wszystkie deterministyczne świetlówki kompaktowe nie są z natury niejednoznaczne. W rzeczywistości odpowiada to również na inne pytanie: ponieważ istnieje z natury niejednoznaczny język i nie jest on deterministyczny, musi być niedeterministyczny (zauważ, że moja definicja niedeterministycznego CFL nie jest standardowa, ponieważ wyklucza deterministyczne CFL; to moja wina za niewłaściwe użycie terminologii). W każdym razie podałeś przykład pytania (2) i pokazałeś, że pytanie (1) jest niemożliwe. Poczekam i zobaczę, czy ktoś opracuje więcej, ale w przeciwnym razie zaakceptuje to jako poprawne. Dzięki!

— Patrick87,

0

czytając wikipedię oraz odpowiedź i komentarz na ten temat, ponownie (Q2), stwierdzając wprost, wszystkie wrodzone niejednoznaczne świetlówki kompaktowe muszą być niedeterministyczne zgodnie ze standardową definicją (w tym własnym przykładem!). natknąłem się na ten ref

Niektóre z natury niejednoznaczne języki bezkontekstowe / Shamir i prawdopodobnie inne są badane w literaturze.

— vzn
źródło