그리바흐 정상형

공식 언어 이론에서 문맥이 없는 문법은 모든 생산 규칙의 오른쪽이 터미널 기호로 시작하고 선택적으로 몇 가지 변수가 뒤따른다면 그리바흐 정상 형태(GNF)이다.비강제 양식은 빈 단어(epsilon, ε)가 설명 언어의 구성원이 되도록 허용하기 위해 이 형식 제한에 대한 하나의 예외를 허용한다.정상적인 형태는 쉴라 그리바흐에 의해 확립되었으며 그녀의 이름이 적혀 있다.

더 정확히 말하면, 문맥이 없는 문법은 Greibach의 정상적인 형태로, 모든 생산 규칙이 다음과 같은 형태인 경우:

${\displaystyle A\to A_{1}A_{1}A_{2}\cdots A_{n}}$

$여기$서 ${\displaystyle A}$은(는) 비터미널 기호,$$${\displaystyle$ $}$은(는) 단자$$ $기호$, A$n은 시작$ 기호를 포함하지 않고$(아마도 비어$ 있을 것임) 비터미널 기호 시퀀스$$$,$ $S{\displaystyle }$ ${\displaystystyle S}$이(가) 시작 기호다.

문법이 반복되지 않도록 주의하십시오.

문맥이 없는 모든 문법은 그리바흐 정상의 형태로 동등한 문법으로 변형될 수 있다.^[1]다양한 구조물이 존재한다.어떤 이들은 두 번째 형태의 규칙을 허용하지 않으며 빈 단어를 생성할 수 있는 문맥 없는 그래머를 변환할 수 없다.그러한 구문 중 하나에 대해 구성된 문법의 크기는 O()이다.n⁴)은 일반 사례 및 O()의 경우n³) 원본 문법의 파생이 단일 비단어 기호로 구성되지 않는 경우, 다음과 같이 한다.n원래 문법의 크기 입니다.^[2]이 변환은 모든 맥락 없는 언어가 실시간(비결정론적) 푸시다운 자동화에 의해 수용될 수 있음을 증명하는데 사용될 수 있다. 즉, 자동화는 매 단계 입력에서 문자를 읽는다.

GNF의 문법과 길이의 문법에서 파생 가능한 끈을 부여한다.n, 모든 하향식 파서는 깊이에서 정지한다.n.

참고 항목

• 백커스-나우르 양식
• 촘스키 정상형
• 쿠로다 정상형

참조

• Alexander Meduna (6 December 2012). Automata and Languages: Theory and Applications. Springer Science & Business Media. ISBN 978-1-4471-0501-5.
• György E. Révész (17 March 2015). Introduction to Formal Languages. Courier Corporation. ISBN 978-0-486-16937-8.