Gramè fòmèl

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, konpilasyon (analiz sentaksik), nan teyori kalkilabilite a nan trètman lang natirèl (tou patikilyèman nan sa ki konsène mòfoloji e sentaks la).

Langaj yo

Yon langaj se yon ansanm mo, ki se senpleman sekans senbòl chwazi nan yon ansanm (anjeneral fini) rele alfabè. Fòmèlman, si $A$ se yon ansanm, nou note $A^{*}$ monoyid lib sou $A$, setadi ansanm swit fini yo pou eleman $A$, avèk operasyon an konkatenasyon pou de (2) mo. Yon langaj sou alfabè $A$ se pa definisyon yon sou-ansanm ki pou $A^{*}$.

Souvan, « senbòl yo », ke nou konsidere lè nou defini yon langaj pa yon gramè fòmèl, 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è yo 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.

Pa egzanp :

• A1 = { a, b, c, d, e } se yon alfabè ki genyen 5 senbòl, tradisyonèlman pòtnon lèt nan ka presi sa a ;
• A2 = { 2, 5, @, $, & } se yon lòt alfabè ki genyen 5 senbòl ;
• A3 = { Det, Adj, Vèb, Non, kowòd, Prep } se yon alfabè pou 6 senbòl ki ka dekri, pa egzanp, estrikti sentaksik nan yon fraz nan yon lang natirèl.

Gramè

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

• Yon ansanm fini ki se senbòl, rele senbòl tèminal (ki se yo k « lèt yo » pou langaj la), note konvansyonnèlman pa debann miniskil yo,
• Yon ansanm fini pou senbòl, rele yo non-tèminal, note konvansyonnèlman pa debann majiskil yo,
• Yon eleman pou ansanm non-tèminal yo, rele aksyòm, note konvansyonèlman $S$,
• Yon ansanm ki pou règ pou pwodiksyon, ki se yo k pa de (2) fòme yon non-tèminal e de yon swit ki pou tèminal yo e ki pou non-tèminal yo ; pa egzanp, $A\rightarrow ABa$

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 aksyòm an.

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

$S\to aSb$

$S\to \varepsilon$ (kote $\varepsilon$ reprezante mo a ki vid)

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

Lyen deyò

• (angle) en Konferans anyèl anlè gramè fòmèl