ไวยากรณ์การต่อช่วง (RCG) เป็นรูปแบบไวยากรณ์ที่พัฒนาโดย Pierre Boullier ^{[ 1 ]}ในปี 1998 เพื่อพยายามอธิบายปรากฏการณ์ต่างๆ ของภาษาธรรมชาติ เช่น ตัวเลขภาษาจีนและการสลับลำดับคำในภาษา เยอรมัน ซึ่งอยู่นอกขอบเขตของภาษาที่ไวต่อบริบทเล็กน้อย^{[ 2 ]}

จากมุมมองทางทฤษฎี ภาษาใดๆ ที่สามารถแยกวิเคราะห์ได้ในเวลาพหุนามจะจัดอยู่ในกลุ่มย่อยของ RCG ที่เรียกว่าไวยากรณ์การเชื่อมต่อช่วงบวก และในทางกลับกัน^{[ 4 ]}

แม้ว่า ไวยากรณ์แบบเคลื่อนไหวตามตัวอักษร (RCG) จะถูกออกแบบมาให้เป็นรูปแบบหนึ่งของไวยากรณ์แบบเคลื่อนไหวตามตัวอักษรของ Groenink (LMG) แต่ RCG กลับมองกระบวนการทางไวยากรณ์เป็นเหมือนการพิสูจน์มากกว่าการสร้างประโยค ในขณะที่ LMG สร้างสตริงสุดท้ายจากภาคแสดงเริ่มต้น RCG มีเป้าหมายที่จะลดภาคแสดงเริ่มต้น (ซึ่งเป็นภาคแสดงของสตริงสุดท้าย) ให้เหลือสตริงว่าง ซึ่งถือเป็นการพิสูจน์ว่าสตริงสุดท้ายนั้นเป็นสมาชิกในภาษา

ไวยากรณ์การเชื่อมต่อช่วงบวก (PRCG) คือทูเปิลโดยที่: ${\displaystyle G=(N,~T,~V,~S,~P)}$

