System półthueowski

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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ą R \subseteq A^{*} \times A^* , gdzie A^* 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 w \rightarrow v jest regułą, to v \rightarrow w też), nazywany jest systemem Thuego.