일반화된 문맥 자유 문법

Generalized context-free grammar

GCFG(Generalized Context-free Grammar)는 규칙을 [1]다시 작성하기 위해 잠재적으로 문맥이 없는 구성 함수를 추가하여 문맥이 없는 문법을 확장하는 문법 형식주의입니다.헤드 문법(및 그 약한 등가물)은 자연어의 다양한 비CF 속성을 처리하는 데 특히 능숙한 것으로 알려진 GCFG의 한 예입니다.

묘사

GCFG는 문자열 튜플을 결합하는 구성 함수 집합과 다시 쓰기 규칙 집합의 두 가지 구성 요소로 구성됩니다.구성 함수는 모두 f( ,., m , ⟨ 1,. , , .) {\ f ..., x_{rangle, ...)=\displaysty 을 갖습니다. 여기서$\ \displaysty는 문자열 하나입니다.또는 문자열 튜플로 감소하는 (거의 다른) 구성 함수의 일부 사용.다시 쓰기 규칙은 X (,.. ){\ X f 처럼 . 서 YY Z는 문자열 튜플 또는 비종단 기호입니다.

GCFGs의 재작성 의미론은 상당히 간단합니다.비종단 기호의 발생은 문맥이 없는 문법에서와 같이 다시 쓰기 규칙을 사용하여 다시 작성되며, 결과적으로 단지 구성(끈 튜플이나 다른 구성에 적용되는 구성 함수)만 생성됩니다.그런 다음 구성 함수가 적용되어 튜플을 하나의 튜플로 순차적으로 줄입니다.

문맥이 없는 문법을 GCFG로 단순 변환하는 방법은 다음과 같습니다.{wwR : { b\{\{의 팔인드롬 언어 ^{R}}의 문법을 고려할 때, 서 ww w이고, 우리는 (2a와 같이 구성 함수를 정의하고 규칙을 다시 쓸 수 있습니다.

(1)

(2a)

(2b)

Abbba의 CF제작은

S
로서
abSba
abbSba
아부바

그리고 그에 상응하는 GCFG 생산은.

선형 컨텍스트 없는 재작성 시스템(LCFRS)

위어(1988)[1]는 구성 함수의 두 가지 속성인 선형성과 규칙성을 설명합니다.f( 1,. , x ) .{\ f ...,})=로 정의된 함수입니다. 선형입니다. 각 변수가 의 양쪽에 한 번만 나타나 f 으로 만들지만 x, ) g( x =gx, x) = g = f ▁..\displaysty fx_n)로 정의된 함수입니다.왼쪽과 오른쪽이 정확히 동일한 변수를 경우 f) {\ fy) g f( g(x,y) = g(y {\ fy) =x, 가 됩니다.

모든 구성 함수가 선형적이고 규칙적인 문법을 LCFRS(Linear Context-free Rewriting System)라고 합니다.LCFRS는 GCFG의 적절한 하위 클래스입니다. 즉, 전체 GCFG보다 계산 능력이 엄격하게 낮습니다.

반면, LCFRS는 선형 인덱스 문법인접 문법(TAG)[2]과 약하게 동등변형 트리보다 엄격히 더 표현력이 높습니다.헤드 문법은 LCFRS 클래스 전체보다 엄격하게 덜 강력한 LCFRS의 또 다른 예입니다.

LCFRS는 (세트 로컬) 다중 구성 요소 TAG(MCTAG)와 약하게 동등하며 다중 문맥 자유 문법(MCFG [1])[3]최소주의 문법(MG)과도 동일합니다.LCFRS에 의해 생성된 언어(및 그 약한 등가물)는 다항 시간 [4]내에 구문 분석될 수 있습니다.

참고 항목

레퍼런스

  1. ^ a b Weir, David Jeremy (Sep 1988). Characterizing mildly context-sensitive grammar formalisms (PDF) (Ph.D.). Paper. Vol. AAI8908403. University of Pennsylvania Ann Arbor.
  2. ^ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 33. ISBN 978-3-642-14846-0.
  3. ^ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 35-36. ISBN 978-3-642-14846-0.
  4. ^ Johan F.A.K. van Benthem; Alice ter Meulen (2010). Handbook of Logic and Language (2nd ed.). Elsevier. p. 404. ISBN 978-0-444-53727-0.