Prefiksna gramatika

U računarstvu, prefiksna gramatika je gramatika srodna formalnim gramatikama, u kojoj se nizovi znakova (stringovi) grade iz skupa baznih nizova znakova neprekidnom zamjenom prefiksa. Prefiksne gramatike opisuju točno sve regularne jezike.

Formalna definicija

Prefiksna gramatika G je uređena trojka Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\Sigma, S, P)} gdje je

• Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} konačna abeceda
• S konačan skup baznih nizova znakova nad abecedom Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma}
• P skup produkcija oblika $u\to v$, gdje su u i v nizovi znakova nad Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} .

Svaka produkcija $u\to v$ se može primjeniti samo na niz znakova oblika uw.

Primjer

Jednostavna prefiksna gramatika definirana na sljedeći način:

• Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma = \left\{ {0,1} \right\}}
• $S=\left\{{01,10}\right\}$
• Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = \left\{0 \to 010, 10 \to 100\right\}}

generira jezik definiran sljedećim regularnim izrazom:

$01(01)^{*}\cup 100^{*}$