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

13

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' |
wvxvw
źródło
1
-1, ponieważ pytanie nie ma teraz sensu. Po pierwsze, łańcuch nie jest językiem; łańcuchy nie są niejednoznaczne, jednoznaczne, deterministyczne ani niedeterministyczne; to tylko struny. Podana gramatyka nie generuje ciągu przykładowego. Nie sprawdziłem wszystkich 180 pochodnych, aby zobaczyć, czy istnieją duplikaty, ale teoretycznie to wszystko, co musisz zrobić, aby zobaczyć, czy gramatyka jest niejednoznaczna. Niestety, język nie może być z natury dwuznaczny, ponieważ jest on skończony, a więc regularny, a zatem zaakceptowany przez DPDA, a więc deterministyczny.
Patrick87
@ Patrick87 eh? Gdzie jest napisane, że ciąg jest językiem? Ten ciąg jest produktem przykładowym i na pewno można go wygenerować przy użyciu podanej gramatyki. Co sprawia, że ​​myślisz inaczej? Ciąg, o którym mowa, jest dokładnie taki, w którym dwie różne sekwencje aplikacji reguł wytwarzają ten sam ciąg, dlatego gramatyka jest niejednoznaczna, ale jeśli usuniesz niektóre reguły (na przykład B -> 'o', to nie będzie już niejednoznaczne ...
wvxvw
Po pierwsze, czy możesz podać pochodną przykładowego ciągu za pomocą gramatyki? Z własnego pytania: „Czy powyższy język jest deterministyczny?” Nigdy nie wymawiasz języka, a jedynie łańcucha, generowanego przez nieskończoną liczbę gramatyk, choć nie tego, który proponujesz.
Patrick87
Czy potrafisz napisać po angielsku? Np. „Zacznij od S. Stosując regułę S := ..., otrzymujemy ......”
Patrick87,
@ Patrick87 Dodałem procedurę generowania krok po kroku, a także zdałem sobie sprawę, że popełniłem błąd w gramatyce, którą naprawiłem.
wvxvw

Odpowiedzi:

9

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={q0,q1}Σ=Γ={za,b}ZA=q0δ

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.
Patrick87
źródło
1
Wiki twierdzi, że PDA nie jest deterministyczne (może istnieć wersja deterministyczna i niedeterministyczna), ale równie dobrze można pominąć pierwszą część zdania, tak naprawdę nie ma to wpływu na to, co mówisz: / Ale to znowu określa język deterministyczny jako język wejściowy czegoś deterministycznego, a to coś nazywa się deterministycznym, ponieważ akceptuje język deterministyczny - to tak, jakby powiedzieć „trawa jest zielona, ​​ponieważ zieleń jest kolorem trawy”. To prawda, ale nie pomaga :( Proszę Przykładem może być więcej niż cenny!
wvxvw
@wvxvw: nie czytasz tego poprawnie. Mówi: „PDA jest deterministyczne wtedy i tylko wtedy, gdy każdy potrójny stan / symbol / stos ma tylko jeden następny stan”. W tej definicji nie ma nic o tym, jaki język akceptuje automat.
Wandering Logic
2
@wvxvw Definicja deterministycznego PDA lub DPDA, której nie podam w żaden sposób, nie kształtuje ani nie opiera się na definicji deterministycznego języka bez kontekstu. Definiuję DPDA tylko na podstawie właściwości automatu. Następnie określam, czym jest deterministyczne CFL pod względem definicji DPDA. Przeczytaj ponownie odpowiedź w świetle tych i komentarzy Wandering Logic i spróbuj sprawdzić, czy ma to sens. Postaram się podać kilka krótkich przykładów.
Patrick87
q1,b(za+b)q2),b(za+b)Q={q0,...q2)}obecna postać? Czy moja interpretacja jest poprawna? x+- jeden lub więcej x, (x)*- zero lub więcej x?
wvxvw,
Konfiguracja @wvxvw odnosi się do bieżącego stanu i bieżącej zawartości stosu. x+zazwyczaj odnosi się do „jednego lub więcej z x, podczas gdy x*zazwyczaj odnosi się do” zero lub więcej z x; Mogę użyć xx*zamiast x+, ponieważ są one identyczne.
Patrick87
7

Oto przykłady (z Wikipedii):

S.0S.0|1S.1|ε

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).

{zanbmdomren|n,m>0}{zanbndomrem|n,m>0}{zanbndodoren|n>0}

