Niejednoznaczna gramatyka

W teoretycznej informatyki i teorii języka , niejednoznaczne lub niejednoznaczna gramatyki jest algebraiczne gramatyka , która przyjmuje słowo z dwóch różnych lewych indeks lub - równoważnie - dwa odrębne drzewami pochodne . Niejednoznaczność lub jednoznaczność jest właściwością gramatyki, a nie języków. Wiele języków dopuszcza zarówno gramatyki niejednoznaczne, jak i jednoznaczne, podczas gdy inne mają tylko gramatyki niejednoznaczne. Jeden język, dla którego wszystkie gramatyki są niejednoznaczne, nazywany jest z natury niejednoznacznym (lub z natury niejednoznacznym) , pozostałe nazywane są językami jednoznacznymi .

Gramatyka odniesienia języków programowania jest czasami niejednoznaczna z powodu konstrukcji, które prowadzą do problemów, takich jak problem wiszący else . Takie niejasności są zwykle rozwiązywane poprzez dodanie reguł pierwszeństwa lub innych reguł, kontekstowych, które czynią ostateczną gramatykę jednoznaczną.

Przykłady

Dodawanie i odejmowanie

Gramatyka algebraiczne zdefiniowany przez następującą zasadą

A → A + A | A - A | w

jest niejednoznaczne, ponieważ słowo a + a - a ma dwie różne lewe wyprowadzenia:

A → A - A → A + A - A → a + A - A → a + a - A → a + a - a

A → A + A → a + A → a + A - A → a + a - A → a + a - a

W pierwszym kroku reguła A → A + A jest używana w drugim kroku; w drugiej, przeciwnie, stosuje się regułę A → a.

Te wyprowadzenia dają dwa różne drzewa derywacji:

Sam język jest jednoznaczny (tj. Nie jest z natury niejednoznaczny), ponieważ jest generowany na przykład przez jednoznaczną gramatykę, która następuje:

A → A + a | A - a | w

Palindromes

Język palindromów jest jednoznaczny. Jest generowany (na przykład na alfabecie a, b) przez jednoznaczną gramatykę, zdefiniowaną przez następującą regułę:

A → aAa | bAb | a | b | ε

Z natury niejednoznaczne języki algebraiczne

Przykład 1 - Język jest algebraiczny i z natury niejednoznaczny. ${\ Displaystyle L = \ {a ^ {\ ell} b ^ {m} c ^ {n} \ mid m = \ ell \ {\ tekst {lub}} \ m = n \}}$

Każdy z języków i jest algebraiczny. Pierwsza jest na przykład generowana przez następującą gramatykę: ${\ Displaystyle L_ {1} = \ {a ^ {m} b ^ {m} c ^ {n} | ~ m, n \ geq 0 \}}$ ${\ Displaystyle L_ {2} = \ {a ^ {m} b ^ {n} c ^ {n} | ~ m, n \ geq 0 \}}$

S → Sc | T T → aTb | ε

$L$ jest algebraiczny jako związek tych dwóch języków algebraicznych.

Słowa są problemem. Możemy udowodnić, używając lematu Ogdena (dowód jest na odpowiedniej stronie), że nie ma jednoznacznej gramatyki dla tego języka. Inne przykłady podano w książce Harrisona lub w książce Cartona. Inną metodą zademonstrowania nieodłącznej niejednoznaczności języka jest przejście przez funkcję generatora, która wylicza liczbę słów danej długości w języku. Zgodnie z twierdzeniem Chomsky'ego-Schützenbergera , ten szereg jest algebraiczny dla języka generowanego przez jednoznaczną gramatykę. $L_ {1} \ cap L_ {2}$

Przykład 2 - Goldstine język jest z natury niejednoznaczne.

To jest przykład zastosowania tej metody.

Przykład 3 - Język utworzony przez słowa , gdzie i są palindromami, jest z natury niejednoznaczny. $xy$ $x$ $y$

