ภาษาปกติและออโตมาตาจำกัด ภาษาปกติ ภาษาปกติและเครื่องสถานะ

ชุดปกติและนิพจน์ทั่วไป

ชุดปกติ

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

คำจำกัดความ 1.อนุญาตวี 1 และวี 2 - โซ่มากมาย เรากำหนดสามการดำเนินการในชุดเหล่านี้

ยูเนี่ยน: V 1 V 2 =(|   V 1 ) หรือ   V 2 .

การต่อข้อมูล (ผลิตภัณฑ์ การติดกาว): Vl V2 = (|  V 1 ,  V 2 ) โดยปกติแล้วเครื่องหมายของการดำเนินการต่อข้อมูลจะถูกละไว้

ตัวอย่าง: V, = (abc, ba), V 2 = (b, cb) V1V2 =(abcb, abccb, bab, bacb)

แสดงด้วย V n ผลคูณของชุด n V:V n =VV...V,V° =() (ในที่นี้  เป็นสตริงว่าง)

ตัวอย่าง: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc)

3. การวนซ้ำ: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

ตัวอย่าง: V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...)

คำจำกัดความ 4.13.คลาสของเซตปกติเหนือพจนานุกรมจำกัดวี กำหนดไปเช่นนี้:

สหภาพ ST;

การต่อข้อมูล ST;

การวนซ้ำ S* และ T*

5. ถ้าเซตไม่สามารถสร้างได้โดยใช้กฎข้อ 1-4 ในจำนวนจำกัด แสดงว่าเซตนั้นผิดปกติ

ตัวอย่างของเซตปกติ: (ab, ba)* (aa); (ข)((ค)(ง, ab)*). ตัวอย่างของเซตผิดปกติ: (a n b n | n > 0); ( | ในห่วงโซ่  จำนวนอักขระ a และ b เท่ากัน)

นิพจน์ทั่วไป

ชุดปกตินั้นดีเพราะสามารถอธิบายได้ง่ายมากโดยใช้สูตร ซึ่งเราจะเรียกว่านิพจน์ทั่วไป

คำจำกัดความ 2คลาสนิพจน์ทั่วไปเหนือพจนานุกรมสุดท้ายวี กำหนดไปเช่นนี้:

ผลรวม R1+R2;

ผลิตภัณฑ์ของพวกเขา R1R2;

การวนซ้ำ R1* และ R2*

4. หากนิพจน์ไม่ได้สร้างขึ้นจากการใช้กฎข้อ 1-3 ในจำนวนจำกัด แสดงว่าไม่ปกติ

สามารถละเครื่องหมายของผลิตภัณฑ์ได้ เพื่อลดจำนวนวงเล็บ เช่นเดียวกับพีชคณิตอื่นๆ จะใช้ลำดับความสำคัญของการดำเนินการ: การวนซ้ำมีลำดับความสำคัญสูงสุด งานที่มีลำดับความสำคัญน้อยกว่า นอกจากนี้มีความสำคัญต่ำสุด

ตัวอย่างของนิพจน์ทั่วไป: ab + ba*; (aa)*b + (c + แต้ม)*.

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

ให้ R^ เป็นชุดปกติที่สอดคล้องกับนิพจน์ทั่วไป R จากนั้น:

ดังนั้น นิพจน์ทั่วไปจึงเป็นสูตรจำกัดที่กำหนดสตริงจำนวนไม่สิ้นสุด ซึ่งก็คือภาษา

มาดูตัวอย่าง Regular Expression และภาษาที่เกี่ยวข้องกัน

การแสดงออกปกติ	ภาษาที่สอดคล้องกัน
	สตริงทั้งหมดที่ขึ้นต้นด้วย b ตามด้วยจำนวนอักขระตามอำเภอใจ a
	สตริงทั้งหมดจาก a และ b มี b สองครั้งพอดี
	สตริงทั้งหมดของ a และ b ที่มี b เป็นคู่เท่านั้น
(a+b)*(aa+bb)(a+b)*	สตริงทั้งหมดจาก a และ b ที่มี a หรือ b ที่อยู่ติดกันอย่างน้อยหนึ่งคู่
(0+1)*11001(0+1)*	สตริงทั้งหมดของ 0 และ 1 ที่มีสตริงย่อย 11001
	สตริงทั้งหมดของ a และ b ที่ขึ้นต้นด้วย a และลงท้ายด้วย b

