Předponová gramatika
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. prosince 2014; kontroly vyžadují 3 úpravy .V informatice je gramatika prefixů typ systému přepisování řetězců sestávající ze sady pravidel přepisování řetězců, podobných formálním gramatikám. Pro gramatiku prefixů není charakteristická forma pravidel, ale způsob jejich použití: přepisují se pouze prefixy .
Formální definice
Předponová gramatika G je trojitá (Σ, S , P ), kde
- Σ je konečná abeceda
- S je konečná množina základních řad nad Σ
- P je množina odvozovacích pravidel ve tvaru u → v , kde u a v jsou řádky nad Σ
Pro řetězce x , y , x → G y (čti: G odvodí y z x v jednom kroku) platí , pokud existují řetězce u, v, w takové, že x = vu, y = wu a v → w patří do P . Všimněte si, že → G je binární relace na řádcích nad Σ.
Jazyk G , označovaný L(G) , je množina řetězců, které lze odvodit z S v žádném nebo více krocích. Formálně je to množina řetězců w taková, že pro některá s z S máme s R w , kde R je tranzitivní uzávěr → G .
Příklad
Předponová gramatika
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
popisuje jazyk určený regulárním výrazem
Vlastnosti
Prefixové gramatiky přesně popisují všechny regulární jazyky. [jeden]