Gramè fòmèl: Diferans ant vèsyon yo

Yon gramè se yon fòmalis ki pèmèt pou defini yon [[sentaks]] e pou yon [[langaj fòmèl]], sa- vle- di yon ansanm mo yo ki admisib sou yon alfabè swadizan.

Nosyon ki pou [[gramè]] a ki fòmèl la se patikilyèman itilize nan pwogramasyon lojik, [[konpilatè|konpilasyon]] ([[analiz sentaksik]]), annnan [[teyori kalkilabilite]] a nan trètman lang natirèl (tou patikilyèman nan sa ki konsène [[mòfoloji]] e [[sentaks]] la).

Yon langaj se yon ansanm ''mo'', ki se senpleman sekans senbòl chwazi nan yon ansanm (anjeneral fini) rele ''alfabè''. Fòmèlman, si <math>A</math> se yon ansanm, nou note <math>A^*</math> [[Monoyid|monoyid lib]] sou <math>A</math>, setadi ansanm suitswit fini yo pou eleman <math>A</math>, avèk operasyon an [[konkatenasyon]] pou de (2) mo. Yon langaj sou alfabè <math>A</math> se pa definisyon yon sou-ansanm ki pou <math>A^*</math>.

Souvan, « senbòl yo », ke nou konsidere lè nou defini yon langaj pa yon gramè fòmèl la, se konstitye pa plizyè karaktè. Yo koresponn pito ak sa nou rele mo nan lang kourant. Nan menm fason an, « mo yo » langaj koresponn an pito ak fraz oubyen tèks. Lè gen anbigwite, nou pale de ''lèt'' oubyen de ''karaktè'' pou senbòl alfabè yoitilizeyo itilize pou kode enfòmasyon yo ; epi nou rezève mo senbòl la pou sa a yo ki nan alfabè abstrè, ki se eleman de baz pou langaj.

* A1 = { a, b, c, d, e } se yon alfabè ki genyen 5 senbòl, tradisyonèlman potnonpòtnon ''lèt'' nan ka presi sa a ;

Yon gramè fòmèl (oubyen, senpleman, gramè) gen antou kat (4) objè suivan :

* Yon ansanm fini kiseki se senbòl, rele ''[[Senbòl tèminal yo e non-tèminal yo|senbòl tèminal]]'' (ki se yo k « lèt yo » pou langaj la), note konvansyonnèlman pa debann miniskileminiskil yo,

* Yon eleman pou ansanm non-tèminal yo, rele ''aksyomaksyòm'', note konvansyonèlman <math>S</math>,

* Yon ansanm ki pou ''règ pou pwodiksyon'', ki se yo k pa de (2) fòme yon non-tèminal e deyonde suityon swit ki poypou tèminal yo e ki pou non-tèminal yo ; pa egzanp, <math>A \rightarrow ABa</math>

Aplike yon règ pou pwodiksyon konsanti ke w ranplase nan yon mo yon okirans pou manm bò goch ki pou règ sa a pa manm li an ki pou dwat ; aplikasyon siksesiv règ yo ki pou pwodiksyon yo rele yon derivasyon. Langaj defini pa yon gramè se ansanm mo yo ki fòme sèlman senbòl tèminal yo ki kapab tou atenn pa derivasyon ak pati ki pou aksyomaksyòm an.

Konsa, gramè defini pa tèminal yo <math>\{a, b\}</math>, non-terminal <math>S</math> la, aksyomaksyòm lan <math>S</math> e de(2) règ yo ki pou pwodiksyon annapre a :

: <math>S \to \varepsilon</math> (kote <math>\varepsilon</math> reprezante mo a ki vid)

reprezante langaj tout mo yo pou lafòm <math>a^n b^n</math> (yon sèten nonm de <math>a</math> – evantyèlman 0, ann vèti ki pou dezyèm règ la –, suiviswivi ki pou menm nonm de <math>b</math>) : <math>\{\varepsilon, ab, aabb, aaabbb,\ldots\}</math>.

== Analiz ==