선형문법

컴퓨터 과학에서, 선형 문법은 문맥이 없는 문법이며, 각각의 제작물의 오른쪽에는 최소한 하나의 비단어가 있다.

선형 언어는 어떤 선형 문법에 의해 생성된 언어다.

예

선형 문법의 예로는 N = {S}, σ = {a, b}, P(시작 기호 S 및 규칙 포함)가 있다.

S → aSb

S → ε

언어${\displaystyle }${${\displaystyle a^{}}$ b ${\displaystyle i^{}}$ ${\displaystyle i{}^{}}$ ${\displaystyle \ge }$ ${\displaystyle 0}$} ${\displaystyle \{a^{i}b^{i}\; \;i\geq$ 0$\}}$을(를) 생성한다$.$

정규 문법과의 관계

두 가지 특별한 유형의 선형 그래머는 다음과 같다.

• 모든 규칙이 A → αw 형식이고 여기서 α는 비어 있거나 단일 비터미널이며 w는 단자의 문자열인 좌선형 또는 좌정규격 그래머
• 모든 규칙이 A → wα 형식이고 α는 단자의 문자열이며 α는 비어 있거나 단일 비단자 형식인 오른쪽 선형 또는 오른쪽 정규 그래머.

이들 각각은 정규 언어를 정확히 묘사할 수 있다.정규 문법은 좌선형 또는 우선형 문법이다.

새로운 비단어를 삽입함으로써, 어떤 선형 문법은 어떤 규칙들은 왼쪽 선이고 어떤 것은 오른쪽 선인 것과 동등한 문법으로 대체될 수 있다는 것을 관찰하라.예를 들어, 위의 G의 규칙은 다음으로 대체될 수 있다.

S → A

A → Sb

S → ε

그러나 모든 규칙은 좌선형(또는 모든 규칙은 우선형)이어야 한다는 요건은 선형 문법의 표현력을 엄격히 감소시킨다.

표현력

모든 정규 언어는 선형이다. 반대로, 위에서 설명한 바와 같이, 선형, 비정규 언어의 예는 {abⁿⁿ }이다.모든 선형 언어는 문맥이 없다. 반대로 문맥이 없는 비선형 언어의 예는 균형 잡힌 대괄호 쌍의 Dyck 언어다.따라서 정규 언어는 선형 언어의 적절한 하위 집합이며, 이는 다시 문맥이 없는 언어의 적절한 하위 집합이다.

정규 언어인 선형 언어가 결정론적인 반면, 비결정론적인 선형 언어가 존재한다.예를 들어, 알파벳 0과 1의 짝수 길이의 팔린드롬 언어는 선형 문법 S → 0S0 1S1 ε을 가지고 있다. 이 언어의 임의 문자열은 모든 문자를 먼저 읽지 않고는 구문 분석할 수 없다. 즉, 푸시다운 자동화가 다른 가능한 길이에 적응하기 위해 대체 상태 전환을 시도해야 한다는 것을 의미한다.반모양의 ^[1]끈이 언어는 비결정론적이다.비결정론적 문맥 없는 언어는 선형 시간에서는 받아들일 수 없기 때문에, 선형 언어는 일반적인 경우 선형 시간에서는 받아들일 수 없다.더욱이 주어진 문맥이 없는 언어가 문맥이 없는 선형 언어인지 여부는 불분명하다.^[2]

마감 속성

L이 선형 언어이고 M이 정규 언어인 경우, 교차로 ${\displaystyle L}$ ${\displaystyle \cap }$ M$[\displaystyle L\cap M}$은 다시 선형 언어인$$ 것이다. 즉, 선형 언어는 정규 집합과 교차로에서 닫힌다.게다가, 선형 언어는 동형주의와 역동형주의에 의해 폐쇄된다.^[3]이 세 개의 폐쇄 속성은 선형 언어가 완전한 3중창을 형성한다는 것을 보여준다.일반적으로 풀 트리오(full trios)는 몇 가지 다른 바람직한 수학 특성을 즐기는 언어 가족이다.

참조