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

Depi Wikipedya, ansiklopedi lib
Contenu supprimé Contenu ajouté
Hat2004 (diskisyon | kontribisyon)
Baliz yo : Modifikasyon mobil Modifikasyon nan sitwèb mobil
Hat2004 (diskisyon | kontribisyon)
Baliz yo : Modifikasyon mobil Modifikasyon nan sitwèb mobil
Liy 26 : Liy 26 :
Konsa, gramè defini pa tèminal yo <math>\{a, b\}</math>, non-terminal <math>S</math> la, aksyom lan <math>S</math> e de(2) règ yo ki pou pwodiksyon annapre a :
Konsa, gramè defini pa tèminal yo <math>\{a, b\}</math>, non-terminal <math>S</math> la, aksyom lan <math>S</math> e de(2) règ yo ki pou pwodiksyon annapre a :
: <math>S \to aSb</math>
: <math>S \to aSb</math>
: <math>S \to \varepsilon</math> ( <math>\varepsilon</math> reprezante mo a ki vid)
: <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 –, suivi ki pou menm nonm de <math>b</math>) : <math>\{\varepsilon, ab, aabb, aaabbb,\ldots\}</math>.
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 –, suivi ki pou menm nonm de <math>b</math>) : <math>\{\varepsilon, ab, aabb, aaabbb,\ldots\}</math>.

Vèsyon jou 8 avril 2019 à 17:28

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

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è

Yon gramè fòmèl (oubyen, senpleman, gramè) se lik gen antou kat 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 konvansyonnèlman ,
  • Yon ansanm de règ pou pwodiksyon, ki se yo k pade(2) fòme yon non-tèminal e deyon suit de tèminal yo e de non-tèminal yo ; pa ekszanp,

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 inikman 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 ) : .

Referans

Lyen deyò