System półthueowski

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

System półthueowski to system przepisywania słów zbliżony do gramatyk typu 0. Jedyna różnica polega na tym, że w systemach półthueowskich nie ma podziału na symbole terminalne i nieterminalne ani wyróżnionego symbolu początkowego. Formalnie, system półthueowski S nad alfabetem A jest relacją , gdzie oznacza zbiór wszystkich słów nad alfabetem A (domknięcie Kleenego).

System półthueowski, w którym wszystkie reguły są odwracalne (tj. jeśli jest regułą, to też), nazywany jest systemem Thuego.