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

สตริงคือลำดับของอักขระที่จำกัดสตริงว่างใช้สัญลักษณ์`null` แทน การต่อสตริงสองสตริงเข้า ด้วยกัน ใช้สัญลักษณ์`concatenation` หรือแบบย่อคือ`concatenation` การต่อสตริงกับสตริงว่างไม่มีผลแตกต่างกัน: `concatenation` การต่อสตริงมีคุณสมบัติการสลับที่ได้ : ` concatenation`${\displaystyle \varepsilon }$${\displaystyle s}$${\displaystyle t}$${\displaystyle s\cdot t}$${\displaystyle st}$${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}$${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}$

ตัวอย่างเช่น, . ${\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }$

ภาษาคือเซตของสตริงที่มีจำนวนจำกัดหรืออนันต์ นอกเหนือจากการดำเนินการเซตทั่วไป เช่น การรวม การตัดกัน ฯลฯ แล้ว การต่อสตริงยังสามารถนำไปใช้กับภาษาได้: ถ้าทั้งและเป็นภาษา การต่อสตริงของทั้งสองภาษาจะถูกกำหนดให้เป็นเซตของการต่อสตริงใดๆ จากและสตริงใดๆ จากในรูปแบบที่เป็นทางการคือโดยที่จุดแสดงการต่อสตริงมักจะถูกละเว้นเพื่อความกระชับ ${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cdot T}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$${\displaystyle \cdot }$

ภาษาที่ประกอบด้วยสตริงว่างเปล่าเพียงอย่างเดียวจะแตกต่างจากภาษาว่างเปล่าการนำภาษาใดๆ มาต่อกับภาษาแรกจะไม่ทำให้เกิดการเปลี่ยนแปลงใดๆในขณะที่การต่อกับภาษาหลังจะให้ผลลัพธ์เป็นภาษาว่างเปล่าเสมอการต่อภาษาต่างๆ มีคุณสมบัติการสลับที่ได้ ${\displaystyle \{\varepsilon \}}$${\displaystyle \{\}}$${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}$${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$

ตัวอย่างเช่น การย่อ จะได้เซตของจำนวนทศนิยมสามหลักทั้งหมดเป็นเซตของจำนวนทศนิยมทั้งหมดที่มีความยาวไม่จำกัดเป็นตัวอย่างหนึ่งของภาษาอนันต์ ${\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}}$${\displaystyle D\cdot D\cdot D}$

ตัวอักษรของสตริงคือเซตของอักขระทั้งหมดที่ปรากฏในสตริงนั้นๆ ถ้าsเป็นสตริงตัวอักษร ของสตริงนั้น จะถูกแทนด้วย

${\displaystyle \operatorname {Alph} (s)}$

อักษรของภาษา คือเซตของอักขระทั้งหมดที่ปรากฏในสตริงใดๆ ก็ตาม โดยมีรูปแบบอย่างเป็นทางการคือ : ${\displaystyle S}$${\displaystyle S}$${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}$

ตัวอย่างเช่น เซตนี้คือตัวอักษรของสตริงและข้างต้นคือตัวอักษรของภาษาข้างต้นรวมถึงตัวอักษรของภาษาของจำนวนทศนิยมทั้งหมดด้วย ${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$${\displaystyle \langle โกโก้\rangle }$${\displaystyle D}$${\displaystyle D\cdot D\cdot D}$

ให้Lเป็นภาษาและให้ Σ เป็นตัวอักษรของภาษานั้นการแทนที่สตริงหรือเรียกง่ายๆ ว่าการแทนที่คือฟังก์ชันfที่แปลงอักขระใน Σ ไปยังภาษาต่างๆ (ซึ่งอาจมีตัวอักษรที่แตกต่างกัน) ตัวอย่างเช่น เมื่อกำหนดอักขระa ∈ Σ จะได้f ( a ) = L _{_a}โดยที่L _{_a} ⊆ Δ ^*คือภาษาที่มีตัวอักษรเป็น Δ ฟังก์ชันนี้สามารถขยายไปยังสตริงได้ดังนี้

f (ε)=ε

สำหรับสตริงว่าง ε และ

f ( sa )= f ( s ) f ( a )

สำหรับสตริงs ∈ Lและอักขระa ∈ Σ การแทนที่สตริงอาจขยายไปยังภาษาทั้งหมดได้ดัง^{[ 1 ]}

${\displaystyle f(L)=\bigcup _{s\in L}f(s)}$

ภาษาปกติปิดภายใต้การแทนที่สตริง กล่าวคือ หากอักขระแต่ละตัวในอักษรของภาษาปกติถูกแทนที่ด้วยภาษาปกติอื่น ผลลัพธ์ก็ยังคงเป็นภาษาปกติ^{[ 2 ]} ในทำนองเดียวกันภาษาไร้บริบทก็ปิดภายใต้การแทนที่สตริง^{[ 3 ] [หมายเหตุ 1 ]}

ตัวอย่างง่ายๆ คือการแปลงf _uc (.) เป็นตัวพิมพ์ใหญ่ ซึ่งอาจกำหนดได้ดังนี้:

สำหรับการขยายฟังก์ชันf _ucไปยังสตริง เรามีตัวอย่างเช่น

• f _uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›} และ
• f _uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