เห็นได้ชัดว่าชุดของสตริงเป็นแบบปกติก็ต่อเมื่อสามารถแสดงด้วยนิพจน์ทั่วไปได้ อย่างไรก็ตาม สตริงชุดเดียวกันสามารถแทนได้ด้วยนิพจน์ทั่วไปที่แตกต่างกัน ตัวอย่างเช่น ชุดของสตริงที่ประกอบด้วยอักขระ a และมี a อย่างน้อยสองตัวสามารถแสดงด้วยนิพจน์: aa*a; อะ*aa*; aaa*; a*aa*aa* เป็นต้น

นิยาม 3.นิพจน์ทั่วไปสองรายการ R1 และ R2 เรียกว่าเทียบเท่า (แสดงแทน Rl = R2) ถ้าและถ้าร1 ^ = ร2 ^ .

ดังนั้น aa*a = a*aaa* = aaa* = a*aa*aa* คำถามเกิดขึ้นว่าจะกำหนดความเท่าเทียมกันของนิพจน์ทั่วไปสองรายการได้อย่างไร

ทฤษฎีบท1 . สำหรับนิพจน์ทั่วไปอาร์ เอส และต ยุติธรรม:

ความสัมพันธ์เหล่านี้สามารถพิสูจน์ได้โดยการตรวจสอบความเท่าเทียมกันของชุดโซ่ที่สอดคล้องกัน สามารถใช้เพื่อลดความซับซ้อนของนิพจน์ทั่วไป ตัวอย่างเช่น b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b ดังนั้น b (b + aa*b) = ba*b ซึ่งไม่ชัดเจน

ทฤษฎีบทของไคลน์

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

ทฤษฎีบท2 . (ทฤษฎีบทของไคลน์) คลาสของเซตปกติและภาษาหุ่นยนต์ตรงกัน นั่นคือ เอ = ร .

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

ให้เราแนะนำแบบจำลองกราฟการเปลี่ยนแปลงในลักษณะทั่วไปของแบบจำลองหุ่นยนต์ที่มีขอบเขตจำกัด กราฟการเปลี่ยนแปลงมีจุดยอดเริ่มต้นหนึ่งจุดและจำนวนจุดสิ้นสุดตามอำเภอใจ และมีการทำเครื่องหมายที่ขอบกำกับ ซึ่งแตกต่างจากออโตมาตอนจำกัด ไม่ใช่ด้วยสัญลักษณ์ แต่ใช้นิพจน์ทั่วไป กราฟการเปลี่ยนแปลงยอมรับห่วงโซ่ a ถ้า กอยู่ในชุดของห่วงโซ่ที่อธิบายโดยผลคูณของนิพจน์ทั่วไป R 1 R 2 ...R n ซึ่งทำเครื่องหมายเส้นทางจากจุดยอดเริ่มต้นไปยังจุดยอดสุดท้ายจุดใดจุดหนึ่ง ชุดของห่วงโซ่ที่อนุญาตโดยกราฟการเปลี่ยนแปลงสร้างภาษาที่อนุญาต

ข้าว. 1. กราฟการเปลี่ยนแปลง

บนมะเดื่อ 1 แสดงกราฟการเปลี่ยนแปลงที่อนุญาต ตัวอย่างเช่น เชน abbca เนื่องจากเส้นทาง s->r->p->s->r->q ซึ่งนำไปสู่สถานะสุดท้าย q ถูกทำเครื่องหมายด้วยเชนของปกติ นิพจน์ab* c*а ออโตมาตอนที่มีขอบเขตเป็นกรณีพิเศษของกราฟการเปลี่ยนแปลง ดังนั้นภาษาทั้งหมดที่อนุญาตโดยออโตมาตาจึงได้รับอนุญาตจากกราฟการเปลี่ยนแปลงด้วย

ทฤษฎีบท 3ภาษาหุ่นยนต์ทุกตัวเป็นชุดปกติ เอ  ร.

การพิสูจน์. กราฟการเปลี่ยนผ่านที่มีจุดยอดเริ่มต้นหนึ่งจุดและจุดยอดสุดท้ายหนึ่งจุด ซึ่งมีขอบเพียงจุดเดียวจากจุดยอดเริ่มต้นไปยังจุดยอดสุดท้ายที่มีป้ายกำกับด้วยนิพจน์ทั่วไป R ยอมรับภาษา R ^ (รูปที่ 1)

