Deterministyczny język algebraiczny

W teoretycznej informatyki i teorii języka , o deterministyczny język algebraiczny jest język algebraiczne uznany (przez stany końcowe) przez deterministycznego automatu push-down . Interesem języków deterministycznych jest to, że ich analiza składniowa jest wykonywana w czasie liniowym w długości słowa, podczas gdy w każdym języku algebraicznym złożoność jest sześcienna, lub w każdym razie redukuje się do złożoności iloczynu macierzowego, dlatego jest w O ( n 2,37 ), gdzie n jest długością słowa według algorytmu Valianta . Każdy deterministyczny język algebraiczny można opisać za pomocą gramatyki LR (1) i odwrotnie. Pozwala to na wykorzystanie ich w praktycznych zastosowaniach. Zatem większość języków programowania to deterministyczne języki algebraiczne.

Przykłady

Język jest deterministyczny. ${\ Displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \}}$
Język , w którym znajduje się litera inna niż i gdzie jest powrót , jest deterministyczny. ${\ Displaystyle \ {wcw ^ {r} \ mid w \ in \ {a, b \} ^ {*} \}}$ $vs$ $a, b$ $w ^ r$ $w$

Nieruchomości

Klasa deterministycznych języków algebraicznych ściśle zawiera klasę języków wymiernych i jest ściśle zaliczana do klasy języków algebraicznych, a nawet jednoznacznych języków algebraicznych .

Typowym kontrprzykładem niedeterministycznego języka algebraicznego jest zbiór palindromów .

Klasę deterministycznych języków algebraicznych zamyka komplementarność. Jednak:

nie jest zamknięty przez przecięcie (ten sam kontrprzykład jak w przypadku niedeterministycznym);
nie jest zamknięty przez zjednoczenie (konsekwencja zamknięcia przez komplementarność i związek);
nie jest zamykany przez konkatenację;
nie jest zamknięty zwierciadłem, na przykład jest deterministyczną algebraiczną, ale nie . $\ {ca ^ {n} b ^ {n} \} \ cup \ {da ^ {{2n}} b ^ {n} \}$ $\ {b ^ {n} a ^ {n} c \} \ cup \ {b ^ {n} a ^ {{2n}} d \}$

Przykłady języków niedeterministycznych

Język nie jest deterministyczny. ${\ Displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \} \ cup \ {a ^ {n} b ^ {2n} \ mid n \ geq 0 \}}$
Język nie jest deterministyczny w przypadku alfabetu zawierającego co najmniej dwie litery. Ten język składa się ze słów, których druga połowa zawiera co najmniej jedno wystąpienie litery . ${\ displaystyle \ {w \ mid w = uv, | u | = | v |, | v | _ {a} \ geq 1 \}}$ $w$
Język palindromów nie jest deterministyczny.

Zasada konstrukcji tych języków jest taka sama: automat wypychający musi podjąć decyzję nie znając całości danych; w pierwszym przykładzie musi przewidzieć, czy liczba b jest równa lub podwójna liczba a , w drugim przykładzie musi sprawdzić obecność litery a w drugiej połowie, nie wiedząc, czy jest już w druga połowa.

Istnieje specjalny lemat iteracyjny dla deterministycznych języków algebraicznych, który umożliwia formalne udowodnienie, że język nie jest deterministyczny. Oświadczenie jest dość skomplikowane. Równie skomplikowany wariant tego lematu podaje Sheng Yu.

Uwagi i odniesienia

Wolper 2006 , sekcja 4.4.4, s. 97 .
Harrison 1978 , Twierdzenie 11.8.5.
Michael Harrison pokazuje nawet, że ten język nie jest związkiem skończonej liczby języków deterministycznych.
Harrison 1978 , Twierdzenie 11.8.3.

Bibliografia

(en) Michael A. Harrison , Wprowadzenie do teorii języka formalnego , Reading, Mass., Addison-Wesley ,1978, 594, str. ( ISBN 0-201-02955-3 , OCLC 266962302 )
Pierre Wolper , Wprowadzenie do obliczalności: kursy i poprawione ćwiczenia , Paryż, Dunod ,2006, 3 e ed. , 224 s. ( ISBN 2-10-049981-5 ).
Sheng Yu , „ Lemat o pompowaniu dla deterministycznych języków bezkontekstowych ”, Information Processing Letters , vol. 31, n o 1,1989, s. 47–51 ( DOI 10.1016 / 0020-0190 (89) 90108-7 )