ทฤษฎีบทของปาริค

Q: ข้อมูลสำคัญเกี่ยวกับ ทฤษฎีบทของปาริค

ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีทฤษฎีบทของปาริคกล่าวว่า หากพิจารณาเฉพาะจำนวนครั้งที่สัญลักษณ์เทอร์มินัล แต่ละตัวปรากฏ ในภาษาแบบไร้บริบทโดยไม่คำนึงถึงลำดับแล้ว

ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีทฤษฎีบทของปาริคกล่าวว่า หากพิจารณาเฉพาะจำนวนครั้งที่สัญลักษณ์เทอร์มินัล แต่ละตัวปรากฏ ในภาษาแบบไร้บริบทโดยไม่คำนึงถึงลำดับแล้ว ภาษาดังกล่าวจะไม่สามารถแยกแยะได้จากภาษาปกติ^{[ 1 ]}ทฤษฎีบทนี้มีประโยชน์ในการตัดสินว่าสตริงที่มีจำนวนเทอร์มินัลที่กำหนดจะไม่ได้รับการยอมรับจากไวยากรณ์แบบไร้ บริบท ^{[ 2 ]} ทฤษฎีบท นี้ได้รับการพิสูจน์ครั้งแรกโดยโรหิต ปาริคในปี 1961 ^{[ 3 ]}และตีพิมพ์ซ้ำในปี 1966 ^{[ 4 ]}

คำจำกัดความและคำแถลงอย่างเป็นทางการ

ให้เป็นตัวอักษรเวกเตอร์ Parikhของคำ ถูกกำหนดให้เป็นภาพของ คำ นั้นภายใต้ฟังก์ชันที่กำหนดโดย^[¹^] โดยที่แทนจำนวนครั้งที่สัญลักษณ์ ปรากฏในคำ $\Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}$ $w$ ${\textstyle p:\Sigma ^{*}\to \mathbb {N} ^{k}}$ $p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})$ $|w|_{a_{i}}$ $a_{i}$ $w$

เซตย่อยของจะเรียกว่าเป็นเซตเชิงเส้นถ้ามีรูปแบบเป็น สำหรับเวกเตอร์บางตัวเซตย่อยของจะเรียกว่าเป็นเซตกึ่งเชิงเส้นถ้าเป็นผลรวมของเซตเชิงเส้นจำนวนจำกัด $\mathbb {N} ^{k}$ $u_{0}+\mathbb {N} u_{1}+\dots +\mathbb {N} u_{m}=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}$ ${\textstyle u_{0},\ldots ,u_{m}}$ $\mathbb {N} ^{k}$

ทฤษฎีบท—ให้เป็นภาษาไร้บริบทหรือภาษาปกติ และให้เป็นเซตของเวกเตอร์พาริขของคำในนั่นคือแล้วเป็นเซตแบบกึ่งเชิงเส้น $L$ $P(L)$ $L$ ${\textstyle P(L)=\{p(w)\mid w\in L\}}$ $P(L)$

ถ้าเป็นเซตแบบกึ่งเชิงเส้นใดๆ แล้วจะมีภาษาปกติ (ซึ่งโดยเฉพาะอย่างยิ่งเป็นภาษาไร้บริบท) ที่มีเวกเตอร์ Parikh เป็น $S$ $S$

กล่าวโดยสรุป ภาพภายใต้บริบทของภาษาไร้บริบทและภาษาปกติเหมือนกัน และเท่ากับเซตของเซตกึ่งเชิงเส้น $p$

กล่าวได้ว่าสองภาษาสมมูลกันในเชิงสลับที่หากมีชุดเวกเตอร์ปาริคเดียวกัน ดังนั้น ทุกภาษาไร้บริบทจึงสมมูลกันในเชิงสลับที่กับภาษาปกติบางภาษา

การพิสูจน์

ส่วนที่สองนั้นพิสูจน์ได้ง่าย

