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 ewe
lub 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 o
z 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' |
B -> 'o'
, to nie będzie już niejednoznaczne ...S
. Stosując regułęS := ...
, otrzymujemy...
...”Odpowiedzi:
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:
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 jesta
. Za każdym razem, gdy PDA zaczyna przetwarzać ciąg znaków rozpoczynający się oda
, istnieje wybór. Wybór oznacza niedeterministyczny.Zamiast tego rozważ następującą tabelę przejścia:
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ą podzbioremq_0, (a+b)*Z0
,q1, a(a+b)*Z0
iq2, 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:
źródło
x+
- jeden lub więcejx
,(x)*
- zero lub więcejx
?x+
zazwyczaj odnosi się do „jednego lub więcej zx
, podczas gdyx*
zazwyczaj odnosi się do” zero lub więcej zx
; Mogę użyćxx*
zamiastx+
, ponieważ są one identyczne.Oto przykłady (z Wikipedii):
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).
źródło
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 .
źródło
źródło
Definicje
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
Odpowiedz na swoje pytanie (związek między determinizmem a niejednoznacznością)
(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:
CFL akceptowany przez niektóre deterministyczne PDA nie jest z natury niejednoznaczny . (Istnieje co najmniej jeden jednoznaczny CFG.)
PS:
źródło