ข้าว. 2. กราฟการเปลี่ยนแปลงยอมรับ FT ภาษาปกติ

ให้เราพิสูจน์ว่าแต่ละภาษาของออโตมาตอนเป็นชุดปกติโดยการลดกราฟการเปลี่ยนแปลงใดๆ โดยไม่ต้องเปลี่ยนภาษาที่ยอมรับให้อยู่ในรูปแบบที่เทียบเท่า (รูปที่ 2)

ออโตมาตอนที่มีขอบเขตจำกัดและกราฟทรานซิชั่นใดๆ สามารถแสดงในรูปแบบนอร์มัลไลซ์ได้เสมอ ซึ่งจะมีจุดยอดเริ่มต้นเพียงจุดเดียวที่มีขอบออกเท่านั้น และจุดสุดยอดสุดท้ายเพียงจุดเดียวที่มีขอบเข้าเท่านั้น (รูปที่ 3)

ข้าว. 3. กราฟการเปลี่ยนผ่านมีจุดยอดเริ่มต้นหนึ่งจุดและจุดยอดสุดท้ายหนึ่งจุด

ด้วยกราฟการเปลี่ยนแปลงที่แสดงในรูปแบบปกติ การดำเนินการลดสองขั้นตอนสามารถทำได้ - การลดขอบและการลดจุดยอด - ในขณะที่รักษาภาษาที่อนุญาตโดยกราฟการเปลี่ยนแปลงนี้:

ก) การลดขอบ:

ข ) การลดลงของจุดยอด (การแทนที่จะดำเนินการสำหรับแต่ละเส้นทางที่ผ่านจุดยอด p โดยมีการโยนทิ้งในภายหลังเป็นสถานะที่ไม่สามารถเข้าถึงได้):

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

ตัวอย่าง

ให้ออโตมาตอนที่มีขอบเขตจำกัด A ได้รับ:

เราสร้างกราฟการเปลี่ยนแปลงที่เทียบเท่าในรูปแบบปกติ

การลดจุดสุดยอด 3:

การลดส่วนโค้งและการใช้กฎ R = R:

การลดจุดสุดยอด 2:

การลดส่วนโค้งและจุดยอด 1:

ดังนั้น ภาษาที่หุ่นยนต์ A รู้จักจึงถูกกำหนดโดยนิพจน์ทั่วไป: R A = b+(a+bb)(b+ab)*a

ให้เราพิสูจน์ทฤษฎีบทของ Kleene ในอีกทางหนึ่ง

ทฤษฎีบท 2ทุกชุดปกติเป็นภาษาอัตโนมัติ: R ก.

การพิสูจน์.ให้เราแสดงว่าสำหรับแต่ละนิพจน์ทั่วไป R a (อาจไม่ใช่ตัวกำหนด) ออโตมาตอนจำกัด A r สามารถสร้างได้ซึ่งรู้จักภาษาที่ระบุโดย R เราจะกำหนดออโตมาตาดังกล่าวซ้ำ

(รวมสถานะเริ่มต้นและสถานะสุดท้ายของ A)

ตัวอย่าง(ต่อเนื่อง)

ไวยากรณ์ปกติ ออโตมาตาจำกัด และชุดปกติ (และนิพจน์ทั่วไปที่แสดงถึงสิ่งเหล่านี้) เป็นสามวิธีที่แตกต่างกันในการกำหนดภาษาปกติ

คำแถลง

ภาษาคือ RM ก็ต่อเมื่อมันถูกกำหนดโดยไวยากรณ์เชิงเส้นซ้าย (เชิงเส้นตรง) ภาษาสามารถกำหนดได้ด้วยไวยากรณ์เชิงเส้นซ้าย (เชิงเส้นตรง) หากเป็นชุดปกติ

ภาษาเป็น PM ก็ต่อเมื่อมันถูกระบุโดยเครื่องสถานะ ภาษาได้รับการยอมรับโดยเครื่องของรัฐหากเป็น PM

