Czym różni się brak jednoznaczności od determinizmu?

Próbuję zrozumieć, co należy rozumieć przez „deterministyczny” w wyrażeniach takich jak „deterministyczna gramatyka bezkontekstowa”. (W tej dziedzinie są bardziej deterministyczne „rzeczy”). Byłbym wdzięczny za przykład bardziej niż najbardziej wyszukane wyjaśnienie! Jeśli to możliwe.

Moje główne źródło zamieszania polega na tym, że nie jestem w stanie powiedzieć, w jaki sposób ta właściwość gramatyki różni się od (nie) dwuznaczności.

Znalazłem najbliżej tego, co to znaczy, cytat z artykułu D. Knutha na temat tłumaczenia języków od lewej do prawej :

Ginsburg i Greibach (1965) zdefiniowali pojęcie języka deterministycznego; pokazujemy w części V, że są to właśnie języki, dla których istnieje gramatyka LR (k)

która staje się okrągła, gdy tylko dojdziesz do Section V, ponieważ tam jest napisane, że to, co parser LR (k) może analizować, to język deterministyczny ...

Poniżej znajduje się przykład, który może pomóc mi zrozumieć, co oznacza „ambiwalentny”, spójrz:

onewartwoearewe

Które można przeanalizować jako one war two ear ewelub o new art woe are we- jeśli gramatyka na to pozwala (powiedzmy, że zawiera wszystkie wyrazy, które właśnie wymieniłem).

Co powinienem zrobić, aby ten przykładowy język (nie) był deterministyczny? (Mógłbym na przykład usunąć słowo oz gramatyki, aby gramatyka nie była niejednoznaczna).

Czy powyższy język jest deterministyczny?

PS. Przykład pochodzi z książki Godel, Esher, Bach: Eternal Golden Braid.

Powiedzmy, że definiujemy gramatykę dla przykładowego języka tak:

S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

Czy poprzez tę argumentację o analizie całego łańcucha gramatyka ta sprawia, że ​​język nie jest deterministyczny?

let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

let rec woe_parser s =
  match s with
  | 'w' :: 'e' :: [] -> true
  | 'e' :: 'w' :: 'e' :: [] -> true
  | 'o' :: x -> woe_parser x
  | 'n' :: 'e' :: 'w' :: x -> woe_parser x
  | 'a' :: 'r' :: 't' :: x -> woe_parser x
  | 'w' :: 'o' :: 'e' :: x -> woe_parser x
  | 'a' :: 'r' :: 'e' :: x -> woe_parser x
  (* this line will trigger an error, because it creates 
     ambiguous grammar *)
  | 'o' :: 'n' :: 'e' :: x -> woe_parser x
  | 'w' :: 'a' :: 'r' :: x -> woe_parser x
  | 't' :: 'w' :: 'o' :: x -> woe_parser x
  | 'e' :: 'a' :: 'r' :: x -> woe_parser x
  | _ -> false;;

woe_parser (explode "onewartwoearewe");;
- : bool = true

| Label   | Pattern      |
|---------+--------------|
| rule-01 | S -> A 'we'  |
| rule-02 | S -> A 'ewe' |
| rule-03 | A -> B       |
| rule-04 | A -> BA      |
| rule-05 | B -> 'o'     |
| rule-06 | B -> 'new'   |
| rule-07 | B -> 'art'   |
| rule-08 | B -> 'woe'   |
| rule-09 | B -> 'are'   |
| rule-10 | B -> 'one'   |
| rule-11 | B -> 'war'   |
| rule-12 | B -> 'two'   |
| rule-13 | B -> 'ear'   |
#+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L

Generating =onewartwoearewe=

First way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-01 | A'we'             |
| A'we'             | rule-04 | BA'we'            |
| BA'we'            | rule-05 | 'o'A'we'          |
| 'o'A'we'          | rule-04 | 'o'BA'we'         |
| 'o'BA'we'         | rule-06 | 'onew'A'we'       |
| 'onew'A'we'       | rule-04 | 'onew'BA'we'      |
| 'onew'BA'we'      | rule-07 | 'onewart'A'we'    |
| 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   |
| 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' |
| 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' |
| 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

Second way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-02 | A'ewe'            |
| A'ewe'            | rule-04 | BA'ewe'           |
| BA'ewe'           | rule-10 | 'one'A'ewe'       |
| 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      |
| 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    |
| 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   |
| 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' |
| 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' |
| 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

PDA jest deterministyczny, stąd DPDA, iff dla każdej osiągalnej konfiguracji automatu, istnieje co najwyżej jedno przejście (tj. Co najwyżej jedna nowa konfiguracja możliwa). Jeśli masz PDA, który może osiągnąć konfigurację, dla której możliwe są dwa lub więcej unikalnych przejść, nie masz DPDA.

Przykład:

$Q = \{q_0, q_1\}$$\Sigma = \Gamma = \{a, b\}$$A = q_0$$\delta$

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

