✖

ภาษารูปนัย

ภาษารูปนัย (formal language) เป็นการขยายความหมายของคำว่า “ภาษา” ที่เราคุ้นเคยในชีวิตประจำวันให้กว้างขึ้น

แนวคิดพื้นฐาน

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

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

สตริง (string) หรือคำ (word) คือลำดับจำกัดของสัญลักษณ์จากอักษร Σ ใดอักษรหนึ่ง เช่น ถ้ามีอักษร Σ= {a,b,c,d,e,…, z} ลำดับ “ahoj” หรือ “dobrman” เป็นสตริง แต่ “naïve” ไม่เป็นสตริง (ไม่มีตัวอักษร “ï”) “Somchai” ก็ไม่เป็นสตริง (ไม่มีตัวอักษร “S”) และ “dobry den” ก็ไม่เป็นสตริงเช่นกัน (ไม่มีช่องว่าง) ความยาวของสตริงคือจำนวนสัญลักษณ์ที่ประกอบกันเป็นสตริงนั้น

การต่อสตริง: ถ้ามีสตริงสองสตริง a = a1a2… an และ b = b1b2… bm การต่อสตริง (concatenation) ทั้งสองจะได้สตริง ab = a1a2… anb1b2… bm ตัวอย่างเช่น การต่อสตริง “ahoj” กับ “dobrman” จะได้สตริง “ahojdobrman” การต่อสตริงเขียนแทนด้วยวงกลมเล็ก คือ a ∘ b หรือไม่ใช้สัญลักษณ์ใดเลยแล้วเขียนสตริงเรียงต่อกันไป

สตริงว่างเขียนแทนด้วย ε หมายถึงสตริงที่มีความยาวเป็นศูนย์ ถ้านำสตริง a = a1… an มาต่อกับสตริงว่าง ε จะได้สตริง a เดิม นั่นคือ a ∘ ε = a

ส่วนปิดคลุมของอักษร Σ คือเซตของสตริงทั้งหมดที่สร้างได้จากอักษร Σ รวมทั้งสตริงว่าง ส่วนปิดคลุมเขียนแทนด้วย Σ∗ ถ้ามีอักษรฐานสอง Σ= {0, 1} จะได้ว่า

Σ∗={ε,0,1,00,01,10,11,000,001,…}

บางครั้งยังใช้ส่วนปิดคลุมบวก (positive closure) ของอักษร ซึ่งก็คือสตริงทั้งหมดที่สร้างได้จากอักษรเช่นกัน ยกเว้นสตริงว่าง ส่วนปิดคลุมบวกเขียนแทนด้วย Σ+ และ Σ+ = Σ∗ ∖ {ε}

ตัวอย่างของอักษร

  • กลับไปที่ตัวอย่างภาษาไทย คำภาษาไทยทุกคำอยู่ในส่วนปิดคลุมของอักษรที่ประกอบด้วยพยัญชนะ สระ วรรณยุกต์ และเครื่องหมายอื่น ๆ (เช่น ไม้ยมก “ๆ”) ถ้าเพิ่มช่องว่างและเครื่องหมายวรรคตอน (จุลภาค มหัพภาค อัศเจรีย์ ปรัศนี …) เข้าไปในอักษรนี้ ส่วนปิดคลุมจะมีประโยคทั้งหมดที่เขียนเป็นภาษาไทยได้ แน่นอนว่าส่วนปิดคลุมนี้ยังมีประโยคอย่าง “กดฟหกด หาสวด ฟหกฤฆฎฏฌ่้ๆๆ ขฃค!!!:??: ::!?:?:กดห” รวมอยู่ด้วย

  • ถ้าอักษรประกอบด้วยเลขโดดทั้งหมด Σ= {0, 1, …, 9} ส่วนปิดคลุมจะมีจำนวนนับทั้งหมด และยังมีสตริงอื่นเกินมาอีก เช่น จำนวนที่ขึ้นต้นด้วยศูนย์อย่าง 00054 หรือศูนย์เพียงตัวเดียว นอกจากนี้ยังมีสตริงว่าง ซึ่งไม่ใช่จำนวนใด ๆ เลย

  • อักษรต้องเป็นเซตไม่ว่าง ดังนั้นอักษรที่เล็กที่สุดต้องมีสัญลักษณ์อย่างน้อยหนึ่งตัว เช่น สำหรับอักษร Σ= {!} จะได้ส่วนปิดคลุม Σ∗ = {ε, !, !!, !!!, !!!!, …} นั่นคือเซตของสตริงซึ่งสำหรับทุก n ∈ ℕ0 จะมีสตริงที่มีเครื่องหมาย “!” จำนวน n ตัวอยู่ในส่วนปิดคลุม และไม่มีสตริงอื่นอยู่ในส่วนปิดคลุมอีก

  • ให้ Σ= {qw,c} อักษรนี้แปลกมาก เพราะมีสตริง qw อยู่ด้วย ปกติไม่ใช้การเขียนแบบนี้เพราะชวนสับสน แต่อาจนึกภาพว่านำตัวอักษร “q” และ “w” มาติดกันจนเป็นอักขระตัวเดียว จึงมองสตริง “qw” เป็นสัญลักษณ์ “qw” ได้ ถ้าสร้างสตริง “qwcqw” จากสัญลักษณ์นี้ สตริงนี้จะมีความยาวสาม เพราะประกอบด้วยสัญลักษณ์ “qw” “c” และ “qw” อักษรลักษณะนี้พบไม่บ่อยนัก แต่ก็มีบางสถานการณ์ที่จำเป็นต้องใช้สัญลักษณ์ที่ประกอบจากสัญลักษณ์หลายตัว

