Gramè fòmèl

Depi Wikipedya, ansiklopedi lib
Sauter à la navigation Sauter à la recherche

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

Langaj yo[edite | modifye sous]

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

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è yoitilize 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 potnon 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è[edite | modifye sous]

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

  • Yon ansanm fini kise senbòl, rele senbòl tèminal (ki se yo k « lèt yo » pou langaj la), note konvansyonnèlman pa debann miniskile 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 aksyom, note konvansyonèlman ,
  • Yon ansanm de règ pou pwodiksyon, ki se yo k pa de (2) fòme yon non-tèminal e deyon suit de tèminal yo e de non-tèminal yo ; pa egzanp,

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 de règ yo ki pou pwodiksyon yo rele yon derivasyon. Langaj defini pa yon gramè se ansanm mo yo ki fòme sèlman de senbòl tèminal yo ki kapab tou aten pa derivasyon ak pati de aksyom nan.

Konsa, gramè defini pa tèminal yo , non-terminal la, aksyom lan e de(2) règ yo ki pou pwodiksyon annapre a :

(kote reprezante mo a ki vid)

reprezante langaj tout mo yo pou lafòm (yon sèten nonm de – evantyèlman 0, ann vèti ki pou dezyèm règ la –, suivi ki pou menm nonm de ) : .

Yerachi Chomsky[edite | modifye sous]

Analiz[edite | modifye sous]

Referans[edite | modifye sous]

Lyen deyò[edite | modifye sous]