• ${\displaystyle N}$และเป็นเซตจำกัดที่ไม่ซ้ำกันของ (ตามลำดับ) ชื่อ述语, สัญลักษณ์ปลายทางและชื่อตัวแปร แต่ละชื่อ述语จะ มีจำนวนอาร์กิวเมนต์ที่เกี่ยวข้อง ซึ่งกำหนดโดยฟังก์ชัน${\displaystyle T}$${\displaystyle V}$${\displaystyle \dim :N\rightarrow \mathbb {N} \setminus \{0\}}$
• ${\displaystyle S\in N}$คือชื่อเงื่อนไขเริ่มต้นและตรวจสอบ${\displaystyle \dim(S)=1}$
• ${\displaystyle P}$เป็นเซตจำกัดของอนุประโยคในรูปแบบโดยที่เป็นภาคแสดงในรูปแบบที่มีและ${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$${\displaystyle \psi _{i}}$${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}$${\displaystyle A_{i}\in N}$${\displaystyle \alpha _{i}\in (T\cup V)^{\star }}$

ไวยากรณ์การเชื่อมต่อช่วงเชิงลบ (NRCG) ถูกนิยามคล้ายกับ PRCG แต่เพิ่มเติมคือ述语บางตัวที่ปรากฏทางด้านขวามือของประโยคสามารถมีรูปแบบได้述语ดังกล่าวเรียกว่า述语เชิงลบ ${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$

ไวยากรณ์การเชื่อมต่อช่วง (Range Concatenation Grammarหรือ PRCG) มีทั้งแบบบวกและแบบลบ แม้ว่า PRCG จะเป็น NRCG ในทางเทคนิค แต่คำเหล่านี้ถูกนำมาใช้เพื่อเน้นให้เห็นถึงการไม่มีอยู่ (PRCG) หรือการมีอยู่ (NRCG) ของคำกริยาเชิงลบ

ช่วงในคำหนึ่งๆคือคู่ของช่วงโดยที่คือความยาวของช่วง ตัวแปรจะผูกกับช่วง ไม่ใช่กับสตริงของสัญลักษณ์ที่ไม่ใช่เทอร์มินัลแบบใดๆ ช่วงสองช่วงและสามารถต่อกันได้ก็ต่อเมื่อ และเราจะได้: เมื่อสร้างข้อความเงื่อนไข โดยที่อาร์กิวเมนต์ประกอบด้วยองค์ประกอบหลายตัวจากช่วงขององค์ประกอบเหล่านั้นจะต้องต่อกัน ${\displaystyle w\in T^{\star }}$${\displaystyle \langle l,r\rangle _{w}}$${\displaystyle 0\leq l\leq r\leq n}$${\displaystyle n}$${\displaystyle w}$${\displaystyle \langle l_{1},r_{1}\rangle _{w}}$${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$${\displaystyle r_{1}=l_{2}}$${\displaystyle \langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}}$${\displaystyle T\cup V}$

สำหรับคำที่มีสัญลักษณ์จุดสำหรับช่วงคือ: ${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$${\displaystyle w_{i}\in T}$${\displaystyle \langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}}$

สตริงของเงื่อนไขที่ถูกเขียนใหม่นั้นแสดงถึงข้อจำกัดที่สตริงที่กำลังทดสอบต้องเป็นไปตาม (ถ้าเป็นเงื่อนไขเชิงบวก) หรือในกรณีของเงื่อนไขเชิงลบ จะต้องไม่เป็นไปตามเงื่อนไขนั้น ลำดับของเงื่อนไขไม่สำคัญ ขั้นตอนการเขียนใหม่นั้นเทียบเท่ากับการแทนที่ข้อจำกัดหนึ่งข้อด้วยข้อจำกัดที่ง่ายกว่าศูนย์ข้อหรือมากกว่านั้น

เช่นเดียวกับ LMG ข้อความ RCG มีรูปแบบทั่วไปคือ โดยที่ใน RCG นั้นจะเป็นสตริงว่างหรือสตริงของเงื่อนไข อาร์กิวเมนต์ประกอบด้วยสตริงของสัญลักษณ์เทอร์มินัลและ/หรือสัญลักษณ์ตัวแปร ซึ่งจะจับคู่รูปแบบกับค่าอาร์กิวเมนต์จริงเช่นเดียวกับใน LMG ตัวแปรที่อยู่ติดกันจะประกอบเป็นกลุ่มของการจับคู่กับพาร์ติชัน ดังนั้นอาร์กิวเมนต์ที่มีตัวแปรสองตัว จะจับคู่กับสตริงตัวอักษรได้สามวิธีที่แตกต่างกัน: ซึ่งจะทำให้เกิดการสร้างข้อความที่มีอาร์กิวเมนต์นั้นขึ้นมาสามแบบที่แตกต่างกัน ${\displaystyle A(x_{1},...,x_{n})\to \alpha }$${\displaystyle \alpha }$${\displaystyle x_{i}}$${\displaystyle xy}$${\displaystyle ab}$${\displaystyle x=\เอปไซลอน ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\เอปไซลอน }$${\displaystyle xy}$

เงื่อนไขแสดงผลลัพธ์มีสองรูปแบบ คือ รูปแบบบวก (ซึ่งจะให้ผลลัพธ์เป็นสตริงว่างเมื่อสำเร็จ) และรูปแบบลบ (ซึ่งจะให้ผลลัพธ์เป็นสตริงว่างเมื่อล้มเหลว/หากเงื่อนไขบวกไม่ให้ผลลัพธ์เป็นสตริงว่าง) เงื่อนไขลบจะเขียนเหมือนกับเงื่อนไขบวก แต่มีขีดบนกำกับไว้ เช่น. ${\displaystyle {\overline {A(x_{1},...,x_{n})}}}$

ความหมายของการเขียนใหม่สำหรับ RCG นั้นค่อนข้างเรียบง่าย เหมือนกับความหมายที่สอดคล้องกันของ LMG ทุกประการ เมื่อกำหนดสตริงภาคแสดงโดยที่สัญลักษณ์เป็นสตริงเทอร์มินัล หากมีกฎในไวยากรณ์ที่ตรงกับสตริงภาคแสดงนั้น สตริงภาคแสดงจะถูกแทนที่ด้วย โดยแทนที่ตัวแปรที่ตรงกันในแต่ละ ${\displaystyle A(\alpha _{1},...,\alpha _{n})}$${\displaystyle \alpha _{i}}$${\displaystyle A(x_{1},...,x_{n})\to \beta }$${\displaystyle \beta }$${\displaystyle x_{i}}$

ตัวอย่างเช่น เมื่อมีกฎโดยที่และเป็นสัญลักษณ์ตัวแปร และและเป็นสัญลักษณ์ปลายทาง สตริงเงื่อนไขสามารถเขียนใหม่ได้เป็นเนื่องจากตรงกับเมื่อ ในทำนอง เดียวกัน หากมีกฎก็สามารถเขียนใหม่ได้เป็น ${\displaystyle A(x,ayb)\to B(axb,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle a}$${\displaystyle b}$${\displaystyle A(a,abb)}$${\displaystyle B(aab,b)}$${\displaystyle A(a,abb)}$${\displaystyle A(x,ayb)}$${\displaystyle x=a,\ y=b}$${\displaystyle A(x,ayb)\to A(x,x)\ A(y,y)}$${\displaystyle A(a,abb)}$${\displaystyle A(a,a)\ A(b,b)}$

การพิสูจน์/การรับรองสตริงทำได้โดยการแสดงให้เห็นว่าสตริงนั้นสร้างสตริงว่าง สำหรับขั้นตอนการเขียนใหม่แต่ละขั้นตอน เมื่อมีความเป็นไปได้หลายทางในการจับคู่ตัวแปร การเขียนใหม่ใดๆ ที่อาจนำไปสู่ความสำเร็จของการพิสูจน์ทั้งหมดจะถูกนำมาพิจารณา ดังนั้น หากมีอย่างน้อยหนึ่งวิธีในการสร้างสตริงว่างจากสตริงเริ่มต้นการพิสูจน์นั้นจะถือว่าประสบความสำเร็จ ไม่ว่าจะมีวิธีอื่นๆ ที่จะล้มเหลวกี่วิธีก็ตาม ${\displaystyle \alpha }$${\displaystyle S(\alpha )}$${\displaystyle S(\alpha )}$

RCG สามารถรับรู้ภาษาดัชนีที่ไม่เป็นเชิงเส้นได้ดังต่อไปนี้: ${\displaystyle \{www:w\in \{a,b\}^{*}\}}$

ให้ x, y และ z เป็นสัญลักษณ์ตัวแปร: การพิสูจน์สำหรับabbabbabbคือ $${\displaystyle {\begin{aligned}S(xyz)&\to A(x,y,z)\\A(ax,ay,az)&\to A(x,y,z)\\A(bx,by,bz)&\to A(x,y,z)\\A(\epsilon ,\epsilon ,\epsilon )&\to \epsilon \end{aligned}}}$$

${\displaystyle S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

หรือใช้สัญลักษณ์จุดไข่ปลาที่ถูกต้องกว่าสำหรับช่วงข้อมูล:

${\displaystyle S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})}$${\displaystyle \Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

สำหรับสตริงของตัวอักษร จะมีรูปแบบที่แตกต่างกันของข้อความแรกนั้น แต่จะมีเพียงรูปแบบเดียวที่ทำให้ ตัวอักษร ทุกตัวสามารถบรรลุถึงการอนุมานได้ ${\displaystyle 3n}$${\displaystyle {\binom {3n+2}{2}}={\frac {(3n+2)(3n+1)}{2}}}$${\displaystyle x,y,z}$${\displaystyle n}$${\displaystyle \epsilon }$

ไวยากรณ์แบบไร้บริบท (CFG) ทุก รูปแบบ สามารถแปลงเป็นไวยากรณ์แบบเชื่อมต่อช่วงได้:

• สำหรับอนาธานทุกตัวของ CFG นั้น RCG จะมีเพรดิเคทที่ มีจำนวนอาร์กิวเมนต์เท่า กัน${\displaystyle A}$${\displaystyle 1}$${\displaystyle A(x)}$
• สำหรับกฎ CFG ทุกข้อRCG จะมี${\displaystyle A\to BC}$${\displaystyle A(xy)\to B(x)C(y)}$
• สำหรับกฎ CFG ทุกข้อ(ที่เป็นกฎสุดท้าย) RCG จะมี.${\displaystyle A\to a}$${\displaystyle a}$${\displaystyle A(a)\to \epsilon }$

จุดตัดและการรวมกันของภาษาการเชื่อมต่อช่วงสองภาษาก็คือภาษาการเชื่อมต่อช่วงแบบง่ายๆ:

• สำหรับจุดตัดของและคุณจะได้${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S(x)\to A(x)B(x)}$
• สำหรับการรวมกันของและคุณจะได้และ${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S(x)\to A(x)}$${\displaystyle S(x)\to B(x)}$

ภาษาการเชื่อมต่อช่วงที่เป็นไปได้ในเชิงลบก็ปิดภายใต้เซตคอมพลีเมนต์ด้วยเช่นกัน

ผลที่ตามมาจากการกล่าวข้างต้นคือไม่สามารถตัดสินได้ว่าภาษาการเชื่อมต่อช่วง (เชิงบวก) นั้นไม่ว่างเปล่าหรือไม่ เพราะไม่สามารถตัดสินได้ว่าจุดตัดของภาษาไร้บริบทสองภาษานั้นไม่ว่างเปล่าหรือไม่ ดังนั้นไวยากรณ์การเชื่อมต่อช่วงจึงไม่ใช่ไวยากรณ์แบบสร้าง (generative grammars)