System postkanoniczny

System postkanoniczny , znany również jako system postprodukcyjny , stworzony przez Emila Posta , to system manipulacji ciągami, który zaczyna się od skończonej liczby ciągów i wielokrotnie je przekształca, stosując skończony zestaw j określonych reguł o określonej formie, tworząc w ten sposób język formalny . Dziś mają one głównie znaczenie historyczne, ponieważ każdy postkanoniczny system można zredukować do systemu przepisywania ciągów (system semi-Thue), który jest prostszym sformułowaniem. Oba formalizmy są Turinga kompletne .

Definicja

Postkanoniczny system to trójka ( A , I , R ), gdzie

• A jest skończonym alfabetem, a skończone (prawdopodobnie puste) ciągi na A nazywane są słowami .
• I jest skończonym zbiorem początkowych słów .
• R jest skończonym zbiorem reguł przekształcających struny (zwanych regułami produkcji ), z których każda ma następującą postać:

${\ Displaystyle {\ overset {\ rozpocząć {macierz} g_ {10} & \ $_ {11} i g_ {11} & \ $ _ {12} i g_ {12} i \ kropki & \ $ _ {1m_ {1} }&g_{1m_{1}}\\g_{20}&\$_{21}&g_{21}&\$_{22}&g_{22}&\kropki &\$_{2m_{2}}&g_ {2m_{2}}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\g_{k0}&\$_{k1}&g_{k1}&\ $_{k2}&g_{k2}&\dots &\$_{km_{k}}&g_{km_{k}}\\\end{matrix}}{\underset {\begin{matrix}h_{0} &\$'_{1}&h_{1}&\$'_{2}&h_{2}&\kropki &\$'_{n}&h_{n}\\\end{macierz}}{\strzałka w dół }}}}$

gdzie każde g i h jest określonym stałym słowem, a każdy $ i $' jest zmienną oznaczającą dowolne słowo. Ciągi przed i za strzałką w regule produkcyjnej nazywane są odpowiednio poprzednikami i następnikami reguły . Wymagane jest, aby każdy $' w następniku był jednym z $ s w poprzednikach tej reguły i aby każdy poprzednik i następnik zawierały co najmniej jedną zmienną.

W wielu kontekstach każda reguła produkcji ma tylko jeden poprzednik, przybierając tym samym prostszą formę

${\ Displaystyle g_ {0} \ \ $ _ {1} \ g_ {$

Język formalny generowany przez system postkanoniczny to zbiór, którego elementami są słowa początkowe wraz ze wszystkimi słowami, które można z nich uzyskać poprzez wielokrotne zastosowanie reguł produkcji. Takie zbiory są przeliczalnymi rekurencyjnie , a każdy język przeliczalny rekurencyjnie jest ograniczeniem jakiegoś takiego zbioru do alfabetu podrzędnego A .

Przykład (dobrze uformowane wyrażenia w nawiasach)

 Alfabet: {[, ]} Początkowe słowo: [] Reguły produkcji: (1)  $  → [  $  ] (2)  $  →  $$  (3)  $  1  $  2  →  $  1  []  $  2  Wyprowadzenie kilku słów w język dobrze sformułowanych wyrażeń w nawiasach: [] początkowe słowo [][] przez (2) [[][]] przez (1) [[][]][[][]] przez (2) [[] []][][[][]] przez (3) ... 

Twierdzenie o postaci normalnej

O systemie postkanonicznym mówi się, że jest w postaci normalnej , jeśli ma tylko jedno słowo początkowe, a każda reguła produkcji ma postać prostą

${\ Displaystyle g \ $ \ \ rightarrow \ \ $ h}$

Po roku 1943 udowodniono niezwykłe twierdzenie o postaci normalnej , które ma zastosowanie do najbardziej ogólnego typu systemu postkanonicznego:

Biorąc pod uwagę dowolny system postkanoniczny na alfabecie A , można z niego zbudować system postkanoniczny w postaci normalnej , prawdopodobnie powiększając alfabet, tak że zestaw słów obejmujący tylko litery A , które są generowane przez system w postaci normalnej, jest dokładnie zestaw słów wygenerowany przez oryginalny system.

Systemy znaczników , które obejmują uniwersalny model obliczeniowy, są godnymi uwagi przykładami systemu postnormalnego, który jest również monogeniczny . (Mówi się, że system kanoniczny jest monogeniczny , jeśli z dowolnej struny można w jednym kroku utworzyć co najwyżej jedną nową strunę — tj. system jest deterministyczny).

Systemy przepisywania ciągów znaków, gramatyki formalne typu 0

System przepisywania ciągów znaków to specjalny rodzaj postkanonicznego systemu z pojedynczym początkowym słowem, a produkcje mają formę

${\ Displaystyle P_ {1} gP_ {2} \ \ rightarrow \ P_ {1} hP_ {2}}$

Oznacza to, że każda reguła produkcji jest prostą regułą podstawienia, często zapisaną w postaci g → h . Udowodniono, że każdy system postkanoniczny jest redukowalny do takiego systemu podstawieniowego , który jako gramatyka formalna jest również nazywany gramatyką struktury frazowej lub gramatyką typu 0 w hierarchii Chomsky'ego .

• Emil Post , „Formalne redukcje ogólnego problemu decyzyjnego kombinatorycznego”, American Journal of Mathematics 65 (2): 197-215, 1943.
• Marvin Minsky , Obliczenia: maszyny skończone i nieskończone , Prentice-Hall, Inc., NJ, 1967.