ภาษารูปนัย

ภาษา (รูปนัย) บนอักษร Σ คือสับเซตใด ๆ ของ Σ∗ ดังนั้นสำหรับภาษา L บนอักษร Σ จะได้ว่า L ⊆ Σ∗ ตัวอย่างของภาษา:

  • ในหัวข้อก่อนได้นิยามอักษรของเลขโดด Σ= {0, 1, …, 9} ไว้แล้ว ส่วนปิดคลุมของอักษรนี้คือสตริงทั้งหมดที่ประกอบด้วยเลขโดดเท่านั้น ถ้าเพิ่มกฎว่าสตริงต้องไม่ขึ้นต้นด้วยศูนย์และต้องไม่เป็นสตริงว่าง จะได้เซตของจำนวนนับ ℕ เนื่องจาก ℕ ⊆ Σ∗ ดังนั้น ℕ เป็นภาษาบนอักษร Σ

  • เพิ่มเครื่องหมายลบ “-” เข้าไปในเซตของเลขโดดข้างต้น จะได้ Σ= {0, 1, …, 9, −} ส่วนปิดคลุมคือสตริงทั้งหมดที่ประกอบด้วยเลขโดดหรือเครื่องหมายลบ นั่นหมายความว่าส่วนปิดคลุมมีสตริงอย่าง “12-84-” “1-5-8” หรือ “-” ด้วย ภาษาของจำนวนเต็ม ℤ สร้างได้โดยเพิ่มกฎสามข้อ:

    • เครื่องหมายลบไม่ปรากฏในสตริงเลย หรือปรากฏที่ต้นสตริง
    • เลขโดดตัวแรกของสตริงต้องไม่เป็นศูนย์ ยกเว้นสตริง “0”
    • ทุกสตริงต้องมีเลขโดดอย่างน้อยหนึ่งตัว

    เซตนี้คือเซตของจำนวนเต็ม และเป็นสับเซตของเซต Σ∗ ดังนั้นจึงเป็นภาษาบนอักษร Σ

  • ให้ Σ= {0, 1} ส่วนปิดคลุมคือสตริงทั้งหมดที่ประกอบด้วยเลข 0 และ 1 ภาษา L บนอักษรนี้อาจนิยามเป็นเซตของสตริงทั้งหมดที่มีเลข 1 อยู่สามตัวเท่านั้นก็ได้ หรือจะคิดให้สร้างสรรค์ขึ้นอีกก็ได้ เช่น ให้ภาษา L เป็นเซตของสตริงทั้งหมดที่เป็นไฟล์ docx ที่ถูกต้อง (ไฟล์เอกสารที่ได้จากโปรแกรมประมวลผลคำ)

  • ยังคงใช้อักษรฐานสอง Σ= {0, 1} สตริงของอักขระใด ๆ (อักขระทั่วไปบนแป้นพิมพ์) แปลงเป็นรูปฐานสอง คือเป็นเลข 0 และ 1 ได้ และแปลงกลับได้ เช่น ด้วยตาราง ASCII (พูดให้ถูกต้องคือ ตาราง ASCII แปลงอักขระเป็นจำนวน และจำนวนในระบบเลขฐานสิบแปลงเป็นจำนวนในระบบเลขฐานสองได้) จึงนิยามภาษาของสตริงทั้งหมดที่เป็นที่อยู่อีเมลที่ถูกต้องได้ และภาษานี้ก็ยังเป็นภาษาบนอักษรฐานสอง

การต่อภาษา: ภาษาก็นำมาต่อกันได้ นิยามจะคล้ายกับผลคูณคาร์ทีเซียนของเซต ให้มีภาษาสองภาษา L1 และ L2 การต่อภาษาทั้งสอง L1 ∘ L2 จะได้ภาษาใหม่ซึ่งนิยามดังนี้:

L1∘L2={w1∘w2|w1∈L1,w2∈L2}

นั่นคือ นำสตริงทุกสตริงจากภาษา L1 มาต่อกับสตริงทุกสตริงจากภาษา L2 ตัวอย่างเช่น ให้

L1={0,1}L2={a,b,ahoj}

จะได้ว่า:

L1∘L2={0a,0b,0ahoj,1a,1b,1ahoj}L2∘L1={a0,a1,b0,b1,ahoj0,ahoj1}L1∘L1={00,01,10,11}

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