ในวิทยาการคอมพิวเตอร์ไวยากรณ์เชิงเส้น (linear grammar)คือไวยากรณ์ที่ไม่ขึ้นกับบริบท (context-free grammar)ซึ่งมีสัญลักษณ์ที่ไม่ใช่เทอร์มินัล (nonterminal) มากที่สุดหนึ่งตัวในด้านขวามือของแต่ละกฎการผลิต

ภาษาเชิงเส้นคือ ภาษาที่สร้างขึ้นจากไวยากรณ์เชิงเส้นบางอย่าง

ตัวอย่างของไวยากรณ์เชิงเส้นคือGโดยที่N = {S}, Σ = {a, b}, Pโดยมีสัญลักษณ์เริ่มต้นSและกฎต่างๆ

S → aSb

S → ε

มันสร้างภาษาขึ้นมา ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$

ไวยากรณ์เชิงเส้นแบบพิเศษสองประเภทมีดังต่อไปนี้:

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

แต่ละข้อเหล่านี้สามารถอธิบายภาษาปกติได้ อย่างแม่นยำ ไวยากรณ์ปกติคือไวยากรณ์ที่เรียงจากซ้ายไปขวา

โปรดสังเกตว่า โดยการแทรกสัญลักษณ์ที่ไม่ใช่เทอร์มินัลใหม่ ไวยากรณ์เชิงเส้นใดๆ ก็สามารถแทนที่ด้วยไวยากรณ์ที่เทียบเท่ากันได้ โดยที่กฎบางข้อเป็นแบบเชิงเส้นซ้าย และบางข้อเป็นแบบเชิงเส้นขวา ตัวอย่างเช่น กฎของGข้างต้นสามารถแทนที่ด้วย

S → aA

A → Sb

S → ε

อย่างไรก็ตาม ข้อกำหนดที่ว่า กฎ ทั้งหมดต้องเป็นแบบเส้นตรงซ้าย (หรือกฎทั้งหมดต้องเป็นแบบเส้นตรงขวา) ส่งผลให้พลังในการแสดงออกของไวยากรณ์เชิงเส้นลดลงอย่างมาก

ภาษาปกติทั้งหมดเป็นภาษาเชิงเส้น ในทางกลับกัน ตัวอย่างของภาษาเชิงเส้นที่ไม่ใช่ภาษาปกติคือ { a ⁿ b ⁿ } ดังที่ได้อธิบายไว้ข้างต้น ภาษาเชิงเส้นทั้งหมดเป็นภาษาไร้บริบทในทางกลับกัน ตัวอย่างของภาษาไร้บริบทที่ไม่ใช่ภาษาเชิงเส้นคือภาษา Dyckของคู่วงเล็บสมดุล ดังนั้น ภาษาปกติจึงเป็นเซตย่อยที่แท้จริงของภาษาเชิงเส้น ซึ่งในทางกลับกันก็เป็นเซตย่อยที่แท้จริงของภาษาไร้บริบท

ในขณะที่ภาษาปกติเป็นภาษาเชิงกำหนดแต่ก็มีภาษาเชิงเส้นที่ไม่เชิงกำหนดอยู่ ตัวอย่างเช่น ภาษาของพาลินโดรม ความยาวคู่ บนตัวอักษร 0 และ 1 มีไวยากรณ์เชิงเส้น S → 0S0 | 1S1 | ε สตริงใดๆ ของภาษานี้ไม่สามารถแยกวิเคราะห์ได้โดยไม่ต้องอ่านตัวอักษรทั้งหมดก่อน ซึ่งหมายความว่าออโตมาตาแบบพุชดาวน์ต้องลองการเปลี่ยนสถานะทางเลือกเพื่อรองรับความยาวที่เป็นไปได้ต่างๆ ของสตริงที่แยกวิเคราะห์บางส่วน^{[ 1 ]}ภาษานี้เป็นภาษาที่ไม่เชิงกำหนด เนื่องจากภาษาบริบทอิสระที่ไม่เชิงกำหนดไม่สามารถยอมรับได้ในเวลาเชิงเส้น ดังนั้นภาษาเชิงเส้นจึงไม่สามารถยอมรับได้ในเวลาเชิงเส้นในกรณีทั่วไป ยิ่งไปกว่านั้น ไม่สามารถตัดสินได้ว่าภาษาบริบทอิสระที่กำหนดเป็นภาษาบริบทอิสระเชิงเส้นหรือไม่^{[ 2 ]}

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

ภาษาเชิงเส้นปิดภายใต้การรวมกันการสร้างนั้นเหมือนกับการสร้างสำหรับการรวมกันของภาษาไร้บริบท ให้ และเป็นภาษาเชิงเส้นสองภาษา จากนั้นจะถูกสร้างขึ้นโดยไวยากรณ์เชิงเส้น โดยที่และทำหน้าที่เป็นไวยากรณ์เชิงเส้นสำหรับ ${\displaystyle L_{1},L_{2}}$${\displaystyle L_{1}\ถ้วย L_{2}}$${\displaystyle S\to S_{1}|S_{2}}$${\displaystyle S_{1},S_{2}}$${\displaystyle L_{1},L_{2}}$

ถ้าLเป็นภาษาเชิงเส้น และMเป็นภาษาปกติการตัดกันของ ภาษาทั้งสองก็ จะเป็นภาษาเชิงเส้นเช่นกัน กล่าวอีกนัยหนึ่ง ภาษาเชิงเส้นทั้งสองมีคุณสมบัติปิดภายใต้การตัดกันกับเซตปกติ ${\displaystyle L\cap M}$

ภาษาเชิงเส้นปิดภายใต้โฮโมมอร์ฟิซึมและ โฮโมมอร์ฟิ ซึมผกผัน^{[ 3 ]}

ผลที่ตามมาคือภาษาเชิงเส้นจะประกอบกันเป็นกลุ่มสามองค์ประกอบที่สมบูรณ์ กลุ่มสามองค์ประกอบที่สมบูรณ์โดยทั่วไปคือตระกูลภาษาที่มีคุณสมบัติทางคณิตศาสตร์ที่พึงประสงค์อื่นๆ อีกสองสามประการ

ภาษาเชิงเส้นไม่ปิดภายใต้การหาจุดร่วม ตัวอย่างเช่น ให้แล้วจุดร่วมของทั้งสองภาษาไม่เพียงแต่ไม่ใช่ภาษาเชิงเส้นเท่านั้น แต่ยังไม่ใช่ภาษาไร้บริบทด้วย ดู ทฤษฎีบทปั๊มสำหรับ ภาษา ไร้บริบท${\displaystyle L_{1}=\{a^{n}b^{n}c^{m}\mid n,m\geq 0\},L_{2}=\{a^{n}b^{m}c^{m}\mid n,m\geq 0\}}$

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