ทั้งสามวิธีนี้เทียบเท่ากัน มีอัลกอริทึมที่อนุญาตให้สร้างวิธีอื่นที่กำหนดภาษาเดียวกันสำหรับภาษาที่ระบุด้วยวิธีใดวิธีหนึ่ง คำอธิบายโดยละเอียดของอัลกอริทึมเหล่านี้มีอยู่ในเอกสาร (ดูรายชื่อ)

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

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

หากต้องการสร้าง CA ตามไวยากรณ์ปกติที่รู้จัก จะต้องย่อให้อยู่ในรูปแบบอัตโนมัติ ชุดของสถานะอัตโนมัติจะสอดคล้องกับชุดของสัญลักษณ์ที่ไม่ใช่ขั้วของไวยากรณ์ 2.3.2 คุณสมบัติของภาษาปกติ

ชุดเรียกว่าปิดด้วยความเคารพต่อการดำเนินการบางอย่าง ถ้าเป็นผลมาจากการดำเนินการนี้กับองค์ประกอบใดๆ ของมัน ได้รับองค์ประกอบใหม่ที่เป็นของชุดเดียวกัน

ชุดปกติจะปิดภายใต้การดำเนินการของการตัดกัน การรวมกัน การบวก การวนซ้ำ การต่อ การเปลี่ยนชื่อสัญลักษณ์ และการแทนที่สตริงสำหรับสัญลักษณ์

ปัญหามากมายสามารถแก้ไขได้สำหรับภาษาทั่วไปที่ไม่สามารถแก้ไขได้สำหรับภาษาประเภทอื่น ตัวอย่างเช่น ปัญหาต่อไปนี้สามารถแก้ไขได้ไม่ว่าจะระบุภาษาด้วยวิธีใดก็ตาม:

ปัญหาความเท่าเทียมกัน: ให้สองภาษาปกติ L 1 (V) และ L 2 (V) จำเป็นต้องระบุว่าเทียบเท่าหรือไม่

ปัญหาของห่วงโซ่ที่เป็นของภาษา กำหนดภาษาปกติ L(V) สตริงสัญลักษณ์ V * จำเป็นต้องตรวจสอบว่าเชนนี้เป็นของภาษานั้นหรือไม่

ปัญหาความว่างเปล่าของภาษา กำหนดภาษาปกติ L(V) จำเป็นต้องตรวจสอบว่าภาษานี้ว่างเปล่าหรือไม่ เช่น หาโซ่ L(V) อย่างน้อยหนึ่งโซ่

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

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

อย่างเป็นทางการ บทแทรกจะเขียนดังนี้ หากกำหนดภาษา L ค่าคงที่ p>0 เช่นนั้นถ้า L และ p สามารถเขียนห่วงโซ่ในรูปแบบโดยที่ 0

ตัวอย่าง. พิจารณาภาษา L=(a n bn n>0) ให้เราพิสูจน์ว่าไม่ใช่เรื่องปกติที่ใช้บทแทรกเกี่ยวกับการเติบโตของภาษา

ปล่อยให้ภาษานี้เป็นปกติ จากนั้นบทแทรกการเติบโตจะต้องคงไว้ ลองใช้เชนของภาษานี้ = a n b n และเขียนในรูปแบบ ถ้า a + หรือ b + สตริง i ไม่ได้เป็นของภาษาสำหรับ i ใดๆ ซึ่งขัดแย้งกับเงื่อนไขของบทแทรก ถ้า a + b + ดังนั้นสตริง 2 ไม่ได้เป็นของภาษา L เราได้รับความขัดแย้งดังนั้นภาษาจึงไม่ปกติ

ทฤษฎีออโตมาตา เป็นส่วนทฤษฏี ระบบควบคุมซึ่งศึกษาแบบจำลองทางคณิตศาสตร์ของตัวแปลงข้อมูลแบบไม่ต่อเนื่องเรียกว่า ปืนกล. จากมุมมองหนึ่ง ตัวแปลงดังกล่าวเป็นทั้งอุปกรณ์จริง (คอมพิวเตอร์ ออโตมาตา สิ่งมีชีวิต ฯลฯ) และระบบนามธรรม (เช่น ระบบที่เป็นทางการ ทฤษฎีเชิงสัจพจน์ ฯลฯ) ซึ่งทำให้สามารถนำทฤษฎีไปใช้ได้ ของออโตมาตาในงานวิจัยทางวิทยาศาสตร์และประยุกต์ต่างๆ ทฤษฎีออโตมาตาเชื่อมโยงอย่างใกล้ชิดที่สุดกับตรรกะทางคณิตศาสตร์และทฤษฎีอัลกอริทึม โดยเฉพาะอย่างยิ่ง ความสามารถในการละลายของแคลคูลัสที่เป็นทางการบางอย่างได้รับการพิสูจน์โดยทฤษฎีออโตมาตะ

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

