Kontextus szerinti nyelvtan
A kontextus szerinti nyelvtan egy formális nyelvtan , amelyben egy nem terminális szimbólum helyettesítése egy bal és egy jobb kontextus jelenlétének függvénye. Általánosabbak, mint az algebrai nyelvtanok . A kontextus szerinti nyelvtanok által generált formális nyelvek kontextuális nyelvek . Lineárisan kötött automaták ismerik fel őket .
A kontextuális nyelvtanokat Noam Chomsky írta le . Ezek a Chomsky-hierarchia 1. típusú nyelvtanai . Használhatók a természetes nyelvek szintaxisának leírására, ahol úgy tűnik, hogy egy szó megfelelő egy bizonyos összefüggésben, de nem más.
Formális meghatározás
A formális nyelvtan (ahol a nem terminális változók vagy szimbólumok halmaza, és a terminál ábécé vagy a terminál szimbólumok halmaza ) kontextusban van, ha az összes szabály formája
G=(V,NÁL NÉL,P,S){\ displaystyle G = (V, A, P, S)}
V{\ displaystyle V}
NÁL NÉL{\ displaystyle A}
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
uxv→uxv{\ displaystyle uXv \ to uxv}![{\ displaystyle uXv \ to uxv}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c53e50aaac0254e153ef77c009f42459e5284cc)
ahol , és bármilyen szóval, nem üres, és egy változó. Így, a csere a által történik a jelenléte a „kontextus” .
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)
Változat
Néha megengedjük a szabályt
S→ε{\ displaystyle S \ to \ varepsilon}![S \ to \ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb30bc1a4b59dcdeb095ecfaad991c8e3b0d26c8)
ahol az üres szót jelöli, feltéve, hogy ez nem jelenik meg a jobb oldali szabálytagban. Ez a technikai konvenció lehetővé teszi a kontextus nyelvének az algebrai nyelvek halmazának tekintését anélkül, hogy meg kellene határoznia, hogy a beillesztés olyan nyelvekre korlátozódik, amelyek nem tartalmazzák az üres szót.
ε{\ displaystyle \ varepsilon}
S{\ displaystyle S}![S](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
Növekvő nyelvtan
A nyelvtan növekszik vagy monoton, ha bármely szabály esetében a hossza
kisebb vagy egyenlő a hosszával . Tudjuk, hogyan lehet az egyre növekvő nyelvtant kontextus szerinti nyelvté alakítani (lásd alább). Ezért a növekvő nyelvtanok által generált nyelvek pontosan azok a kontextuális nyelvek, amelyek nem tartalmazzák az üres szót.
α→β{\ displaystyle \ alpha \ to \ beta}
α{\ displaystyle \ alpha}
β{\ displaystyle \ beta}![\ béta](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed48a5e36207156fb792fa79d29925d2f7901e8)
A nyelvtan Kuroda normális formájában van, ha a szabályok az alábbi formák egyikét alkotják:
xY→ZT{\ displaystyle XY \ - ZT}
x→ZT{\ displaystyle X \ - ZT}
x→Y{\ displaystyle X \ - Y}
x→nál nél{\ displaystyle X \ to a}
hol vannak változók, és ez egy végtag. A Kuroda normál formájú nyelvtanai növekszenek. Ezzel szemben tudjuk, hogyan lehet az egyre növekvő nyelvtant normál Kuroda formában átalakítani nyelvtanná. Ezért ezek a nyelvtanok pontosan olyan kontextus nyelveket generálnak, amelyek nem tartalmazzák az üres szót. Nevüket Sige-Yuki Kurodáról kapták .
x,Y,Z,T{\ displaystyle X, Y, Z, T}
nál nél{\ displaystyle a}![nál nél](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
Példák
- A következő nyelvtan generálja a nem algebrai nyelvet :{nál nélnembnemvs.nem|nem≥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→nál nélSBVS{\ displaystyle S \ aSBC-hez}
![{\ displaystyle S \ aSBC-hez}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69a64ff879d59f8b274ab996ac600eb8965a28d2)
- S→nál nélBVS{\ displaystyle S \ aBC-hez}
![{\ displaystyle S \ aBC-hez}](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 \ to HC}
![{\ displaystyle HB \ to 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)
- nál nélB→nál nélb{\ displaystyle aB \ ab-ig}
![{\ displaystyle aB \ ab-ig}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eadc7327a7b7cda2be0e5833fcdd9766125198b9)
- bB→bb{\ displaystyle bB \ to bb}
![{\ displaystyle bB \ to bb}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf3ca6ae444e64991e3cf151abd8dacb53a38f)
- bVS→bvs.{\ displaystyle bC \ to bc}
![{\ displaystyle bC \ to bc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae0b6c3bc3be4e54ab904bed09b935644e2fb5fc)
- vs.VS→vs.vs.{\ displaystyle cC \ to cc}
![{\ displaystyle cC \ to cc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501a156633feea0d3da1a79cdcfeb85c4842bfed)
Az első két szabály a szavak előállítására szolgál . A következő három szabályok lehetővé teszik, hogy cserélje ki a . A levezetése a következő:
nál nélnem(BVS)nem{\ displaystyle a ^ {n} (BC) ^ {n}}
VSB{\ displaystyle CB}
BVS{\ displaystyle BC}
nál nélnál nélnál nélbbbvs.vs.vs.{\ displaystyle aaabbbccc}![{\ displaystyle aaabbbccc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ec095ab16679aac56c29373186f0bd2344d5659)
S⇒1nál nélSBVS⇒1nál nélnál nélSBVSBVS⇒2nál nélnál nélnál nélBVSBVSBVS⇒3nál nélnál nélnál nélBHBVSBVS⇒4nál nélnál nélnál nélBHVSVSBVS⇒5.nál nélnál nélnál nélBBVSVSBVS⇒3nál nélnál nélnál nélBBVSHBVS⇒4nál nélnál nélnál nélBBVSHVSVS⇒5.nál nélnál nélnál nélBBVSBVSVS⇒3nál nélnál nélnál nélBBHBVSVS⇒4nál nélnál nélnál nélBBHVSVSVS⇒5.nál nélnál nélnál nélBBBVSVSVS⇒6.nál nélnál nélnál nélbBBVSVSVS⇒7nál nélnál nélnál nélbbBVSVSVS⇒7nál nélnál nélnál nélbbbVSVSVS⇒8.nál nélnál nélnál nélbbbvs.VSVS⇒9.nál nélnál nélnál nélbbbvs.vs.VS⇒9.nál nélnál nélnál nélbbbvs.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 {aligned}}}![{\ 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 {aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c486b715f6792266c4ab9e743c81c54293acfd62)
Ugyanezt a nyelvet a következő növekvő nyelvtan generálhatja:
- S→nál nélbvs.{\ displaystyle S \ abc}
![{\ displaystyle S \ abc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/937b9b30351913a0ddef674c850276ec59213761)
- S→nál nélSBvs.{\ displaystyle S \ to aSBc}
![{\ displaystyle S \ to aSBc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e2ac1a46d28e12fb4bdf5629ba3f1465ece1a5a)
- vs.B→Bvs.{\ displaystyle cB \ to Bc}
![{\ displaystyle cB \ to Bc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ead4cecb3c46ca51ded677cd567766c87db4134b)
- bB→bb{\ displaystyle bB \ to bb}
![{\ displaystyle bB \ to bb}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf3ca6ae444e64991e3cf151abd8dacb53a38f)
- A következő növekvő nyelvtan generálja a négyzetek nem algebrai nyelvét :VS={xx|x∈{nál nél,b}+}{\ displaystyle C = \ {xx | x \ in \ {a, b \} ^ {+} \}}
![{\ displaystyle C = \ {xx | x \ in \ {a, b \} ^ {+} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00be151590ac6d697710728490a0a748891c6b7a)
- S→nál nélNÁL NÉLS|bBS|nál nélNÁL NÉL¯|bB¯{\ displaystyle S \ rightarrow aAS | bBS | a {\ bar {A}} | b {\ bar {B}}}
![{\ displaystyle S \ rightarrow aAS | bBS | a {\ bar {A}} | b {\ bar {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd05271adf8473e1b0caf7fd42bcfa28444579e4)
- NÁL NÉLnál nél→nál nélNÁL NÉL{\ displaystyle Aa \ rightarrow aA}
![{\ displaystyle Aa \ rightarrow aA}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4534a68fb883274672c9248aee39fe03c5a8f28a)
- Bnál nél→nál nélB{\ displaystyle Ba \ rightarrow aB}
![{\ displaystyle Ba \ rightarrow aB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b607dd6709730c32a1245dafb71f48fbcab2936)
- NÁL NÉLb→bNÁL NÉL{\ displaystyle Ab \ rightarrow bA}
![{\ displaystyle Ab \ rightarrow bA}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e3dc5d161ae53f522f7ad1542bcbf28234fd8d8)
- Bb→bB{\ displaystyle Bb \ rightarrow bB}
![{\ displaystyle Bb \ rightarrow bB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba18fbb2d8ede24791fbe0a8b67982eb6df5c89)
- NÁL NÉLNÁL NÉL¯→NÁL NÉL¯nál nél{\ 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)
- BNÁL NÉL¯→B¯nál nél{\ 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)
- NÁL NÉLB¯→NÁL NÉL¯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)
- nál nélNÁL NÉL¯→nál nélnál nél{\ displaystyle a {\ bar {A}} \ rightarrow aa}
![{\ displaystyle a {\ bar {A}} \ rightarrow aa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/023b4e19f54949f661e72fad93776fa36735f4db)
- bNÁL NÉL¯→bnál nél{\ displaystyle b {\ bar {A}} \ rightarrow ba}
![{\ displaystyle b {\ bar {A}} \ rightarrow ba}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28a9be6bff65733767d4ce7ad5db1696993ae030)
- nál nélB¯→nál nélb{\ 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)
Az abaaba levezetése a következő:
S⇒1nál nélNÁL NÉLS⇒1nál nélNÁL NÉLbBS⇒1nál nélNÁL NÉLbBnál nélNÁL NÉL¯⇒4nál nélbNÁL NÉLBnál nélNÁL NÉL¯⇒3nál nélbNÁL NÉLnál nélBNÁL NÉL¯⇒2nál nélbnál nélNÁL NÉLBNÁL NÉL¯⇒7nál nélbnál nélNÁL NÉLB¯nál nél⇒8.nál nélbnál nélNÁL NÉL¯bnál nél⇒10.nál nélbnál nélnál nélbnál nél{\ 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 {aligned}}}![{\ 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 {aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68ae7e97af1dab2d8c886323a5f531291daf4166)
Növekvő nyelvtanok és kontextuális nyelvtanok
Így alakíthatjuk át az egyre növekvő nyelvtant kontextus szerinti nyelvtanná. Még ha ez az űrlap új szabályainak bevezetését is jelenti , hol van egy betű, feltételezhetjük az űrlap összes szabályát
x→nál nél{\ displaystyle X \ to a}
nál nél{\ displaystyle a}![nál nél](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
x1x2⋯xnem→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)
ahol és minden szimbólum változó. Egy ilyen szabályt a következő halmazsal cserélünk:
m≥nem≥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⋯xnem→Z1x2⋯xnemZ1x2⋯xnem→Z1Z2⋯xnem⋯Z1Z2⋯Znem-1xnem→Z1Z2⋯Znem-1YnemYnem+1⋯YmZ1Z2⋯Znem-1YnemYnem+1⋯Ym→Z1Z2⋯Znem-2Ynem-1YnemYnem+1⋯Ym⋯Z1Z2Y3⋯Ym→Z1Y2Y3⋯YmZ1Y2⋯Ym→Y1Y2⋯Ym.{\ displaystyle {\ begin {aligned} X_ {1} X_ {2} \ cdots X_ {n} & \ to Z_ {1} X_ {2} \ cdots X_ {n} \\ Z_ {1} X_ {2} \ cdots X_ {n} és \ to 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} és \ - 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} és \ to Z_ {1} Y_ {2} Y_ {3} \ cdots Y_ {m} \\ Z_ {1} Y_ {2} \ cdots Y_ {m} és \ to Y_ {1} Y_ {2} \ cdots Y_ {m} \ ,. \ end {aligned}}}![{\ displaystyle {\ begin {aligned} X_ {1} X_ {2} \ cdots X_ {n} & \ to Z_ {1} X_ {2} \ cdots X_ {n} \\ Z_ {1} X_ {2} \ cdots X_ {n} és \ to 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} és \ - 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} és \ to Z_ {1} Y_ {2} Y_ {3} \ cdots Y_ {m} \\ Z_ {1} Y_ {2} \ cdots Y_ {m} és \ to Y_ {1} Y_ {2} \ cdots Y_ {m} \ ,. \ end {aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c05f76984ff3d6ad5c0a7e0ed814d669e0cbe62)
Például a következő szabály:
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)
átalakul
x1x2x3→Z1x2x3Z1x2x3→Z1Z2x3Z1Z2x3→Z1Z2Y3Y4Y5.Z1Z2Y3Y4Y5.→Z1Y2Y3Y4Y5.Z1Y2Y3Y4Y5.→Y1Y2Y3Y4Y5.{\ displaystyle {\ begin {aligned} X_ {1} X_ {2} X_ {3} & \ to Z_ {1} X_ {2} X_ {3} \\ Z_ {1} X_ {2} X_ {3} & \ - Z_ {1} Z_ {2} X_ {3} \\ Z_ {1} Z_ {2} X_ {3} és \ - Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ { 5} \\ Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ {5} és \ -től Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \\ Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} és \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \ end {igazítva}}}![{\ displaystyle {\ begin {aligned} X_ {1} X_ {2} X_ {3} & \ to Z_ {1} X_ {2} X_ {3} \\ Z_ {1} X_ {2} X_ {3} & \ - Z_ {1} Z_ {2} X_ {3} \\ Z_ {1} Z_ {2} X_ {3} és \ - Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ { 5} \\ Z_ {1} Z_ {2} Y_ {3} Y_ {4} Y_ {5} és \ -től Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \\ Z_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} és \ - Y_ {1} Y_ {2} Y_ {3} Y_ {4} Y_ {5} \ end {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c23610e5d0d137fc7611f649f84d2289d6bbb3)
Döntési kérdések
- Az algoritmikus komplexitás értelmében eldönthető és PSPACE-teljes annak a problémája, hogy tudjuk-e az x szó az adott kontextus szerinti nyelvtan által generált nyelvhez tartozik-e .
- Dönthetetlen annak eldöntése, hogy a kontextus szerinti nyelvtan által generált nyelv üres-e.
Alkalmazások
Megállapították, hogy a természetes nyelveket általában kontextuális nyelvtanokkal lehet leírni. A kontextuális nyelvek osztálya azonban sokkal nagyobb, mint a természetes nyelveké. Sőt, mivel a döntési probléma teljes a PSPACE esetében , ez a leírás a gyakorlatban nem használható. Éppen ezért a nyelv egy specifikusabb nyelvtani modellek, például a kombinatorikus kategorikus nyelvtanokhoz (in) csatlakozó nyelvtanfa vagy más rendszerek kifejlesztésére irányult . Az e nyelvtanok által generált nyelvek kissé kontextuálisak (en), és szigorúan az algebrai nyelvek és a kontextuális nyelvek közé esnek.
Megjegyzések
-
(in) Noam Chomsky , " Három modell leírására a nyelv " , IRE Transactions on Information Theory , n o 21956, P. 113–124 ( online olvasás )
-
Box 2008 , p. 144 - 145
-
(in) Michael R. Garey és David S. Johnson , Számítógépek és kezelhetetlen: A Guide to the Theory of NP-teljessége , New York, WH Freeman,
1983, 338 p. ( ISBN 0-7167-1045-5 ) - AL3. Feladat: „Lineárisan korlátozott automata elfogadás”, 265. oldal.
-
John E. Hopcroft és Jeffrey D. Ullman, A hivatalos nyelvek és viszonyuk az automatákhoz , Addison-Wesley,1969( ISBN 0-201-02983-9 , SUDOC 004772571 ) - 14.7. Szakasz, 230–23.
-
Lásd például Salamon Marcust , „Kontextus szerinti nyelvtanok és természetes nyelvek” , Grzegorz Rozenberg és Arto Salomaa (szerk.), Formális nyelvek kézikönyve , vol. 2: Lineáris modellezés: Háttér és alkalmazás , Springer Science & Business Media,1997, 528 p. ( ISBN 9783540606482 ) , fejezet. 5. o. 215-236.
Hivatkozások
- Olivier Carton , hivatalos nyelvek, kiszámíthatóság és összetettség ,2008[ a kiadás részlete ] ( online olvasható )
- Michael Sipser , Bevezetés a számítás elméletébe , PWS Publishing Company,1996, 239 o. ( ISBN 0-534-95250-X )
- Pierre Wolper , Bevezetés a kiszámíthatóságba: tanfolyamok és javított gyakorlatok , Párizs, Dunod,2006, 3 e . , 224 p. ( ISBN 2-10-049981-5 )
Fordítási forrás
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">