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

Depi Wikipedya, ansiklopedi lib
Contenu supprimé Contenu ajouté
Graenmairyen (diskisyon | kontribisyon)
Baliz yo : Modifikasyon mobil Modifikasyon nan sitwèb mobil
Gilles2014 (diskisyon | kontribisyon)
Aucun résumé des modifications
Liy 1 : Liy 1 :
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.
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]]), ann [[teyori kalkilabilite]] a nan trètman lang natirèl (tou patikilyèman nan sa ki konsène mòfoloji e sentaks la).
Nosyon ki pou [[gramè]] a ki fòmèl la se patikilyèman itilize nan pwogramasyon lojik, [[konpilatè|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 ==
== 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 <math>A</math> se yon ansanm, nou note <math>A^*</math> [[Monoyid|monoyid lib]] sou <math>A</math>, setadi ansanm suit 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>.
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 swit 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è 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.
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 :
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 ;
* 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 ;
* 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.
* 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.
Liy 16 : Liy 16 :
== Gramè ==
== Gramè ==


Yon gramè fòmèl (oubyen, senpleman, gramè) gen antou kat (4) objè suivan:
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 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 miniskile yo,
* Yon ansanm fini ki 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 miniskil yo,
* Yon ansanm fini pou senbòl, rele yo ''[[Senbòl tèminal yo e non-tèminal yo|non-tèminal]]'', note konvansyonnèlman pa debann majiskil yo,
* Yon ansanm fini pou senbòl, rele yo ''[[Senbòl tèminal yo e non-tèminal yo|non-tèminal]]'', note konvansyonnèlman pa debann majiskil yo,
* Yon eleman pou ansanm non-tèminal yo, rele ''aksyom'', note konvansyonèlman <math>S</math>,
* Yon eleman pou ansanm non-tèminal yo, rele ''aksyò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 deyon suit ki poy tèminal yo e ki pou non-tèminal yo ; pa egzanp, <math>A \rightarrow ABa</math>
* 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, <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 aksyom an.
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 <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, aksyòm 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> (kote <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 –, swivi ki pou menm nonm de <math>b</math>) : <math>\{\varepsilon, ab, aabb, aaabbb,\ldots\}</math>.


== Yerachi Chomsky ==
== Yerachi Chomsky ==


==Analiz==
== Analiz ==


== Referans ==
== Referans ==

Vèsyon jou 24 me 2021 à 15:33

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 se yon ansanm, nou note monoyid lib sou , setadi ansanm swit 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, 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 ,
  • 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,

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 , non-terminal la, aksyòm 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 –, swivi ki pou menm nonm de ) : .

Yerachi Chomsky

Analiz

Referans

Lyen deyò