บทนำ

1. แนวคิดเริ่มต้นของทฤษฎีภาษาทางการ

พิจารณาเซตจำกัดที่ไม่ว่างเปล่า แต่, ประกอบด้วยอักขระ ( ก 1 , …, ก เค). เราจะโทร แต่ ตามตัวอักษร และสัญลักษณ์คือ ตัวอักษร . ลำดับตัวอักษรใด ๆ ในตัวอักษรนี้เรียกว่า คำ (โซ่ หรือ สตริง ): ว=ก 1 ก 2 …ก น- คำ ( ก ผม ก), |ว| - ความยาวของคำ (จำนวนตัวอักษรที่ประกอบกันเป็นคำ และแต่ละตัวอักษรเกิดขึ้นกี่ครั้งก็ได้ตามที่เกิดขึ้นใน ว). ผ่าน | ว| ขแสดงจำนวนครั้งของสัญลักษณ์ ขสรุป ว.

ลำดับตัวอักษรที่ไม่มีที่สิ้นสุด แต่เรียกว่า คำวิเศษณ์ , - superword ของตัวอักษรจำนวนไม่สิ้นสุด ก. ว่างเปล่า เป็นคำที่ไม่มีตัวอักษรประกอบ มันเขียนแทนด้วย  แน่นอน ||=0

- ตัวอักษรหลายคำ แต่ความยาว น. ชุดของคำทั้งหมดของตัวอักษร แต่(รวมถึงคำวิเศษณ์) จะแสดงแทน แต่*. เซตนี้นับได้ เนื่องจากเป็นการรวมตัวของเซตจำกัดจำนวนที่นับได้
. ชุดของคำที่ไม่ว่างทั้งหมดในตัวอักษร แต่แสดง แต่+ . ถ้า ก ก={ก), แล้ว แต่*={ก)* จะแสดงด้วย ก*.

ส่วนย่อยใดๆ
เรียกว่า ภาษา (ภาษาที่เป็นทางการ ) เหนือตัวอักษร แต่.

ถ้า ก xและ ย- คำของภาษา
แล้วคำว่า ฮ(ผลแห่งการบัญญัติศัพท์ ที่ในตอนท้ายของคำ เอ็กซ์) ถูกเรียก การต่อข้อมูล (คลัตช์ , งาน ) คำ เอ็กซ์และ ที่.
(นเมื่อเราใช้เวลา เอ็กซ์). ใส่กันเถอะ
.

พวกเขาพูดคำว่า เอ็กซ์ – คำย่อย คำ ที่, ถ้า ย=uxvสำหรับบางคำ ยูและ โวลต์. คำย่อยทั้งหมดของคำในภาษา
รูปร่าง ชุดของคำย่อย ภาษา แอลซึ่งแสดงโดย Subw( แอล).

ตัวอย่าง. 1. บ้า 3 =บ้า,
- คำนี้มีคำย่อย ab, บ้า, บ้าเป็นต้น

2. ชุด ( ก, แอ๊บ) - ภาษา (สุดท้าย) มากกว่าตัวอักษร ( ก, ข}.

3. มากมาย
เป็นภาษาเหนือตัวอักษร ( ก, ข). ภาษานี้ไม่มีที่สิ้นสุด มันมีคำ ข, บ้า, บ้า, บ้า, บ้า, บ้า, อ่าาาา, อ๊าาเป็นต้น

เนื่องจากแต่ละภาษาเป็นชุด เราสามารถพิจารณาการดำเนินการยูเนียน การตัดกัน และความแตกต่างของภาษาที่กำหนดผ่านตัวอักษรเดียวกัน ใช่ภาษา
, ที่ไหน
เรียกว่าภาษาส่วนเติมเต็ม แอลเกี่ยวกับตัวอักษร แต่. และถ้า  รวมอยู่ด้วยเสมอ แต่* แล้วภาษา
อาจมีหรือไม่มี  ก็ได้ ในกรณีหลัง
.