สำหรับการขยายf _ucไปสู่ภาษาต่างๆ เรามีตัวอย่างเช่น

• f _uc ({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }

โฮโมมอร์ฟิซึมของสตริง (มักเรียกง่ายๆ ว่าโฮโมมอร์ฟิซึมในทฤษฎีภาษาเชิงรูปธรรม ) คือการแทนที่สตริงโดยที่อักขระแต่ละตัวจะถูกแทนที่ด้วยสตริงเดียว นั่นคือโดยที่เป็นสตริง สำหรับแต่ละอักขระ[ ^{หมายเหตุ2 ] [ 4 ]}${\displaystyle f(a)=s}$${\displaystyle s}$${\displaystyle a}$

โฮโมมอร์ฟิซึมของสตริงคือมอร์ฟิซึมของโมโนอิดบนโมโนอิดอิสระซึ่งรักษาคุณสมบัติของสตริงว่างและการดำเนินการทวิภาคของการต่อสตริงไว้ เมื่อกำหนดภาษาเซตเรียกว่าภาพโฮโมมอร์ฟิกของภาพโฮโมมอร์ฟิกผกผันของสตริงถูกกำหนดเป็น ${\displaystyle L}$${\displaystyle f(L)}$${\displaystyle L}$${\displaystyle s}$

${\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}$

ในขณะที่ภาพโฮโมมอร์ฟิกผกผันของภาษาถูกนิยามว่า ${\displaystyle L}$

${\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}$

โดยทั่วไปแล้วในขณะที่คนหนึ่งมี ${\displaystyle f(f^{-1}(L))\neq L}$

${\displaystyle f(f^{-1}(L))\subseteq L}$

และ

${\displaystyle L\subseteq f^{-1}(f(L))}$

สำหรับทุกภาษา ${\displaystyle L}$

กลุ่มภาษาปกติปิดภายใต้โฮโมมอร์ฟิซึมและโฮโมมอร์ฟิซึมผกผัน^{[ 5 ]} ในทำนองเดียวกัน ภาษาอิสระบริบทปิดภายใต้โฮโมมอร์ฟิซึม^{[หมายเหตุ 3 ]}และโฮโมมอร์ฟิซึมผกผัน^{[ 6 ]}

กล่าวได้ว่าโฮโมมอร์ฟิซึมของสตริงนั้นปราศจาก ε (หรือปราศจาก e) ถ้าสำหรับทุกaในตัวอักษรตัวอย่างของโฮโมมอร์ฟิซึมของสตริงที่ปราศจาก ε คือ การเข้ารหัสแบบแทนที่ตัวอักษรเดี่ยวอย่างง่าย${\displaystyle f(a)\neq \varepsilon }$${\displaystyle \Sigma }$

ตัวอย่างโฮโมมอร์ฟิซึมของสตริงg _ucสามารถหาได้โดยการกำหนดคล้ายกับ การแทนที่ ข้างต้น : g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε แต่ให้g _ucไม่ถูกกำหนดบนอักขระเครื่องหมายวรรคตอน ตัวอย่างของภาพโฮโมมอร์ฟิกผกผันมีดังนี้

• g _uc ⁻¹ ({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› } เนื่องจากg _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS› และ
• g _uc ⁻¹ ({ ‹A›, ‹bb› }) = { ‹a› } เนื่องจากg _uc (‹a›) = ‹A› ในขณะที่ ‹bb› ไม่สามารถเข้าถึงได้โดยg _uc

สำหรับภาษาหลังg _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› } โฮโมมอร์ฟิซึมg _ucไม่ใช่ ε-free เนื่องจากมันแมป eg ‹0› ไปยัง ε

ตัวอย่างง่ายๆ ของการแปลงสตริงแบบโฮโมมอร์ฟิซึม ซึ่งแมปแต่ละอักขระไปยังอักขระอีกตัวหนึ่ง คือ การแปลงสตริง ที่เข้ารหัสแบบ EBCDICไปเป็นASCII

ถ้าsเป็นสตริง และเป็นตัวอักษรการฉายภาพสตริงของsคือสตริงที่ได้จากการลบตัวอักษรทั้งหมดที่ไม่อยู่ใน ออกไปเขียนได้เป็น โดยนิยามอย่างเป็นทางการคือการลบตัวอักษร ออกจากด้านขวามือ: ${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \pi _{\Sigma }(s)\,}$

${\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{ถ้า }}s=\varepsilon {\mbox{สตริงว่าง}}\\\pi _{\Sigma }(t)&{\mbox{ถ้า }}s=ta{\mbox{ และ }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{ถ้า }}s=ta{\mbox{ และ }}a\in \Sigma \end{cases}}}$

ในที่นี้หมายถึงสตริงว่างการฉายภาพของสตริงนั้นโดยพื้นฐานแล้วเหมือนกับการฉายภาพในพีชคณิตเชิงสัมพันธ์ ${\displaystyle \varepsilon }$