Są to niedeterministyczne urządzenia PDA, ponieważ początkowa konfiguracja - q_0, Z0- jest osiągalna, a istnieją dwa ważne przejścia prowadzące od niej, jeśli symbolem wejściowym jest a. Za każdym razem, gdy PDA zaczyna przetwarzać ciąg znaków rozpoczynający się od a, istnieje wybór. Wybór oznacza niedeterministyczny.

Zamiast tego rozważ następującą tabelę przejścia:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

Kusi cię, by powiedzieć, że ten PDA jest niedeterministyczny; w końcu istnieją na przykład dwa ważne przejścia od konfiguracji q1, b(a+b)*. Ponieważ jednak ta konfiguracja nie jest osiągalna przez żadną ścieżkę przez automat, nie ma ona znaczenia. Jedyne osiągalne konfiguracje są podzbiorem q_0, (a+b)*Z0, q1, a(a+b)*Z0i q2, b(a+b)*Z0, i dla każdego z tych konfiguracji, co najwyżej jedno przejście jest zdefiniowana.

CFL jest deterministyczny, jeśli jest to język niektórych DPDA.

CFG jest jednoznaczny, jeśli każdy ciąg ma co najwyżej jedno prawidłowe wyprowadzenie zgodnie z CFG. W przeciwnym razie gramatyka jest dwuznaczna. Jeśli masz CFG i możesz wytworzyć dwa różne drzewa pochodnych dla jakiegoś ciągu, masz niejednoznaczną gramatykę.

CFL jest z natury niejednoznaczny, jeśli nie jest językiem jednoznacznego CFG.

Uwaga:

• Deterministyczny CFL musi być językiem niektórych DPDA.
• Każda CFL jest językiem nieskończenie wielu niedeterministycznych PDA.
• Z natury niejednoznaczny CFL nie jest językiem żadnego jednoznacznego CFG.
• Każda CFL jest językiem nieskończenie wielu niejednoznacznych CFG.
• Z natury niejednoznaczny CFL nie może być deterministyczny.
• Niedeterministyczny CFL może, ale nie musi być z natury dwuznaczny.

Oto przykłady (z Wikipedii):

$S \rightarrow 0S0 | 1S1|\varepsilon$

Język bezkontekstowy jest deterministyczny wtedy i tylko wtedy, gdy istnieje co najmniej jeden deterministyczny automat popychający, który akceptuje ten język. (Może również istnieć wiele niedeterministycznych automatów push-down, które akceptują język, i nadal byłby to język deterministyczny.) Zasadniczo deterministyczne automaty push-down to takie, w których przejścia maszynowe są deterministycznie oparte na bieżącym stanie, symbol wejściowy i aktualny najwyższy symbol stosu . Deterministycznyoznacza to, że nie ma więcej niż jedno przejście stanu dla dowolnego stanu / symbolu wejściowego / najwyższego symbolu stosu. Jeśli masz dwa lub więcej kolejnych stanów dla potrójnego symbolu stanu / wejściowego / najwyższego stosu, wówczas automat nie jest deterministyczny. (Musisz odgadnąć, które przejście wybrać, aby zdecydować, czy automat akceptuje, czy nie.)

Knuth udowodnił, że każda gramatyka LR (k) ma deterministyczny automat odpychający i że wszystkie deterministyczne automaty odpychające mają gramatykę LR (k). Tak więc gramatyki LR (k) i deterministyczne automaty pushdown mogą obsługiwać ten sam zestaw języków. Ale zestaw języków, które mają deterministyczny automat, który je akceptuje, to (z definicji) języki deterministyczne. Argument nie jest okrągły.

Tak więc język deterministyczny implikuje, że istnieje jednoznaczna gramatyka. I pokazaliśmy jednoznaczną gramatykę, która nie ma deterministycznego automatu wypychania (a zatem jest to jednoznaczna gramatyka, która akceptuje niedeterministyczny język).

$\{a^nb^mc^md^n|n,m>0\}$$\{a^nb^nc^md^m|n,m>0\}$$\{a^nb^nc^cd^n|n>0\}$

Deterministyczne języki bezkontekstowe to te, które są akceptowane przez niektóre deterministyczne automaty do odpychania (języki bezkontekstowe to te, które są akceptowane przez niektóre niedeterministyczne automaty do odpychania). Jako taka jest właściwością języka, a nie gramatyki . Natomiast dwuznaczność jest właściwością gramatyki, podczas gdy wrodzona niejednoznaczność jest właściwością języka (język bezkontekstowy jest z natury niejednoznaczny, jeśli każda bezkontekstowa gramatyka dla tego języka jest niejednoznaczna).

Istnieje związek między tymi dwiema definicjami: deterministyczne, pozbawione kontekstu języki nigdy nie są z natury dwuznaczne, jak pokazano w odpowiedzi na to pytanie .

$\{a,b\}$$\{ w \in (a+b)^* \mid w = w^R \}$$S\to aSa | bSb | a | b | \epsilon$$a$$b$$a$$b$$a$$b$

Definicje