อนุญาต ,
. แล้วภาษาเรียกว่า การต่อข้อมูล (คลัตช์ , งาน ) ภาษา และ . ในนั้น
,
(นครั้ง) ถ้า น>0.

ตัวอย่าง. 1. ถ้า
,
,แล้ว .

2. ถ้า L=(0, 01) แล้ว
.

การทำซ้ำ ภาษา แอลเรียกว่าภาษา
(การดำเนินการนี้เรียกอีกอย่างว่า สตาร์คลีน ). ภาษา
เรียกว่า การทำซ้ำในเชิงบวก ภาษา แอล.

ตัวอย่าง. ถ้า ก ก={ก, ข) และ แอล={อ่า, ab, บ้า, BB), แล้ว
.

อุทธรณ์ หรือ ในภาพสะท้อน คำ วเรียกว่าคำ ว รซึ่งในตัวอักษรของคำ วไปในลำดับที่กลับกัน ตัวอย่างเช่น ถ้า ว=แบค, แล้ว

อนุญาต
. แล้วภาษา
เรียกว่า อุทธรณ์ ภาษา แอล.

จุดเริ่มต้นของคำใด ๆ จะถูกเรียก คำนำหน้า , และทุกคำที่ลงท้าย - คำต่อท้าย . ตัวอย่างเช่น ถ้า ย=xv, แล้ว เอ็กซ์- คำนำหน้า ที่(การกำหนด - เอ็กซ์[ย) ก โวลต์- คำต่อท้าย ที่(การกำหนด - โวลต์]ย). แน่นอน คำว่างเป็นทั้งคำนำหน้าและคำต่อท้ายของคำใดๆ คำนำหน้าทั้งหมดของคำในภาษา
รูปร่าง ชุดคำนำหน้า ภาษานี้: Pref( แอล)
. คล้ายกับ Suf ( แอล)
-ม ชุดคำต่อท้าย ภาษา
.

ถ้าภาษา แอลเช่นนั้นไม่มีคำพูด แอลไม่ใช่คำนำหน้า (ต่อท้าย) ของคำอื่นใด แอลแล้วพวกเขาก็พูดอย่างนั้น แอลมี คำนำหน้า (ต่อท้าย) คุณสมบัติ .

อนุญาต แต่ 1 และ แต่ 2 - ตัวอักษร ถ้าจอแสดงผล ฉ:
ตรงตามเงื่อนไขทุกคำ
และ
จากนั้นจึงทำการแมป ฉเรียกว่า โฮโมมอร์ฟิซึม .

หมายเหตุ. 1. สามารถพิสูจน์ได้ว่าหาก ฉเป็นโฮโมมอร์ฟิซึมแล้ว
.

2. Homomorphisms ไม่ใช่ bijections เสมอไป แต่ homomorphism แต่ละตัวจะถูกกำหนดโดยค่าของมันในคำที่มีตัวอักษรเดียว

3. การนำโฮโมมอร์ฟิซึมมาใช้กับภาษา แอลเราได้รับภาษาอื่น ฉ(แอล).

ถ้า ก ฉ:
เป็นโฮโมมอร์ฟิซึ่ม
และ
จากนั้นผ่าน ฉ(แอล 1) มีการระบุภาษา
และผ่าน
ภาษาที่กำหนด
และการทำแผนที่เอง
เรียกว่า การผกผันของโฮโมมอร์ฟิซึ่ม .

ตัวอย่าง. 1. สมมติว่าเราต้องการแทนที่ทุกอักขระ 0 ในสตริงด้วยอักขระ กและแต่ละรายการของ 1 เปิดอยู่ BB. จากนั้นเราสามารถกำหนดโฮโมมอร์ฟิซึ่มได้ ฉดังนั้น
และ
. ถ้า ก
, แล้ว
.

2. ปล่อยให้ ฉเป็นโฮโมมอร์ฟิซึมซึ่ง
และ
. แล้ว
และ
.

ในบทนี้ เราจะเริ่มอธิบายองค์ประกอบของทฤษฎีภาษาทางการ

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

เมื่อเรียนภาษา มีสามประเด็นหลักที่ต้องจำไว้