การพิสูจน์

กำหนดเซตแบบกึ่งเชิงเส้นเพื่อสร้างภาษาปกติที่มีเซตของเวกเตอร์ Parikh เป็น $S$ $S$

$S$ คือการรวมกันของเซตเชิงเส้น 0 เซตขึ้นไป เนื่องจากภาษาว่างเป็นภาษาปกติ และการรวมกันของภาษาปกติก็เป็นภาษาปกติเช่นกัน จึงเพียงพอที่จะพิสูจน์ได้ว่าเซตเชิงเส้นใดๆ ก็คือเซตของเวกเตอร์ Parikh ของภาษาปกติ

ให้แล้ว ก็คือเซตของเวกเตอร์ Parikh ของโดยที่แต่ละมีเวกเตอร์Parikh $S=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}$ $\{z_{0}\}\cdot (\cup _{i=1}^{m}\{z_{i}\})^{*}$ $z_{i}$ $u_{i}$

ส่วนแรกนั้นยากกว่า หลักฐานต่อไปนี้เป็นผลงานของโกลด์สไตน์^{[ 5 ]}

ขั้นแรก เราต้องเสริมความแข็งแกร่งเล็กน้อยให้กับหลักการปั๊ม (pumping lemma) สำหรับภาษาที่ไม่ขึ้นกับบริบท (context-free languages) :

บทตั้ง—ถ้าถูกสร้างขึ้นโดยไวยากรณ์รูปแบบปกติของชอมสกี แล้วซึ่งทำให้ข้อความต่อไปนี้เป็นจริง $L$ $\exists N\geq 1$

สำหรับค่าใดๆและสำหรับค่าใดๆที่มี โดยกำหนดอนุพันธ์ของจากสัจพจน์เราสามารถแบ่ง ออกเป็นส่วนๆและเลือกสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเพื่อให้ได้ดังนี้: $k\geq 1$ $w\in L$ $|w|\geq N^{k}$ $S\Rightarrow ^{*}uAv$ $w$ $S$ $w$ $w=ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v$ $A$

$|x_{i}y_{i}|\geq 1$ สำหรับทุกคนและ $i$ $|x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}$

และสามารถแบ่งกระบวนการสร้างประโยคออกเป็นดังต่อไปนี้ (โดยใช้โครงสร้างประโยคแบบเดียวกัน โดยเฉพาะอย่างยิ่งการใช้สัญลักษณ์ที่ไม่ใช่เทอร์มินัลแบบเดียวกัน): $S\Rightarrow ^{*}uAv$

$S\Rightarrow ^{*}uAv\quad \forall i,A\Rightarrow ^{*}x_{i}Ay_{i}A\Rightarrow ^{*}z\quad$

การพิสูจน์นั้นโดยพื้นฐานแล้วเหมือนกับทฤษฎีบทการสูบฉีดมาตรฐาน: ใช้หลักการรังนกพิราบเพื่อค้นหาสำเนาของสัญลักษณ์ที่ไม่ใช่เทอร์มินัลบางตัวในเส้นทางที่ยาวที่สุดในต้นไม้การสืบเนื่องที่สั้นที่สุด $k$ $A$

ต่อไปนี้เราจะพิสูจน์ส่วนแรกของทฤษฎีบทของปาริค โดยใช้บทพิสูจน์ย่อยข้างต้น

การพิสูจน์

ขั้นแรก สร้างไวยากรณ์รูปแบบปกติของ Chomsky สำหรับ $L$

สำหรับแต่ละเซตย่อยจำกัดที่ไม่ว่างเปล่าของสัญลักษณ์ที่ไม่ใช่เทอร์มินัลให้กำหนดให้ เป็นเซตของประโยคในที่มีการสร้างประโยคโดยใช้สัญลักษณ์ที่ไม่ใช่เทอร์มินัลทุกตัวในไม่มากไม่น้อยกว่านั้น เห็นได้ชัดว่าดังนั้นจึงเพียงพอที่จะพิสูจน์ว่าแต่ละเป็นเซตแบบกึ่งเชิงเส้น $U$ $L_{U}$ $L$ $U$ $L=\cup _{U}L_{U}$ $p(L_{U})$