Podczas gdy sam język palindromów jest jednoznaczny.

Przykład 1 ' - Język słów składających się z trzech liter i utworzonych słów, takich jak lub, jest z natury niejednoznaczny. $a, b$ $vs$ $w$ ${\ displaystyle | w | _ {a} \ neq | w | _ {b}}$ ${\ displaystyle | w | _ {c} \ neq | w | _ {b}}$

Ten język jest zbliżony do pierwszego podanego przykładu.

Demonstracja

Demonstracja jest interesująca, ponieważ przechodzi przez komplementarność. Próbujemy pokazać, że generujący ciąg języka nie jest algebraiczny. Wystarczy, aby udowodnić, że szereg generujący język komplementarny

{\ displaystyle M = \ {w \ mid | w | _ {a} = | w | _ {b} = | w | _ {c} \}}

nie jest algebraiczne. Teraz ta seria jest

{\ displaystyle f_ {M} (z) = \ suma _ {n \ geq 0} {\ frac {(3n)!} {n! ^ {3}}} z ^ {3n}}

a według wzoru Stirlinga współczynnik asymptotycznie równa się ${\ displaystyle z ^ {3n}}$

{\ Displaystyle 3 ^ {3n} {\ Frac {\ sqrt {3}} {2 \ pi n}}}

Jednak zgodnie z ogólnym wynikiem Philippe'a Flajoleta , asymptotyczny odpowiednik formy jest charakterystyczny dla funkcji transcendentnej. ${\ Displaystyle \ beta ^ {n} / n}$

Nieruchomości

W deterministycznych językach algebraicznych zawsze występuje niejednoznaczna gramatyka. Stanowią ścisłą podklasę rodziny języków jednoznacznych. Powyższy język palindromów stanowi przykład niedeterministycznego języka algebraicznego, który jest jednoznaczny.

Własność - następujący problem jest nierozstrzygalny : „Czy dana gramatyka jest niejednoznaczna?” ”.

Dowód podany poniżej dotyczy problemu korespondencji Post .

Demonstracja

Możemy zmniejszyć korespondencji problemu Post mogą problemu niejednoznaczności.

Rozważmy przykład problemu korespondencji pocztowej (PCP) w alfabecie . Wprowadzamy nowy alfabet złożony z liter nienależących do . Na alfabecie definiujemy dwa języki: ${\ displaystyle (u_ {1}, v_ {1}), \ dotsc, (u_ {m.}, v_ {m.})}$ $\ Sigma$ ${\ displaystyle A = \ {a_ {1} \ dotsc, a_ {m.} \}}$ $m$ $\ Sigma$ ${\ displaystyle A \ cup \ Sigma}$

{\ displaystyle L_ {u} = \ {u_ {i_ {1}} u_ {i_ {2}} \ dotsb u_ {i_ {n}} a_ {i_ {n}} \ dotsb a_ {i_ {2}} a_ {i_ {1}} \ mid n \ geq 0, \ 1 \ leq i_ {k} \ leq m \}}

{\ displaystyle L_ {v} = \ {v_ {i_ {1}} v_ {i_ {2}} \ dotsb v_ {i_ {n}} a_ {i_ {n}} \ dotsb a_ {i_ {2}} a_ {i_ {1}} \ mid n \ geq 0, \ 1 \ leq i_ {k} \ leq m \}}

Organ PCP dopuszcza rozwiązanie wtedy i tylko wtedy, gdy . Język jest generowany przez gramatykę z następującymi zasadami: ${\ displaystyle (u_ {1}, v_ {1}), ..., (u_ {m.}, v_ {m.})}$ ${\ Displaystyle L_ {u} \ czapka L_ {czas} \ neq \ emptyset}$ ${\ Displaystyle (L_ {u} \ filiżanka L_ {v}) \ setminus \ {\ varepsilon \}}$

{\ displaystyle S \ do U \ mid V}