Wędrująca logika
źródło
Czy możesz wyjaśnić, dlaczego konieczność spojrzenia na cały ciąg przed określeniem środka sprawia, że ​​ten język jest niedeterministyczny? Przeczytałem inne wyjaśnienie tego, czym jest „deterministyczny” i tam napisano, że „jeśli nie trzeba cofać się podczas analizowania, ten język jest deterministyczny”. Nie widzę potrzeby cofania się w celu przeanalizowania tego języka ...
wvxvw,
1
Rozważ ciąg wejściowy „10011001”. Automaty przesuwania w dół nie wiedzą, jak długi jest łańcuch, dopóki nie dojdzie do końca. Gdy dojdziesz do drugiej cyfry 0, musisz dokonać wyboru: czy jest to czteroznakowy ciąg „1001”, czy dłuższy ciąg, który wygląda jak „100 ???? 001”? Gdy dojdziesz do piątego znaku, którego nadal nie znasz: czy jest to 8-znakowy ciąg „10011001” czy dłuższy ciąg, który wygląda jak „10011 ???? 11001”?
Wandering Logic,
1
„Analizuj cały ciąg” nie jest definicją niedeterministyczną. Chciałem dodać tylko intuicję. Zarówno @ Patrick87, jak i ja podaliśmy wam prawdziwą definicję deterministyczną: z każdego stanu istnieje co najwyżej jeden następny stan. Jeśli język nie ma jednoznacznej gramatyki, musi być niedeterministyczny. Nie mogę odpowiedzieć na twój przykład bez wykonywania większej ilości pracy: wykazałeś się niejednoznaczną gramatyką, ale to nie jest ważne, musisz wykazać, że nie ma jednoznacznej gramatyki, jeśli chcesz pokazać, że język jest z natury niejednoznaczny.
Wandering Logic
1
@wvxvw Jeśli szukasz procedury obliczeniowej, prawdopodobnie nie masz szczęścia ... według en.wikipedia.org/wiki/List_of_undecidable_problems , nie można rozstrzygnąć, czy CFG jest niejednoznaczny, nie mówiąc już, czy jego język jest z natury niejednoznaczny ; nierozstrzygalne jest również, czy CFG generuje wszystkie ciągi. Biorąc to pod uwagę, poważnie wątpię, aby rozstrzygalne, znacznie mniej wydajne było podejmowanie decyzji, czy język CFG jest deterministycznym CFL.
Patrick87
1
@wvxvw Jeśli masz szczęście, to masz do czynienia z tym, co nazywamy szczęśliwym przypadkiem, tj. nie jednym z przypadków, które sprawiają, że jest to nierozstrzygalny problem. Możesz zdefiniować heurystykę, która działa dla wielu szczęśliwych przypadków i nie wysadza pozostałych, ale nie będą działać na wszystkich szczęśliwych przypadkach; gdyby tak się stało, miałbyś decydujący problem, który z naszego założenia jest niemożliwy.
Patrick87
5

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 .

Yuval Filmus
źródło
Przepraszam, to nie jest bardzo pomocne. Zacząłem od DPDA, ale nigdy nie wyjaśnia, dlaczego nazywa się to deterministycznym. Jest to definicja, którą łatwo znaleźć na Wikipedii / Googlingu dla innych artykułów. Ale jaką właściwość gramatyki / języka / parsera opisuje słowo „deterministyczny”? Innymi słowy, co powinno się stać z gramatyką, aby można było ją nazwać deterministyczną?
wvxvw
Przepraszam, jeśli za dużo komentuję. Zamieszanie polega na tym, że nie mogę stwierdzić, na przykład, patrząc na jakiś język, czy jest on deterministyczny, czy nie, i nie wiedziałbym, od czego zacząć identyfikowanie „determinizmu” języka. Niezwykle pomocny byłby przykład języka deterministycznego, a następnie zmienionego w sposób, który czyni go niedeterministycznym.
wvxvw
1
L.R(k)
1
Przepraszamy, ale nadal nie jest pomocny. Rozumiem, co mówisz, ale to nie pomaga mi rozpoznać języka deterministycznego i odróżnić go od niedeterministycznego. Na przykład: jeśli język ma regułę produkcyjną, która stwarza problem zrównoważonego nawiasów, od razu wiem, że FSM nie może go przeanalizować. (Ponieważ wymagałoby stosu). Ale kiedy wspominasz o innym formalizmie, staje się on tylko rekurencyjny, nie pomaga mi zrozumieć, czym ten język powinien się różnić od drugiego.
wvxvw
Innymi słowy (jak wspomniałeś w poprzednim komentarzu), potrzebujesz przykładów deterministycznych i niedeterministycznych bezkontekstowych języków tego samego „sortowania”. Być może powinieneś zadać na ten temat skoncentrowane pytanie.
Yuval Filmus,
1

{za,b}{w(za+b)w=wR}S.zaS.za|bS.b|za|b|ϵzabzabzab

PMar
źródło
1

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.
Maha
źródło
PS 1 jest błędny: istnieje standardowa definicja deterministycznych / niejednoznacznych świetlówek kompaktowych, a mianowicie są one zdefiniowane jako takie, dla których wszystkie CFG są deterministyczne / niejednoznaczne.
reinierpost
właśnie zdałem sobie sprawę, że 7 jest błędny. Również punkt 6 z drugiej ostatniej listy jest taki sam i jest błędny.
Maha
Rzeczywiście ... determinizm nie ma dwuznaczności w żadnym momencie podczas parsowania, więc jest ściśle silniejszy niż dwuznaczność (tj. Dwuznaczność nawet po zakończeniu parsowania).
reinierpost