การฉายภาพของสตริงอาจถูกยกระดับเป็นการฉายภาพของภาษาเมื่อกำหนดภาษาเชิงรูปธรรมLการฉายภาพของภาษานั้นจะกำหนดโดย

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$

ผลหารทางขวาของอักขระaจากสตริงsคือการตัดอักขระaในสตริงsจากด้านขวา โดยใช้สัญลักษณ์ถ้าสตริงไม่มีอักขระ aอยู่ทางด้านขวา ผลลัพธ์จะเป็นสตริงว่าง ดังนั้น: ${\displaystyle s/a}$

${\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}$

สามารถหาผลหารของสตริงว่างได้ดังนี้:

${\displaystyle \varepsilon /a=\varepsilon }$

ในทำนองเดียวกัน เมื่อกำหนดเซตย่อยของโมโนอิดแล้ว เราสามารถกำหนดเซตย่อยผลหารได้ดังนี้ ${\displaystyle S\subset M}$${\displaystyle M}$

${\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}$

สามารถนิยาม ผลหารทางซ้ายได้ในลักษณะเดียวกัน โดยการดำเนินการจะเกิดขึ้นทางด้านซ้ายของสตริง

Hopcroft และ Ullman (1979) กำหนดผลหารL ₁ / L ₂ของภาษาL ₁และL ₂บนตัวอักษรเดียวกันเป็นL ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ } ^{[ 7 ]}นี่ ไม่ใช่การสรุปทั่วไปของคำจำกัดความข้างต้น เนื่องจากสำหรับสตริงsและอักขระที่แตกต่างกันa , bคำจำกัดความของ Hopcroft และ Ullman บ่งชี้ว่าส่งผลให้ได้ {} แทนที่จะเป็น { ε }

ผลหารด้านซ้าย (เมื่อกำหนดคล้ายกับ Hopcroft และ Ullman 1979) ของภาษาซิงเกิลตันL ₁และภาษาL ₂ ใดๆ เรียกว่าอนุพันธ์ BrzozowskiหากL ₂ถูกแทนด้วยนิพจน์ปกติผลหารด้านซ้ายก็จะเป็นเช่นกัน^{[ 8 ]}

ผลหารด้านขวาของเซตย่อยของโมโนอิดจะกำหนดความสัมพันธ์สมมูลซึ่งเรียกว่าความสัมพันธ์ทางไวยากรณ์ด้านขวาของSโดยกำหนดโดย ${\displaystyle S\subset M}$${\displaystyle M}$

${\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}$

ความสัมพันธ์ดังกล่าวมีดัชนีจำกัดอย่างชัดเจน (มีจำนวนชั้นสมมูลจำกัด) ก็ต่อเมื่อตระกูลของผลหารด้านขวามีจำนวนจำกัด กล่าวคือ ถ้า

${\displaystyle \{S/m\ \vert \ m\in M\}}$

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

การ ตัด ตัวอักษรaออกจากสตริงs ทาง ด้านขวาคือการลบตัวอักษรa ตัวแรกที่ปรากฏ ในสตริงsโดยเริ่มจากด้านขวา ใช้สัญลักษณ์และนิยามแบบเวียนเกิดว่า ${\displaystyle s\div a}$

${\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}$

สตริงว่างสามารถยกเลิกได้เสมอ:

${\displaystyle \varepsilon \div a=\varepsilon }$

ชัดเจน การยกเลิกที่ถูกต้องและการเดินทาง แบบคาดการณ์ล่วงหน้า :

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$

คำนำหน้าของสตริงคือ เซตของคำนำหน้า ทั้งหมด ของสตริง โดยสัมพันธ์กับภาษาที่กำหนด:

${\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}$

ที่ไหน. ${\displaystyle s\in L}$

การปิดคำนำหน้าของภาษาคือ

${\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}}$

ตัวอย่าง:${\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}$

ภาษาหนึ่งเรียกว่าภาษาปิดคำนำหน้าถ้า. ${\displaystyle \operatorname {Pref} (L)=L}$

ตัวดำเนินการปิดคำนำหน้ามีคุณสมบัติไม่เปลี่ยนแปลงผลลัพธ์ :

${\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}$

ความสัมพันธ์แบบพรีฟิกคือความสัมพันธ์ทวิภาค ที่มีลักษณะว่าถ้าและเฉพาะเมื่อความสัมพันธ์นี้เป็นตัวอย่างเฉพาะของลำดับแบบพรีฟิก ${\displaystyle \sqsubseteq }$${\displaystyle s\sqsubseteq t}$${\displaystyle s\in \operatorname {Pref} _{L}(t)}$

• การเปรียบเทียบภาษาโปรแกรม (ฟังก์ชันสตริง)
• เลวีส์ เลมมา
• สตริง (วิทยาการคอมพิวเตอร์) — คำจำกัดความและการใช้งานการดำเนินการพื้นฐานต่างๆ บนสตริง