{\ Displaystyle U \ to \ sum _ {i = 1} ^ {m} {u_ {i} Ua_ {i}} \ mid \ sum _ {i = 1} ^ {m} {u_ {i} a_ {i }}}

{\ Displaystyle V \ to \ sum _ {i = 1} ^ {m} {v_ {i} Va_ {i}} \ mid \ sum _ {i = 1} ^ {m} {v_ {i} a_ {i }}}

Łatwo zauważyć, że ta gramatyka jest niejednoznaczna wtedy i tylko wtedy , gdy ; i że to skrzyżowanie jest puste wtedy i tylko wtedy, gdy dopuszcza rozwiązanie. Redukcja jest obliczeniem powyższej gramatyki z instancji PCP . Dowodzi to, że problem niejednoznaczności jest nierozstrzygalny. ${\ Displaystyle L_ {u} \ czapka L_ {czas} \ neq \ emptyset}$ ${\ Displaystyle (u_ {1}, v_ {1}), \ ldots, (u_ {m.}, v_ {m.})}$ ${\ Displaystyle (u_ {1}, v_ {1}), \ ldots, (u_ {m.}, v_ {m.})}$

Stopień niejednoznaczności

Stopień dwuznaczności wyrazu w generowanego przez gramatykę jest liczba pozostawionych indeks, inne, które sprawiają, że można dojść do słowa wag . Stopień niejednoznaczności gramatyki to maksymalna (prawdopodobnie nieskończona) liczba stopni słów wygenerowanych przez tę gramatykę.

Własność - istnieją języki z natury niejednoznaczne, dla których stopień niejednoznaczności dowolnej gramatyki jest nieskończony.

Rozstrzygalność z następującym stwierdzeniem jest problemem otwartym (w roku 1977): „Biorąc pod uwagę gramatykę, jest jego stopień niejednoznaczności skończoności?” "

Uwagi i odniesienia

Hopcroft i Ullman 1969 .
Harrison 1978 .
Ramka 2014 , sekcje 2.3.3 i 2.3.4.
Berstel i Boasson 1990 .
Flajolet 1987 .
Hopcroft, Motwani i Ullman 2007 .
Mateescu i Salomaa 1997 - Rozdział 6.5: „ Niejednoznaczność ”, s. 238-240 .

Powiązany artykuł

Amfibologia

Bibliografia

John E. Hopcroft i Jeffrey D. Ullman, Języki formalne i ich związek z automatami , Addison-Wesley,1969( ISBN 0-201-02983-9 , SUDOC 004772571 ).
Michael A. Harrison, Wprowadzenie do teorii języka formalnego , Addison-Wesley,1978, 594, str. ( ISBN 0-201-02955-3 , OCLC 266962302 ).
John E. Hopcroft, Rajeev Motwani i Jeffrey D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń , Pearson Addison Wesley,2007, 3 e ed. , xvii + 535 pkt. ( ISBN 978-0-321-45536-9 , 0201441241 i 0-321-45536-3 )
Olivier Carton , Języki formalne, obliczalność i złożoność , Paryż, Vuibert , wyd . "Vuibert sup maths",2014, 256 pkt. [ szczegóły wydania ] ( ISBN 978-2-311-01400-6 , prezentacja online )
Alexandru Mateescu i Arto Salomaa, „Aspects of Classical Language Theory” , w: G. Rozenberg i A. Salomaa (red.), Handbook of Formal Languages , vol. 1: Słowo, Język, Gramatyka , Springer,1997
Jean Berstel i Luc Boasson, „Context-Free Languages” , w: G. Rozenberg, A. Salomaa (red.), Handbook of Theoretical Computer Science , vol. B: Formal Models and Sematics , Elsevier and MIT Press,1990( ISBN 0-444-88074-7 ) , str. 59-102
(en) Philippe Flajolet, „ Modele analityczne i wieloznaczność języków bezkontekstowych ” , Teoret. Comput. Sci. , vol. 49,1987, s. 283-309