ทีนี้กำหนดค่าคงที่บางค่าแล้วให้เราสร้างเซตจำกัดสองเซตโดยที่ซึ่งเห็นได้ชัดว่าเป็นเซตกึ่งเชิงเส้น $U$ $k=|U|$ $F,G$ $p(L_{U})=p(F\cdot G^{*})$

เพื่อให้เข้าใจได้ชัดเจนยิ่งขึ้น ให้เขียนว่า "มีการสร้างโดยใช้สัญลักษณ์ที่ไม่ใช่เทอร์มินัลไม่เกิน (แต่ก็อาจน้อยกว่า) ใน" ด้วยเหตุนี้ เราจึงกำหนดดังนี้:

\Rightarrow _{U}^{*}

U

F,G

$F=\{w\in L_{U}:|w|<N^{k}\}$ $G=\{xy:1\leq |xy|\leq N^{k}{\text{ and there exists }}A\in U{\text{ such that }}A\Rightarrow _{U}^{*}xAy\}$

เพื่อพิสูจน์เราใช้วิธีอุปนัยบนความยาวของ $p(L_{U})\subset p(F\cdot G^{*})$ $w\in L_{U}$

ถ้าแล้ว ดังนั้นมิฉะนั้น เนื่องจากจึงมีการพิสูจน์โดยใช้เฉพาะองค์ประกอบของโดยทฤษฎีบทการสูบฉีดที่เสริมความแข็งแกร่ง การพิสูจน์นี้สามารถเขียนใหม่ให้อยู่ในรูปแบบ

|w|<N^{k}

w\in F

p(w)\in p(F\cdot G^{*})

w\in L_{U}

w

U

