Předpona gramatiky - Prefix grammar

v teoretická informatika a teorie formálního jazyka, a předpona gramatiky je typ systém přepisování řetězců, skládající se ze sady tětiva přepis pravidla a podobně jako a formální gramatika nebo a semi-Thue systém. U předponových gramatik není specifický tvar jejich pravidel, ale způsob jejich použití: pouze předpony jsou přepsány. Prefixové gramatiky popisují přesně všechny běžné jazyky.^[1]

Formální definice

Předpona gramatiky G je 3-n-tice, (Σ, S, P), kde

• Σ je konečná abeceda
• S je konečná sada základních řetězců nad Σ
• P je konečná sada výrobních pravidel formuláře u → proti kde u a proti jsou řetězce nad Σ

Pro smyčce X, y, píšeme X →_G y (a řekni: G může odvodit y z X v jednom kroku), pokud existují řetězce u, v, w takhle ${ displaystyle x = vu, y = wu}$, a proti → w je v P. Všimněte si, že →_G je binární relace na strunách Σ.

The Jazyk z G, označeno ${ displaystyle L (G)}$, je sada řetězců odvozitelných z S v nule nebo více krocích: formálně sada řetězců w takové, že pro některé s v S, s R w, kde R je přechodné uzavření z →_G.

Příklad

Předpona gramatiky

• Σ = {0, 1}
• S = {01, 10}
• P = {0 → 010, 10 → 100}

popisuje jazyk definovaný v regulární výraz

${ displaystyle 01 (01) ^ {*} šálek 100 ^ {*}}$

Viz také

• Pravidelná gramatika

Reference