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

กล่าวอย่างเป็นทางการมากขึ้น ความสูงของดาว (star height) ของนิพจน์ปกติEบนตัวอักษร จำกัด Aนั้นถูกกำหนดแบบอุปนัยดังนี้:

• ${\displaystyle \textstyle h\left(\emptyset \right)\,=\,0}$และสำหรับสัญลักษณ์ตัวอักษรa ทุก ตัว ในA${\displaystyle \textstyle h\left(\varepsilon \right)\,=\,0}$${\displaystyle \textstyle h\left(a\right)\,=\,0}$
• ${\displaystyle \textstyle h\left(EF\right)\,=\,h\left(E\,\mid \,F\right)\,=\,\max \left(\,h(E),h(F)\,\right)}$
• ${\displaystyle \textstyle h\left(E^{*}\right)\,=\,h(E)+1.}$

ในที่นี้คือนิพจน์ปกติพิเศษที่ใช้แทนเซตว่าง และ ε คือนิพจน์ปกติพิเศษที่ใช้แทนคำว่างส่วน EและFเป็นนิพจน์ปกติใดๆ ก็ได้ ${\displaystyle \scriptstyle \emptyset }$

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

ในขณะที่การคำนวณความสูงของดาว (star height) ของนิพจน์ปกติ (regular expression) นั้นง่าย แต่การกำหนดความสูงของดาวของภาษานั้นบางครั้งอาจยุ่งยาก เพื่อเป็นตัวอย่าง นิพจน์ปกติ

${\displaystyle \textstyle \left(b\,\mid \,aa^{*}b\right)^{*}aa^{*}}$

ตัวอักษรA = {a,b} มีความสูงของดาวเท่ากับ 2 อย่างไรก็ตาม ภาษาที่อธิบายไว้เป็นเพียงเซตของคำทั้งหมดที่ลงท้ายด้วยaดังนั้นภาษานี้จึงสามารถอธิบายได้ด้วยนิพจน์เช่นกัน

${\displaystyle \textstyle (a\,\mid \,b)^{*}a}$

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

ความสูงของดาวของ^ภาษากลุ่มสามารถคำนวณได้: ตัวอย่างเช่น ความสูงของดาวของภาษาเหนือ { a , b } ซึ่งจำนวนการปรากฏของaและbสอดคล้องกันโมดูล 2 ⁿคือn ^{[ 1} ]

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

ในทฤษฎีกราฟอันดับวัฏจักรr ( G ) ของกราฟทิศทาง (digraph) G  = ( V ,  E )ถูกกำหนดแบบอุปนัยดังนี้:

• ถ้าGไม่มีวัฏจักรr ( G ) = 0โดยเฉพาะอย่างยิ่งถ้าGเป็นเซตว่าง
• ถ้าGเป็นเมทริกซ์ที่เชื่อมต่อกันอย่างแน่นหนาและEเป็นเมทริกซ์ที่ไม่ว่างเปล่า แล้ว

${\displaystyle r(G)=1+\min _{v\in V}r(Gv),\,}$ โดยที่⁠ ⁠${\displaystyle Gv}$คือกราฟระบุทิศทางที่ได้จากการลบจุดยอดv และขอบทั้งหมดที่เริ่มต้นหรือสิ้นสุดที่v

• ถ้าGไม่มีการเชื่อมต่ออย่างแน่นหนาr ( G ) จะเท่ากับลำดับวัฏจักรสูงสุดในบรรดาส่วนประกอบที่มีการเชื่อมต่ออย่างแน่นหนาทั้งหมดของG

ในทฤษฎีออโต มาตา ออ _โตมาตาจำกัดแบบไม่กำหนดที่มีการเปลี่ยนสถานะ ε (ε-NFA) ถูกนิยามว่าเป็นทูเปิล 5 ตัว ( Q , Σ, δ , q0 , F ) ซึ่งประกอบด้วย

• เซตจำกัดของสถานะQ
• เซตจำกัดของสัญลักษณ์อินพุต Σ
• ชุดของขอบที่มีป้ายกำกับδซึ่งเรียกว่าความสัมพันธ์การเปลี่ยนผ่าน : Q × (Σ ∪{ε}) × Qโดยที่ ε แทนคำว่าง
• สถานะเริ่มต้นq ₀ ∈ Q
• เซตของสถานะF ที่ถูก จำแนกเป็นสถานะยอมรับF ⊆ Q

คำw ∈ Σ ^*จะได้รับการยอมรับโดย ε-NFA ก็ต่อเมื่อมีเส้นทางแบบมีทิศทางจากสถานะเริ่มต้นq ₀ไปยังสถานะสุดท้ายบางสถานะในFโดยใช้ขอบจากδซึ่งการต่อกันของป้ายกำกับทั้งหมดที่เยี่ยมชมตามเส้นทางนั้นให้ผลลัพธ์เป็นคำwเซตของคำทั้งหมดใน Σ ^*ที่ได้รับการยอมรับโดยออโตมาตอนคือภาษาที่ ได้รับการยอมรับโดยออโตมาตอนA

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

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

บทพิสูจน์ของทฤษฎีบทนี้ได้รับการนำเสนอโดยEggan (1963)และล่าสุดโดยSakarovitch (2009 )

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

${\displaystyle \textstyle h\left(E^{c}\right)\,=\,h(E)}$

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

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

${\displaystyle \textstyle (a\,\mid \,b)^{*}a,}$

ซึ่งเราได้เห็นในตัวอย่างข้างต้น สามารถอธิบายได้อย่างเทียบเท่าด้วยนิพจน์ปกติทั่วไป

${\displaystyle \textstyle \emptyset ^{c}a}$,

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

ภาษาที่มีความสูงของดาวทั่วไปเป็นศูนย์เรียกว่าภาษาที่ปราศจากดาว (star-free languages ) สามารถแสดงได้ว่าภาษาLเป็นภาษาที่ปราศจากดาวก็ต่อเมื่อโมโนอิดเชิงไวยากรณ์ ของภาษานั้น เป็น แบบ ไม่มีคาบ ( Schützenberger (1965) )

• ปัญหาความสูงของดาว
• ปัญหาความสูงของดาวโดยทั่วไป