คนแรกคือ ไวยากรณ์ของภาษา . ภาษาคือชุดของ "คำ" โดยที่ "คำ" คือลำดับที่แน่นอนของ "ตัวอักษร" - สัญลักษณ์ของตัวอักษรบางตัวที่ถูกกำหนดล่วงหน้า คำว่า "ตัวอักษร" และ "คำ" สามารถเข้าใจได้หลายวิธี (คำจำกัดความทางคณิตศาสตร์ของคำศัพท์เหล่านี้จะได้รับด้านล่าง) ดังนั้น "ตัวอักษร" สามารถเป็นตัวอักษรของตัวอักษรของภาษาธรรมชาติหรือภาษาที่เป็นทางการบางภาษาได้ เช่น ภาษารัสเซียหรือภาษาโปรแกรม "Pascal" จากนั้น "คำ" จะเป็นลำดับสุดท้ายของ "ตัวอักษร": จระเข้", " จำนวนเต็ม" คำดังกล่าวเรียกว่า "lexemes" แต่ "ตัวอักษร" สามารถเป็น "คำ" ("lexeme") โดยรวม จากนั้น "คำ" คือประโยคของภาษาธรรมชาติหรือโปรแกรมของภาษาโปรแกรม ถ้าบาง ชุดของ "ตัวอักษร" ได้รับการแก้ไขแล้ว ไม่ใช่ทุกลำดับของพวกมันจะเป็น "คำ" นั่นคือ Elexeme ของภาษาที่กำหนด แต่มีเพียงลำดับดังกล่าวที่เป็นไปตามกฎบางอย่างเท่านั้น คำว่า "krykadil" ไม่ใช่ศัพท์ภาษารัสเซีย และคำว่า "iff" ไม่ใช่ศัพท์ในภาษาปาสคาล ประโยค "ฉันรักคุณ" ไม่ใช่ประโยคภาษารัสเซียที่ถูกต้อง เช่นเดียวกับสัญกรณ์ "х:= =t" ไม่ใช่ตัวดำเนินการกำหนด "Pascal" ที่เขียนอย่างถูกต้อง ไวยากรณ์ * ของภาษาเป็นระบบของกฎซึ่งเป็นไปได้ที่จะสร้างลำดับ "ตัวอักษร" ที่ "ถูกต้อง" แต่ละคำของภาษามีโครงสร้างเฉพาะสำหรับภาษานั้นโดยเฉพาะ จากนั้น ในแง่หนึ่ง การพัฒนากลไกสำหรับการแจงนับหรือการสร้างคำที่มีโครงสร้างที่กำหนด และในทางกลับกัน กลไกในการตรวจสอบว่าคำหนึ่งๆ เป็นภาษาใดภาษาหนึ่ง ประการแรก กลไกเหล่านี้ได้รับการศึกษาโดยทฤษฎีคลาสสิกของภาษาทางการ

ลักษณะที่สองคือ ความหมายของภาษา . ความหมาย** เกี่ยวข้องกับการจับคู่คำในภาษาของ "ความหมาย" บางอย่าง ตัวอย่างเช่น เมื่อเขียนสูตรทางคณิตศาสตร์ เราต้องปฏิบัติตามกฎวากยสัมพันธ์ (การจัดวงเล็บเหลี่ยม การสะกดสัญลักษณ์ ลำดับของสัญลักษณ์ ฯลฯ ) แต่ นอกจากนี้ สูตรยังมีความหมายค่อนข้างชัดเจน หมายถึงบางสิ่ง

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

* คำว่า "ไวยากรณ์" มาจากภาษากรีกโบราณ "syn" - "together" และ "taxi" - "order, order" ดังนั้นจึงสามารถเข้าใจไวยากรณ์ได้ว่าเป็น "องค์ประกอบ"

** จากคำภาษากรีกโบราณ "sema" - "sign, sign" และ "semanticos" - "denoting"

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

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

• ตัวอักษร, คำ, ภาษา

• ไวยากรณ์กำเนิด

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

เรารู้การทำงานของการรวมภาษา เรากำหนดการดำเนินการของการต่อข้อมูลและการวนซ้ำ (บางครั้งเรียกว่าการปิด Kleene)

ให้ L 1 และ L 2 เป็นภาษาในตัวอักษร

