Kontekstuaalinen kielioppi
Asiayhteyteen kielioppi on muodollinen kielioppi , jossa substituutiot ei-terminaalin symboli sovelletaan läsnä vasen konteksti ja oikeassa kontekstissa. Ne ovat yleisempiä kuin algebralliset kieliopit . Kontekstuaalisten kieliopien luomat muodolliset kielet ovat asiaankuuluvia kieliä . Ne tunnistetaan lineaarisesti rajoitetuilla automaateilla .
Noam Chomsky kuvasi asiayhteyteen liittyviä kielioppeja . Nämä ovat tyypin 1 kielioppeja Chomsky-hierarkiassa . Niitä voidaan käyttää kuvaamaan luonnollisten kielten syntaksia, jos näyttää siltä, että sana on sopiva tietyssä yhteydessä, mutta ei ole toisin.
Virallinen määritelmä
Muodollinen kielioppi , (jossa on joukko ei-terminaalin muuttujia tai symboleja , ja on pääte aakkoset tai joukko päätemerkkejä ) on kontekstuaalinen jos kaikki säännöt ovat muotoa
G=(V,AT,P,S){\ displaystyle G = (V, A, P, S)}
V{\ displaystyle V}
AT{\ displaystyle A}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
uXv→uxv{\ displaystyle uXv \ uxv}![{\ displaystyle uXv \ uxv}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c53e50aaac0254e153ef77c009f42459e5284cc)
missä , ja ovat kaikki sanat, joissa epätyhjä, ja on vaihteleva. Siten, korvaaminen mukaan tehdään läsnä ollessa "yhteydessä" .
u{\ displaystyle u}
v{\ displaystyle v}
x{\ displaystyle x}
x{\ displaystyle x}
X{\ displaystyle X}
X{\ displaystyle X}
x{\ displaystyle x}
(u,v){\ displaystyle (u, v)}![(u, v)](https://wikimedia.org/api/rest_v1/media/math/render/svg/eadf12294edccd7a29c99cfc1765e4a14bf47e58)
Vaihtoehto
Joskus sallimme säännön
S→e{\ displaystyle S \ to \ varepsilon}![S \ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb30bc1a4b59dcdeb095ecfaad991c8e3b0d26c8)
jossa merkitsee tyhjää sanaa edellyttäen, että sitä ei näy oikeanpuoleisessa säännön jäsenessä. Tämä tekninen käytäntö antaa mahdollisuuden pitää asiaankuuluvia kieliä algebrallisten kielten pääjoukkona tarvitsematta sanoa, että sisällytys rajoittuu kieliin, jotka eivät sisällä tyhjää sanaa.
e{\ displaystyle \ varepsilon}
S{\ displaystyle S}![S](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
Kasvava kielioppi
Kielioppi on kasvava tai yksitoikkoinen, jos minkä tahansa säännön pituus
on pienempi tai yhtä suuri kuin . Tiedämme kuinka muuntaa kasvava kielioppi kontekstuaaliseksi kieliopiksi (katso alla). Siksi lisääntyvien kieliopien tuottamat kielet ovat täsmälleen asiayhteyskieliä, jotka eivät sisällä tyhjää sanaa.
a→β{\ displaystyle \ alpha \ to \ beta}
a{\ displaystyle \ alfa}
β{\ displaystyle \ beta}![\beeta](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed48a5e36207156fb792fa79d29925d2f7901e8)
Kielioppi on Kurodan normaalissa muodossa, jos säännöt ovat jossakin seuraavista muodoista:
XY→ZT{\ displaystyle XY \ - ZT}
X→ZT{\ displaystyle X \ - ZT}
X→Y{\ displaystyle X \ - Y}
X→klo{\ displaystyle X \ a}}
missä ovat muuttujat ja on päätekirjain. Kurodan normaalimuotoiset kieliopit kasvavat. Vastaavasti tiedämme kuinka muuntaa kasvava kielioppi kieliopiksi normaalissa Kuroda-muodossa. Siksi nämä kieliopit luovat täsmälleen kontekstikielet, jotka eivät sisällä tyhjää sanaa. Ne on nimetty Sige-Yuki Kurodan mukaan .
X,Y,Z,T{\ displaystyle X, Y, Z, T}
klo{\ displaystyle a}![klo](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
Esimerkkejä
- Seuraava kielioppi luo ei- algebrallisen kielen :{kloeibeivs.ei|ei≥1}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} | n \ geq 1 \}}
![{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} | n \ geq 1 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17176613d33e9b9221461ec9f666ac6276401a2d)
- S→kloSBVS{\ displaystyle S \ aSBC}
![{\ displaystyle S \ aSBC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69a64ff879d59f8b274ab996ac600eb8965a28d2)
- S→kloBVS{\ displaystyle S \ aBC}
![{\ displaystyle S \ aBC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a205f7891d9e7ebba4ab6efe84a39892808b0f5)
- VSB→HB{\ displaystyle CB \ - HB}
![{\ displaystyle CB \ - HB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18652317c2eb9a46cf746a63cd70bcbb51f3d0cb)
- HB→HVS{\ displaystyle HB \ - HC}
![{\ displaystyle HB \ - HC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4032d8342e42c7619c23528860931418905d34cf)
- HVS→BVS{\ displaystyle HC \ - BC}
![{\ displaystyle HC \ - BC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24b13e84d837b9a2390f9bbaf784cb1f5115fa41)
- kloB→klob{\ displaystyle aB \ to ab}
![{\ displaystyle aB \ to ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eadc7327a7b7cda2be0e5833fcdd9766125198b9)
- bB→bb{\ displaystyle bB \ - bb}
![{\ displaystyle bB \ - bb}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf3ca6ae444e64991e3cf151abd8dacb53a38f)
- bVS→bvs.{\ displaystyle bC \ - bc}
![{\ displaystyle bC \ - bc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae0b6c3bc3be4e54ab904bed09b935644e2fb5fc)
- vs.VS→vs.vs.{\ displaystyle cC \ - cc}
![{\ displaystyle cC \ - cc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501a156633feea0d3da1a79cdcfeb85c4842bfed)
Kahta ensimmäistä sääntöä käytetään sanojen luomiseen . Seuraavien kolmen säännön avulla voit korvata sen . Johdanto mallille on seuraava:
kloei(BVS)ei{\ displaystyle a ^ {n} (BC) ^ {n}}
VSB{\ displaystyle CB}
BVS{\ displaystyle BC}
klokloklobbbvs.vs.vs.{\ displaystyle aaabbbccc}![{\ displaystyle aaabbbccc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ec095ab16679aac56c29373186f0bd2344d5659)
S⇒1kloSBVS⇒1klokloSBVSBVS⇒2kloklokloBVSBVSBVS⇒3kloklokloBHBVSBVS⇒4kloklokloBHVSVSBVS⇒5kloklokloBBVSVSBVS⇒3kloklokloBBVSHBVS⇒4kloklokloBBVSHVSVS⇒5kloklokloBBVSBVSVS⇒3kloklokloBBHBVSVS⇒4kloklokloBBHVSVSVS⇒5kloklokloBBBVSVSVS⇒6klokloklobBBVSVSVS⇒7klokloklobbBVSVSVS⇒7klokloklobbbVSVSVS⇒8klokloklobbbvs.VSVS⇒9klokloklobbbvs.vs.VS⇒9klokloklobbbvs.vs.vs.{\ displaystyle {\ begin {aligned} S & \ Rightarrow _ {1} aSBC \ Rightarrow _ {1} a {\ boldsymbol {aSBC}} BC \ Rightarrow _ {2} aa {\ boldsymbol {aBC}} BCBC \\ & \ Rightarrow _ {3} aaaB {\ boldsymbol {HB}} CBC \ Rightarrow _ {4} aaaB {\ boldsymbol {HC}} CBC \ Rightarrow _ {5} aaaB {\ boldsymbol {BC}} CBC \\ & \ Rightarrow _ {3} aaaBBC {\ boldsymbol {HB}} C \ Rightarrow _ {4} aaaBBC {\ boldsymbol {HC}} C \ Rightarrow _ {5} aaaBBC {\ boldsymbol {BC}} C \\ & \ Rightarrow _ {3} aaaBB {\ boldsymbol {HB}} CC \ Rightarrow _ {4} aaaBB {\ boldsymbol {HC}} CC \ Rightarrow _ {5} aaaBB {\ boldsymbol {BC}} CC \\ & \ Rightarrow _ {6 } aa {\ boldsymbol {ab}} BBCCC \ Rightarrow _ {7} aaa {\ boldsymbol {bb}} BCCC \ Rightarrow _ {7} aaab {\ boldsymbol {bb}} CCC \\ & \ Rightarrow _ {8} aaabb {\ boldsymbol {bc}} CC \ Rightarrow _ {9} aaabbb {\ boldsymbol {cc}} C \ Rightarrow _ {9} aaabbbc {\ boldsymbol {cc}} \ end {kohdistettu}}}![{\ displaystyle {\ begin {aligned} S & \ Rightarrow _ {1} aSBC \ Rightarrow _ {1} a {\ boldsymbol {aSBC}} BC \ Rightarrow _ {2} aa {\ boldsymbol {aBC}} BCBC \\ & \ Rightarrow _ {3} aaaB {\ boldsymbol {HB}} CBC \ Rightarrow _ {4} aaaB {\ boldsymbol {HC}} CBC \ Rightarrow _ {5} aaaB {\ boldsymbol {BC}} CBC \\ & \ Rightarrow _ {3} aaaBBC {\ boldsymbol {HB}} C \ Rightarrow _ {4} aaaBBC {\ boldsymbol {HC}} C \ Rightarrow _ {5} aaaBBC {\ boldsymbol {BC}} C \\ & \ Rightarrow _ {3} aaaBB {\ boldsymbol {HB}} CC \ Rightarrow _ {4} aaaBB {\ boldsymbol {HC}} CC \ Rightarrow _ {5} aaaBB {\ boldsymbol {BC}} CC \\ & \ Rightarrow _ {6 } aa {\ boldsymbol {ab}} BBCCC \ Rightarrow _ {7} aaa {\ boldsymbol {bb}} BCCC \ Rightarrow _ {7} aaab {\ boldsymbol {bb}} CCC \\ & \ Rightarrow _ {8} aaabb {\ boldsymbol {bc}} CC \ Rightarrow _ {9} aaabbb {\ boldsymbol {cc}} C \ Rightarrow _ {9} aaabbbc {\ boldsymbol {cc}} \ end {kohdistettu}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c486b715f6792266c4ab9e743c81c54293acfd62)
Sama kieli voidaan luoda seuraavalla kasvavalla kieliopilla:
- S→klobvs.{\ displaystyle S \ abc}
![{\ displaystyle S \ abc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/937b9b30351913a0ddef674c850276ec59213761)
- S→kloSBvs.{\ displaystyle S \ aSBc}
![{\ displaystyle S \ aSBc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e2ac1a46d28e12fb4bdf5629ba3f1465ece1a5a)
- vs.B→Bvs.{\ displaystyle cB \ - Bc}
![{\ displaystyle cB \ - Bc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ead4cecb3c46ca51ded677cd567766c87db4134b)
- bB→bb{\ displaystyle bB \ - bb}
![{\ displaystyle bB \ - bb}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf3ca6ae444e64991e3cf151abd8dacb53a38f)
- Seuraava kasvava kielioppi tuottaa neliöiden ei- algebrallisen kielen :VS={xx|x∈{klo,b}+}{\ displaystyle C = \ {xx | x \ sisään \ {a, b \} ^ {+} \}}
![{\ displaystyle C = \ {xx | x \ sisään \ {a, b \} ^ {+} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00be151590ac6d697710728490a0a748891c6b7a)
- S→kloATS|bBS|kloAT¯|bB¯{\ displaystyle S \ oikeanpuoleinen aAS | bBS | a {\ bar {A}} | b {\ bar {B}}}
![{\ displaystyle S \ oikeanpuoleinen aAS | bBS | a {\ bar {A}} | b {\ bar {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd05271adf8473e1b0caf7fd42bcfa28444579e4)
- ATklo→kloAT{\ displaystyle Aa \ oikeanpuoleinen aA}
![{\ displaystyle Aa \ oikeanpuoleinen aA}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4534a68fb883274672c9248aee39fe03c5a8f28a)
- Bklo→kloB{\ displaystyle Ba \ oikeanpuoleinen aB}
![{\ displaystyle Ba \ oikeanpuoleinen aB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b607dd6709730c32a1245dafb71f48fbcab2936)
- ATb→bAT{\ displaystyle Ab \ oikeanpuoleinen bA}
![{\ displaystyle Ab \ oikeanpuoleinen bA}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e3dc5d161ae53f522f7ad1542bcbf28234fd8d8)
- Bb→bB{\ displaystyle Bb \ oikeanpuoleinen bB}
![{\ displaystyle Bb \ oikeanpuoleinen bB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba18fbb2d8ede24791fbe0a8b67982eb6df5c89)
- ATAT¯→AT¯klo{\ displaystyle A {\ bar {A}} \ rightarrow {\ bar {A}} a}
![{\ displaystyle A {\ bar {A}} \ rightarrow {\ bar {A}} a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1084ea784ef6b08098a0de7535125eafe61e758)
- BAT¯→B¯klo{\ displaystyle B {\ bar {A}} \ rightarrow {\ bar {B}} a}
![{\ displaystyle B {\ bar {A}} \ rightarrow {\ bar {B}} a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2f35ceb7109f5c81625919e24c4b16160f8a860)
- ATB¯→AT¯b{\ displaystyle A {\ bar {B}} \ rightarrow {\ bar {A}} b}
![{\ displaystyle A {\ bar {B}} \ rightarrow {\ bar {A}} b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11b1ea9894c9b1d8cf0e180fc00833993edddf46)
- BB¯→B¯b{\ displaystyle B {\ bar {B}} \ rightarrow {\ bar {B}} b}
![{\ displaystyle B {\ bar {B}} \ rightarrow {\ bar {B}} b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d434041757197c3d58a4a079dec2efa5009b0617)
- kloAT¯→kloklo{\ displaystyle a {\ palkki {A}} \ rightarrow aa}
![{\ displaystyle a {\ palkki {A}} \ rightarrow aa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/023b4e19f54949f661e72fad93776fa36735f4db)
- bAT¯→bklo{\ displaystyle b {\ bar {A}} \ rightarrow ba}
![{\ displaystyle b {\ bar {A}} \ rightarrow ba}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28a9be6bff65733767d4ce7ad5db1696993ae030)
- kloB¯→klob{\ displaystyle a {\ bar {B}} \ rightarrow ab}
![{\ displaystyle a {\ bar {B}} \ rightarrow ab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8830bfbabe593617251a3d011cca90662ea9b43)
- bB¯→bb{\ displaystyle b {\ bar {B}} \ rightarrow bb}
![{\ displaystyle b {\ bar {B}} \ rightarrow bb}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db8dfdbc72bc568a3669d93af344cf96a59456f8)
Johtaminen abaaba on seuraava:
S⇒1kloATS⇒1kloATbBS⇒1kloATbBkloAT¯⇒4klobATBkloAT¯⇒3klobATkloBAT¯⇒2klobkloATBAT¯⇒7klobkloATB¯klo⇒8klobkloAT¯bklo⇒10klobkloklobklo{\ displaystyle {\ begin {aligned} S & \ Rightarrow _ {1} aAS \ Rightarrow _ {1} aAbBS \ Rightarrow _ {1} aAbBa {\ bar {A}} \\ & \ Rightarrow _ {4} abABa { \ bar {A}} \ Rightarrow _ {3} abAaB {\ bar {A}} \ Rightarrow _ {2} abaAB {\ bar {A}} \\ & \ Rightarrow _ {7} abaA {\ bar {B} } a \ Rightarrow _ {8} aba {\ bar {A}} ba \ Rightarrow _ {10} abaaba \ end {tasattu}}}![{\ displaystyle {\ begin {aligned} S & \ Rightarrow _ {1} aAS \ Rightarrow _ {1} aAbBS \ Rightarrow _ {1} aAbBa {\ bar {A}} \\ & \ Rightarrow _ {4} abABa { \ bar {A}} \ Rightarrow _ {3} abAaB {\ bar {A}} \ Rightarrow _ {2} abaAB {\ bar {A}} \\ & \ Rightarrow _ {7} abaA {\ bar {B} } a \ Rightarrow _ {8} aba {\ bar {A}} ba \ Rightarrow _ {10} abaaba \ end {tasattu}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68ae7e97af1dab2d8c886323a5f531291daf4166)
Kasvavat kieliopit ja asiayhteyteen liittyvät kieliopit
Näin voimme muuntaa kasvavan kieliopin kontekstuaaliseksi kieliopiksi. Vaikka se tarkoittaisi uusien lomakkeen sääntöjen , joissa on kirjain, käyttöönottoa, voimme olettaa, että kaikki lomakkeen säännöt
X→klo{\ displaystyle X \ a}}
klo{\ displaystyle a}![klo](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
X1X2⋯Xei→Y1Y2⋯Ym{\ displaystyle X_ {1} X_ {2} \ cdots X_ {n} \ - Y_ {1} Y_ {2} \ cdots Y_ {m}}![{\ displaystyle X_ {1} X_ {2} \ cdots X_ {n} \ - Y_ {1} Y_ {2} \ cdots Y_ {m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24127bd6f93326866a74d31face045483729417f)
missä ja kaikki symbolit ovat muuttujia. Korvataan tällainen sääntö seuraavalla joukolla:
m≥ei≥1{\ displaystyle m \ geq n \ geq 1}![{\ displaystyle m \ geq n \ geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de7a47710ea1d9bb3c4688bd7bd4bbf5f1d3001f)
X1X2⋯Xei→Z1X2⋯XeiZ1X2⋯Xei→Z1Z2⋯Xei⋯Z1Z2⋯Zei-1Xei→Z1Z2⋯Zei-1YeiYei+1⋯YmZ1Z2⋯Zei-1YeiYei+1⋯Ym→Z1Z2⋯Zei-2Yei-1YeiYei+1⋯Ym⋯Z1Z2Y3⋯Ym→Z1Y2Y3⋯YmZ1Y2⋯Ym→Y1Y2⋯Ym.{\ displaystyle {\ begin {kohdistettu} X_ {1} X_ {2} \ cdots X_ {n} & \ - Z_ {1} X_ {2} \ cdots X_ {n} \\ Z_ {1} X_ {2} \ cdots X_ {n} & \ - Z_ {1} Z_ {2} \ cdots X_ {n} \\ & \ cdots \\ Z_ {1} Z_ {2} \ cdots Z_ {n-1} X_ {n} & \ - Z_ {1} Z_ {2} \ cdots Z_ {n-1} Y_ {n} Y_ {n + 1} \ cdots Y_ {m} \\ Z_ {1} Z_ {2} \ cdots Z_ {n -1} Y_ {n} Y_ {n + 1} \ cdots Y_ {m} & \ - Z_ {1} Z_ {2} \ cdots Z_ {n-2} Y_ {n-1} Y_ {n} Y_ { n + 1} \ cdots Y_ {m} \\ & \ cdots \\ Z_ {1} Z_ {2} Y_ {3} \ cdots Y_ {m} & \ - Z_ {1} Y_ {2} Y_ {3} \ cdots Y_ {m} \\ Z_ {1} Y_ {2} \ cdots Y_ {m} & \ to Y_ {1} Y_ {2} \ cdots Y_ {m} \ ,. \ end {aligned}}}![{\ displaystyle {\ begin {kohdistettu} X_ {1} X_ {2} \ cdots X_ {n} & \ - Z_ {1} X_ {2} \ cdots X_ {n} \\ Z_ {1} X_ {2} \ cdots X_ {n} & \ - Z_ {1} Z_ {2} \ cdots X_ {n} \\ & \ cdots \\ Z_ {1} Z_ {2} \ cdots Z_ {n-1} X_ {n} & \ - Z_ {1} Z_ {2} \ cdots Z_ {n-1} Y_ {n} Y_ {n + 1} \ cdots Y_ {m} \\ Z_ {1} Z_ {2} \ cdots Z_ {n -1} Y_ {n} Y_ {n + 1} \ cdots Y_ {m} & \ - Z_ {1} Z_ {2} \ cdots Z_ {n-2} Y_ {n-1} Y_ {n} Y_ { n + 1} \ cdots Y_ {m} \\ & \ cdots \\ Z_ {1} Z_ {2} Y_ {3} \ cdots Y_ {m} & \ - Z_ {1} Y_ {2} Y_ {3} \ cdots Y_ {m} \\ Z_ {1} Y_ {2} \ cdots Y_ {m} & \ to Y_ {1} Y_ {2} \ cdots Y_ {m} \ ,. \ end {aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c05f76984ff3d6ad5c0a7e0ed814d669e0cbe62)
Esimerkiksi seuraava sääntö:
X1X2X3→Y1Y2Y3Y4Y5{\ displaystyle X_ {1} X_ {2} X_ {3} \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5}}![{\ displaystyle X_ {1} X_ {2} X_ {3} \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2b91c660b8e700cf4cd8850e59e7a633a609b10)
muuttuu
X1X2X3→Z1X2X3Z1X2X3→Z1Z2X3Z1Z2X3→Z1Z2Y3Y4Y5Z1Z2Y3Y4Y5→Z1Y2Y3Y4Y5Z1Y2Y3Y4Y5→Y1Y2Y3Y4Y5{\ displaystyle {\ begin {kohdistettu} X_ {1} X_ {2} X_ {3} ja \ kohtaan Z_ {1} X_ {2} X_ {3} \\ Z_ {1} X_ {2} X_ {3} & \ - Z_ {1} Z_ {2} X_ {3} \\ Z_ {1} Z_ {2} X_ {3} & \ - Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ { 5} \\ Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ {5} & \ - Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \\ Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} ja \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \ loppu {tasattu}}}![{\ displaystyle {\ begin {kohdistettu} X_ {1} X_ {2} X_ {3} ja \ kohtaan Z_ {1} X_ {2} X_ {3} \\ Z_ {1} X_ {2} X_ {3} & \ - Z_ {1} Z_ {2} X_ {3} \\ Z_ {1} Z_ {2} X_ {3} & \ - Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ { 5} \\ Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ {5} & \ - Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \\ Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} ja \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \ loppu {tasattu}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c23610e5d0d137fc7611f649f84d2289d6bbb3)
Päätöskysymykset
Sovellukset
On todettu, että luonnollisia kieliä voidaan yleensä kuvata asiayhteyteen liittyvillä kieliopilla. Kontekstuaalisten kielten luokka on kuitenkin paljon suurempi kuin luonnollisten kielten luokka. Lisäksi koska PSPACE : n päätösongelma on täydellinen , tätä kuvausta ei voida käyttää käytännössä. Siksi kieli suunnattiin spesifisempien kieliopimallien, kuten kombinatoristen kategoristen kieliopien (in) vieressä olevan kieliopin , tai muiden järjestelmien kehittämiseen. Näiden kieliopien tuottamat kielet ovat hieman kontekstuaalisia (en) ja kuuluvat tiukasti algebrallisten kielten ja asiaankuuluvien kielten välillä.
Huomautuksia
-
(sisään) Noam Chomsky , " Kolme mallia kielen kuvaukselle " , IRE Transaction on Information Theory , n o 21956, s. 113–124 ( lue verkossa )
-
Laatikko 2008 , s. 144-145
-
(in) Michael R. Garey ja David S. Johnson , Tietokoneet ja intractability: Opas teoria NP-täydellisyys , New York, WH Freeman,
1983, 338 Sivumäärä ( ISBN 0-7167-1045-5 ) - Ongelma AL3, ”Lineaarisesti rajoitettu automaatin hyväksyntä”, sivu 265.
-
John E.Hopcroft ja Jeffrey D.Ullman, Muodolliset kielet ja niiden suhde automaatteihin , Addison-Wesley,1969( ISBN 0-201-02983-9 , SUDOC 004772571 ) - Osa 14.7 sivut 230-23.
-
Katso esimerkiksi Salomon Marcus , ”Kontekstuaaliset kieliopit ja luonnolliset kielet” , julkaisussa Grzegorz Rozenberg ja Arto Salomaa (toim.), Handbook of Formal Languages , voi. 2: Lineaarinen mallinnus: Tausta ja sovellus , Springer Science & Business Media,1997, 528 Sivumäärä ( ISBN 9783540606482 ) , luku. 5, s. 215-236.
Viitteet
- Olivier Carton , Muodolliset kielet, laskettavuus ja monimutkaisuus ,2008[ yksityiskohdat painoksesta ] ( lue verkossa )
- Michael Sipser , Johdatus laskentateoriaan , PWS Publishing Company,1996, 239 Sivumäärä ( ISBN 0-534-95250-X )
- Pierre Wolper , Johdatus laskettavuuteen: kurssit ja korjatut harjoitukset , Pariisi, Dunod,2006, 3 ja toim. , 224 Sivumäärä ( ISBN 2-10-049981-5 )
Käännöslähde
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">