Prefix gramatica

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 decembrie 2014; verificările necesită 3 modificări .

În informatică, o gramatică de prefix este un tip de sistem de rescriere a șirurilor care constă dintr-un set de reguli de rescriere a șirurilor, similare gramaticilor formale. Ceea ce este caracteristic unei gramatici cu prefix nu este forma regulilor, ci modul în care sunt aplicate: doar prefixele sunt rescrise .

Definiție formală

Prefixul gramatical G este triplul (Σ, S , P ), unde

Pentru șirurile x , y , x → G y (a se citi: G derivă y din x într-un singur pas) este adevărată dacă există șiruri u, v, w astfel încât x = vu, y = wu și v → w aparține lui P . Rețineți că → G este o relație binară pe rândurile peste Σ.

Limbajul G , notat L(G) , este mulțimea de șiruri care pot fi derivate din S în zero sau mai mulți pași. Formal, aceasta este mulțimea de șiruri w astfel încât pentru unele s din S avem s R w , unde R este închiderea tranzitivă → G .

Exemplu

Prefix gramatica

descrie limbajul specificat de expresia regulată

Proprietăți

Gramaticile prefixelor descriu exact toate limbile obișnuite. [unu]

Link -uri

  1. M. Frazier și CD Page. Gramaticile prefixelor: O caracterizare alternativă a limbilor obișnuite. Information Processing Letters, 51(2):67–71, 1994.