จากนั้นกล่าวคือ การต่อภาษาประกอบด้วยการเชื่อมคำทุกคำในภาษาที่หนึ่งกับทุกคำในภาษาที่สอง โดยเฉพาะอย่างยิ่ง ถ้า แล้ว และถ้า แล้ว

ให้เราแนะนำสัญกรณ์สำหรับ "องศา" ของภาษา L:

ดังนั้น L i มีคำทั้งหมดที่สามารถแบ่งออกเป็น i คำต่อเนื่องจาก L

การวนซ้ำ (L) * ของภาษา L เกิดจากคำทั้งหมดที่สามารถแบ่งออกเป็นหลายคำติดต่อกันจาก L :

สามารถแสดงโดยใช้องศา:

มักจะสะดวกที่จะพิจารณาการวนซ้ำแบบ "ตัดทอน" ของภาษาที่ไม่มีคำว่างหากไม่มีอยู่ในภาษานั้น: . นี่ไม่ใช่การดำเนินการใหม่ แต่เป็นเพียงการย่อที่สะดวกสำหรับนิพจน์

นอกจากนี้ เรายังทราบด้วยว่าหากเราถือว่าตัวอักษรเป็นภาษาจำกัดที่ประกอบด้วยคำที่มีตัวอักษรเดียว สัญกรณ์ที่แนะนำก่อนหน้านี้สำหรับชุดของคำทั้งหมด รวมทั้งคำที่ว่าง ในตัวอักษรจะสอดคล้องกับคำจำกัดความของการวนซ้ำของภาษานี้ .

ตารางต่อไปนี้ให้คำนิยามอุปนัยที่เป็นทางการ นิพจน์ทั่วไปเหนือตัวอักษรและภาษาที่ใช้แทน

นิพจน์ ร	ภาษา Lr
	L ก = (ก)
ให้ r 1 และ r 2 เป็น	L r1 และ L r2 -เป็นตัวแทน
นิพจน์ทั่วไป.	ภาษาของพวกเขา
แล้วนิพจน์ต่อไปนี้
เป็นปกติ	และเป็นตัวแทนของภาษา:
r=(r1+r2)
r=(r1circr2)
r=(r 1) *	L r = L r1 *

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

คำจำกัดความ 5.1. สอง นิพจน์ทั่วไป r และ p เรียกว่าเทียบเท่าหากภาษาที่พวกเขาเป็นตัวแทนตรงกันเช่น L r = L p . ในกรณีนี้ เราเขียน r = p .

ตรวจสอบได้ง่าย เช่น คุณสมบัติปกติการดำเนินงาน:

• r + p= p+ r (การสับเปลี่ยนยูเนี่ยน),
• (r+p) +q = r + (p+q) (สมาคมสหภาพแรงงาน),
• (r p) q = r (p q) (การเชื่อมโยงของการต่อข้อมูล),
• (r *) * = r * (ศักยภาพของการวนซ้ำ),
• (r+p) คิว = rq + พีคิว(การกระจาย).

ตัวอย่าง 5.1. ตัวอย่างเช่น ลองพิสูจน์ความเท่าเทียมกันที่ไม่ชัดเจน: (r + p) * = (r * p *) * .

ให้ L 1 เป็นภาษาที่แสดงโดยด้านซ้าย และ L 2 เป็นด้านขวา คำว่างเป็นของทั้งสองภาษา หากเป็นคำที่ไม่ว่างเปล่า คำนิยามของการวนซ้ำสามารถแสดงเป็นคำเชื่อมของคำย่อยที่เป็นของภาษาได้ แต่ภาษานี้เป็นส่วนหนึ่งของภาษา L"=L r * L p * (ทำไม?) ดังนั้น . ในทางกลับกัน หากเป็นคำ ก็สามารถแสดงเป็นคำเชื่อมของคำย่อยที่เป็นของภาษา L" . แต่ละคำย่อยดังกล่าว v สามารถแสดงเป็น v= v 1 1 ... v k 1 v 1 2 ... v l 2โดยที่สำหรับทั้งหมด i=1, ... , k เป็นคำย่อยและสำหรับทั้งหมด j=1, ... , l เป็นคำย่อย (เป็นไปได้ว่า k หรือ l เท่ากับ 0) แต่นั่นหมายความว่า w เป็นการเชื่อมคำย่อยเข้าด้วยกัน ซึ่งแต่ละคำเป็นของ และ ดังนั้น