$S{\underset {d_{0}}{\stackrel {*}{\Rightarrow }}}uAv{\underset {d_{1}}{\stackrel {*}{\Rightarrow }}}ux_{1}Ay_{1}v{\underset {d_{2}}{\stackrel {*}{\Rightarrow }}}\cdots {\underset {d_{k}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}Ay_{k}\cdots y_{1}v{\underset {d_{k+1}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v$

โดยที่, , และ.

A\in U

1\leq |x_{i}y_{i}|

|x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}

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

k-1

U\setminus \{A\}

k

d_{1},...,d_{k}

U\setminus \{A\}

d_{i}

w'

U

L_{U}

$p(w)=p(uzv)+p(x_{1}y_{1})+\cdots +p(x_{k}y_{k})=p(w')+p(x_{i}y_{i})$

โดยการอุปมานและโดยการสร้างดังนั้น

p(w')\in p(F\cdot G^{*})

x_{i}y_{i}\in G

p(w)\in p(F\cdot G^{*})

เพื่อพิสูจน์ให้พิจารณาสมาชิกเราจำเป็นต้องแสดงว่าเราใช้วิธีอุปนัยกับจำนวนตัวประกอบน้อยที่สุดจากที่จำเป็นในการระบุว่า เป็นสมาชิกของ $p(L_{U})\supset p(F\cdot G^{*})$ $w\in F\cdot G^{*}$ $p(w)\in p(L_{U})$ $G$ $w$ $F\cdot G^{*}$

หากไม่จำเป็นต้องใช้ปัจจัยใดๆ จากนั้น.

G

w\in F\subset L_{U}

ในทางกลับกันสำหรับบางค่าและที่ต้องการปัจจัยจากน้อยกว่า

w=w'xy

w'\in F\cdot G^{*}

xy\in G

w'

G

w

โดยการอุปมานสำหรับบางค่าโดยการสร้างจะมีบางค่าที่ทำให้

p(w')=p(w'')

w''\in L_{U}

G

A\in U

A\Rightarrow _{U}^{*}xAy

โดยการสร้างสัญลักษณ์จะปรากฏในการพิสูจน์โดยใช้ ทั้งหมดอย่างแม่นยำจากนั้นเราสามารถแทรกเข้าไปในการพิสูจน์นั้นเพื่อให้ได้ บางค่าที่ทำให้

L_{U}

A

w''

U

A\Rightarrow _{U}^{*}xAy

w'''\in L_{U}

$p(w''')=p(w'')+p(xy)=p(w')+p(xy)=p(w)$

การเสริมความแข็งแกร่งสำหรับภาษาที่มีขอบเขตจำกัด

ภาษาจะถูกจำกัดหากสำหรับคำคงที่บางคำGinsburg และ Spanier ^[⁶^] ได้ให้เงื่อนไขที่จำเป็นและเพียงพอ ซึ่งคล้ายกับทฤษฎีบทของ Parikh สำหรับภาษาที่ถูกจำกัด $L$ $L\subset w_{1}^{*}\ldots w_{k}^{*}$ $w_{1},\ldots ,w_{k}$

เรียกเซตเชิงเส้นว่าเซตแบบแบ่งชั้น (stratified set ) ถ้าในนิยามของเซตนั้นเวกเตอร์ แต่ละตัว มีคุณสมบัติว่ามีพิกัดที่ไม่เป็นศูนย์อย่างมากที่สุดสองพิกัด และสำหรับแต่ละเวกเตอร์ถ้าเวกเตอร์แต่ละตัวมีพิกัดที่ไม่เป็นศูนย์สองพิกัด คือและตามลำดับ แล้วลำดับของเวกเตอร์เหล่านั้นจะไม่ใช่เซตแบบแบ่งชั้น เซตแบบกึ่งเชิงเส้น (semi-linear set) เรียกว่าเซตแบบแบ่งชั้น ถ้าเซตนั้นเป็นการรวมกันของเซตย่อยเชิงเส้นแบบแบ่งชั้นจำนวนจำกัด $i\geq 1$ $u_{i}$ $i,j\geq 1$ $u_{i},u_{j}$ $i_{1}<i_{2}$ $j_{1}<j_{2}$ $i_{1}<j_{1}<i_{2}<j_{2}$

Ginsburg-Spanier —ภาษาที่มีขอบเขตจำกัดจะเป็นภาษาไร้บริบทก็ต่อเมื่อเป็นเซตแบบกึ่งเชิงเส้นที่มีการแบ่งชั้น เท่านั้น $L$ $\{(n_{1},\ldots ,n_{k})\mid w_{1}^{n_{1}}\ldots w_{k}^{n_{k}}\in L\}$

ความสำคัญ

ทฤษฎีบทนี้สามารถตีความได้หลายแบบ มันแสดงให้เห็นว่าภาษาไร้บริบทบนตัวอักษรเดี่ยวต้องเป็นภาษาปกติและภาษาไร้บริบทบางภาษาจะมีไวยากรณ์ที่กำกวม ได้เท่านั้น ภาษาเหล่านั้นเรียกว่าภาษาที่กำกวมโดยเนื้อแท้จาก มุมมอง ของไวยากรณ์เชิงรูปธรรมนี่หมายความว่าไวยากรณ์ไร้บริบทที่ กำกวมบางไวยากรณ์ ไม่สามารถแปลงเป็นไวยากรณ์ไร้บริบทที่ไม่กำกวมที่เทียบเท่ากันได้

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

ทฤษฎีบทของปาริค

คำจำกัดความและคำแถลงอย่างเป็นทางการ

การพิสูจน์

การเสริมความแข็งแกร่งสำหรับภาษาที่มีขอบเขตจำกัด

ความสำคัญ

ข้อมูลสำคัญจากบทความ