1. Deterministyczny akceptor rozwijana do dołu (DPDA) jest automatem rozwijana do dołu, który nigdy nie ma wyboru w jego ruchu.
2. DPDA i NPDA nie są równoważne.
3. CFG jest non deterministyczny wtw istnieją co najmniej dwie produkcje z tego samego prefiksu zacisku po prawej stronie z nich.
4. CFG jest niejednoznaczna IFF istnieje kilka w ∈ L (G), który ma co najmniej dwa różne Wyprowadzenie drzew. Zatem ma dwa lub więcej skrajnych lewych lub skrajnych prawych pochodnych odpowiadających dwóm różnym drzewom pochodnym.
5. CFG jest jednoznaczne wtw każdy ciąg ma co najwyżej jedną ważną wyprowadzenie według CFG. W przeciwnym razie gramatyka jest dwuznaczna.
6. CFL jest z natury wieloznaczne wtw nie jest językiem jakiejkolwiek jednoznacznej CFG. Nie może mieć żadnego DPDA.
   Jeśli każda gramatyka, która generuje CFL, jest niejednoznaczna, wówczas CFL jest nazywana z natury niejednoznaczną . Tak więc to nie jest język jakichkolwiek jednoznacznych CFGs.

Fakty

1. Każda CFL jest językiem nieskończenie wielu niedeterministycznych PDA.
2. Każda CFL jest językiem nieskończenie wielu niejednoznacznych CFG.
3. Świetlówka CFL zaakceptowana przez niektóre DPDA nie jest z natury dwuznaczna. (Istnieje co najmniej jeden jednoznaczny CFG.)
4. CFL zaakceptowany przez NDPDA może, ale nie musi być z natury niejednoznaczny, ponieważ może istnieć dla niego trochę DPDA (lub jednoznaczna CFG).
5. CFL generowany przez niejednoznaczny CFG może, ale nie musi być z natury niejednoznaczny, ponieważ mogą istnieć pewne jednoznaczne CFG (lub DPDA).
6. CFL wygenerowany przez co najmniej jeden jednoznaczny CFG nie jest z natury niejednoznaczny. (Istnieje na to trochę DPDA.)
7. Gramatyka niedeterministyczna może być niejednoznaczna.

Odpowiedz na swoje pytanie (związek między determinizmem a niejednoznacznością)

1. (Nie) dwuznaczność dotyczy głównie gramatyki (tutaj CFG). (Nie) determinizm dotyczy zarówno gramatyki, jak i automatu (tutaj PDA).

   Jeśli chcesz logicznych różnic, możesz spojrzeć na ostatnie cztery punkty w sekcji faktów, gdy próbują one powiązać zarówno dwuznaczność, jak i determinizm. Powtarzam je jeszcze raz:

2. CFL akceptowany przez niektóre deterministyczne PDA nie jest z natury niejednoznaczny . (Istnieje co najmniej jeden jednoznaczny CFG.)

3. CFL akceptowany przez niedeterministyczny PDA może, ale nie musi być z natury niejednoznaczny, ponieważ może istnieć dla niego trochę DPDA (lub jednoznaczna CFG).
4. CFL generowany przez niejednoznaczny CFG może, ale nie musi być z natury niejednoznaczny, ponieważ mogą istnieć dla niego pewne jednoznaczne CFG (lub deterministyczne PDA).
5. CFL wygenerowany przez co najmniej jeden jednoznaczny CFG nie jest z natury niejednoznaczny . (Istnieje na to trochę DPDA.)
6. Non deterministyczny gramatyka mogą lub nie mogą być niejednoznaczne .

PS:

1. W przyjętej odpowiedzi użyto linii takich jak „CFL jest deterministyczny”, „deterministyczny CFL”, „CFL nie może być deterministyczny”, „Niedeterministyczny CFL”. Myślę, że przymiotniki „deterministyczny” i „dwuznaczny” nie dotyczą CFL, ale PDA i CFG. (Chociaż przymiotnik „z natury dwuznaczny” dotyczy CFL) Chociaż nie chcę krytykować oryginalnej odpowiedzi, ponieważ sam nauczyłem się kluczowego punkty z tego. (W rzeczywistości dosłownie skopiowałem kilka wierszy z tej odpowiedzi.) Ale nadal czułem, że należy to poprawić. Starałem się więc ująć rzeczy wyraźniej w dwóch częściach definicji i faktów (mogłem uczynić to niepotrzebnie gadatliwym i długim). Myślę, że powinienem był zredagować oryginalną odpowiedź, ale wtedy będzie to wymagało usunięcia wielu punktów, które wykorzystują powyższe linie. I nie wiem, czy to sprawi, że będzie to jakakolwiek poprawna edycja, ponieważ wymaga całkowitego przepisania.
2. Zauważ, że podałem ilościowe słowa pogrubioną kursywą, aby podkreślić różnice porównawcze w różnych definicjach i faktach. Terminy definicji są tylko pogrubione .
3. Kilka punktów, które sam sobie przedstawiłem, więc będę potrzebować potwierdzenia od osoby znającej się na poprawności każdego punktu.