경미한 문맥 의존 문법 형식주의

Mildly context-sensitive grammar formalism

컴퓨터 언어학에서, 경미한 문맥에 민감한 문법 형식주의라는 용어는 자연 언어의 구문 구조에 대한 적절한 설명을 제공하기 위해 개발된 여러 개의 문법 형식주의를 가리킨다.

모든 경미한 문맥에 민감한 문법 형식주의는 경미한 문맥에 민감한 문법(정식주의에서 지정될 수 있는 문법)의 클래스를 정의하고, 따라서 경미한 문맥에 민감한 언어(정식 문법에 의해 생성된 공식 언어)의 클래스를 정의한다.

배경

1985년까지, 기술 언어학 및 수리 언어학에서 몇몇 연구자들은 자연 언어의 구문 구조가 문맥 없는 [1][2]문법에 의해 적절하게 기술될 수 있다는 가설에 대한 증거를 제공했다.동시에, 맥락에 민감한 문법에 대한 촘스키 계층의 다음 단계로 가는 단계는 불필요하고 바람직하지 않은 것으로 보였다.자연어 구문의 적절한 기술에 필요한 정확한 형식적 힘을 정확히 지적하기 위해, 아라빈드 조시는 "문맥이 없는 문법(및 관련 언어)"[3]보다 약간 더 강력한 문법(및 관련 언어)을 특징지었다.그는 이러한 문법을 경미한 문맥에 민감한 문법이라고 불렀고 관련 언어들은 경미한 문맥에 민감한 언어라고 불렀다.

경미한 문맥에 민감한 문법에 대한 조시의 특성화는 나무접합문법(TAG)에 대한 그의 연구에 치우쳤다.하지만, 그의 학생 Vijay Shanker와 David Weir와 함께, Joshi는 생성된 문자열 언어 측면에서 TAG가 독립적으로 도입된 머리 문법(HG)[4]과 동등하다는 것을 곧 발견했습니다.그 후 선형 색인 문법([5]LIG)과 조합 범주 문법(CCG)[6]에 대한 두 가지 유사한 동등성 결과가 뒤따랐다. 이 결과는 경미한 문맥 민감도의 개념이 매우 일반적인 것이며 특정 형식주의에 얽매이지 않는다는 것을 보여주었다.

TAG와 동등한 형식은 LCFRS([7][8]Linear Context-Free Rewriting System)의 도입으로 일반화되었습니다.이러한 문법은 문맥이 없는 언어와 문맥에 민감한 언어 사이에서 문자열 언어의 무한 계층을 정의하며, 계층 하단의[clarification needed] TAG 등가 형식주의에 의해 생성된 언어를 사용합니다.LCFRS와 독립적으로 그리고 거의 동시에 히로유키 세키 등은 다중 문맥 자유 문법(MCFG)[9]의 본질적으로 동일한 형식주의를 제안했다.LCFRS/MCFG는 경미한 문맥에 민감한 문법을 지정하는 가장 일반적인 형식주의로 간주되기도 합니다.다만, 복수의 저자에 의하면, TAG등가형식의 특징적인 속성 중 일부는 LCFRS/[10]MCFG에 의해서 보존되지 않고, 경미한 컨텍스트 감도의 특징적인 속성을 가지고 있지만, LCFRS/MCFG에 [11]의해서 생성되지 않는 언어도 있습니다.

최근 몇 년 동안 TAG와 동등한 형식을 적절히 포함하지만 제한되지 않은 LCFRS/MCFG 계층에 적절히 포함되는 문법의 클래스를 정의하는 잘 내포된 선형 컨텍스트 프리 재작성 시스템/멀티 컨텍스트 프리 [10][12]문법의 제한된 클래스에 대한 관심이 높아지고 있습니다.

특성화

주제에 대한 상당한 양의 연구에도 불구하고, 경미한 문맥 감도의 공식적 정의는 일반적으로 받아들여지지 않는다.

Joshi의 [3]원래 특징에 따르면, 경미한 문맥에 민감한 문법의 클래스는 다음과 같은 특성을 가져야 한다.

  1. 제한된 교차 종속성
  2. 일정한 성장
  3. 다항식 해석

이와 더불어 경미한 문맥에 민감한 문법의 모든 클래스는 문맥이 없는 모든 언어를 생성할 수 있어야 한다는 것을 이해한다.

조시의 성격은 정식 정의가 아니다.그는 [3]다음과 같이 말한다.

조건 1과 조건 3은 문법에 따라 다르며 조건 2는 언어에 따라 다르므로 지금까지보다 훨씬 정확하게 조건 1을 지정해야 합니다.

다른 저자들은 경미한 문맥-감도의 대체적 특성화를 제안했는데, 그 중 일부는 형식적 정의의 형태를 취한다.예를 들어 Laura[13] Kallmeyer는 조시의 특성화에서처럼 문법의 클래스가 아닌 언어의 클래스 속성으로 정의되어야 한다는 관점을 가지고 있다.이러한 언어 기반의 정의는 조시와는 다른 개념으로 이어진다.

크로스 시리얼 의존관계

교차직렬의존성이라는 용어는 특정한 특징적인 어순 패턴, 특히 네덜란드어와 스위스어의 [2]하위[1] 절에서 관찰되는 동사-인수 패턴을 가리킨다.이것들은 자연어의 문맥적 자유에 반하는 데 사용될 수 있는 바로 그 패턴들이다. 따라서 교차직렬의존성을 모델링하기 위해 약간의 문맥에 민감한 문법을 필요로 하는 것은 이러한 문법이 문맥이 없는 문법보다 더 강력해야 한다는 것을 의미한다.

Kallmeyer는[13] 복사 언어를 생성하는 기능과 교차 시리얼 의존 관계를 모델링하는 기능을 식별합니다.

최대 몇 개의 바인드(bound)를 포함하여 w의 두 개 이상의 복사본으로 일반화합니다.이러한 언어는 문맥이 없는 언어가 아니며 펌핑 보조항목을 사용하여 표시할 수 있습니다.

지속적인 성장

언어 내의 모든 문자열이 다음 짧은 문자열보다 최대 (언어 고유의) 상수만큼 길면 정식 언어는 지속적으로 성장합니다.일부 저자들은 자연 언어의 특정 현상이 [14]상수에 의해 제한될 수 없는 성장을 보여준다고 주장하지만, 이 속성을 위반하는 언어는 종종 인간의 능력 밖의 것으로 여겨진다.

대부분의 경미한 문맥에 민감한 문법 형식(특히 LCFRS/MCFG)은 실제로 [7]반직선성이라고 불리는 지속적인 성장보다 더 강한 속성을 충족합니다.Parikh-mapping(문자열에서 기호의 상대적인 위치를 "잊어버리고" 효과적으로 단어의 가방으로 취급하는 매핑) 아래의 이미지가 정규 언어라면 언어는 반직선적입니다.모든 반선형 언어는 지속적으로 성장하지만, 지속적으로 성장한 모든 언어가 [11]반선형인 것은 아니다.

다항식 해석

문법형식은 결정론적 다항식 시간에 구성원 문제를 해결할 수 있다면 다항식 해석을 갖는다고 한다.이것은 형식주의로 쓰여진 문법 G와 문자열 w가 주어진다면 w가 G에 의해 생성되는지 여부, 즉 w가 G에 따라 "문법적"인지 여부를 결정하는 문제이다.이 문제의 시간 복잡도는 G와 w의 합계로 측정된다.

언어 클래스의 속성으로서의 경미한 문맥 감도에 대한 견해에서 다항식 해석은 언어 멤버쉽 문제를 언급합니다.이것은 고정 언어 L에 대해 특정 문자열 w가 L에 속하는지 여부를 결정하는 문제입니다.이 문제의 시간 복잡도는 w의 길이로 측정되며 L을 어떻게 지정하는지에 대한 질문은 무시됩니다.

다항식 파싱에 대한 두 가지 이해는 실제 적용의 경우 문장이 문법적인지 여부뿐만 아니라 문법이 문장에 할당하는 구문 구조에도 관심이 있다는 점에서 이상화라는 점에 유의하십시오.

형식주의

오랜 세월 동안 조시가 제시한 특징의 일부 또는 전부를 만족시키는 많은 문법 형식주의가 도입되었다.이들 중 일부는 이 문서에서 설명하지 않은 대체 자동 기반 특성화를 가지고 있다. 예를 들어, 트리 결합 문법에 의해 생성된 언어는 내장된 푸시다운 자동화에 의해 특징지어질 수 있다.

TAG와 동등한 형식

일반 LCFRS/MCFG와 동등한 형식

충분히 테스트된 LCFRS/MCFG와 동등한 형식

  • 중복되지 않는 매크로 문법[20]
  • Coupled Context-Free Grammars(CCFG)[21]
  • 콘텍스트가 필요 없는 리니어 리라이트[12] 시스템 탑재
  • 문맥이 없는 다중 문법을[10] 잘 내포

형식주의 간의 관계

리니어 콘텍스트 프리 리라이트 시스템/멀티 콘텍스트 프리 그래머는 팬아웃과 [22]랭크라고 불리는 2개의 문법 고유의 파라미터에 관해 2차원 생성 파워 계층을 형성합니다.보다 정확하게는 팬아웃 f가 1이고 랭크 r이 3인 LCFRS/MCFG가 생성하는 언어 클래스 및 랭크 r과 팬아웃 f가 1인 LCFRS/MCFG가 생성하는 언어 클래스에 적절하게 포함됩니다.잘 네스트된 경우 이 계층은 팬아웃에 관해 1차원 계층으로 축소됩니다.이는 잘 네스트된 모든 LCFRS/MCFG를 동일한 팬아웃과 [10][12]랭크2를 가진 동등한 잘 네스트된 LCFRS/MCFG로 변환할 수 있기 때문입니다.LCFRS/MCFG 계층 내에서는 문맥이 없는 언어를 팬아웃1의 문법으로 특징지을 수 있습니다.이 팬아웃의 경우 일반 문법과 잘 네스트된 문법의 차이는 없습니다.TAG와 동등한 형식은 팬아웃2의 LCFRS/MCFG를 충분히 네스트한 것으로 특징지을 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b 리니 위브레츠."문맥이 없는 구문의 구조 문법의 약점"Ger de Haan, Mieke Trommelen 및 Wim Zonneveld 편집자, Van periferie naar kern, 81~99페이지.네덜란드 도르드레흐트, 포리스, 1984년
  2. ^ a b 스튜어트 M.쉬버.'문맥에 대한 증거-자연어의 자유'언어학과 철학, 8(3): 333-343, 1985.
  3. ^ a b c d 아라빈드 K조시 "문법 옆 나무: 적절한 구조 설명을 제공하려면 컨텍스트 감도가 어느 정도 필요합니까?"데이비드 R에서.다우티, 라우리 카트튠, 아놀드 M. 즈위키, 자연어 해석, 206~250쪽 편집자.케임브리지 대학 출판부, 1985.
  4. ^ 데이비드 J.Weir, K.비제이 생커와 아라빈드 K.조시 "나무와 머리 문법의 관계"컴퓨터 언어학 협회(ACL) 제24회 연차총회 의사록(67~74페이지), 미국 뉴욕, 1986.
  5. ^ K. 비제이 생커"문법 인접한 나무 연구"1987년 미국 필라델피아 펜실베니아 대학 박사 학위 논문
  6. ^ a b 데이비드 J.위어와 아라빈드 K.조시 "비교적 범주형 문법: 생성력과 선형 문맥 자유 개서 체계와의 관계"컴퓨터 언어학 협회(ACL) 제26회 연차총회 의사록(Presidings of the Association of Computational Languageology, 278–285) (미국 버팔로, 1988).
  7. ^ a b c d K. 비제이 생커, 데이비드 J.위어, 그리고 아라빈드 K.「다양한 문법적 형식주의에 의한 구조 기술」.컴퓨터 언어학 협회(ACL) 제25회 연차총회(Proceedings of the Association of Computational Languageology, 104–111) (Stanford, CA, USA, 1987).
  8. ^ a b 데이비드 J.Weir. "문맥에 따라 문맥에 따라 문법에 맞는 문법의 형식화"박사학위 논문, 펜실베니아 대학, 필라델피아, 1988년.
  9. ^ a b 세키 히로유키, 마츠무라 타카시, 후지이 마모루, 카사미 타다오.'다양한 문맥이 없는 문법에 대하여'이론 컴퓨터 공학, 88(2):191~229, 1991.
  10. ^ a b c d 가나자와 마코토"여러 문맥이 없는 언어를 잘 네스트하기 위한 펌핑 보조법"언어이론의 발전.제13회 국제회의, DLT 2009, 독일 슈투트가르트, 2009년 6월 30일~7월 3일. 컴퓨터 과학 강의 노트 제5583권, 312~325쪽, 2009년.
  11. ^ a b 로라 칼마이어."경미한 컨텍스트에 민감한 비선형 개서에 대하여"언어와 계산에 관한 연구, 8(4): 341~363, 2010.
  12. ^ a b c 카를로스 고메즈 로드리게스, 마르코 쿨만, 조르지오 사타."잘 중첩된 선형 컨텍스트 없는 개서 시스템의 효율적인 구문 분석"인간 언어 기술 절차: 컴퓨터 언어학 협회(NAACL) 북미 지부 2010년 연차 총회, 276~284쪽, 미국 로스앤젤레스, 2010년.
  13. ^ a b 로라 칼마이어.문맥을 벗어난 구문 분석 - 문법이 필요 없습니다.Springer, 2010년
  14. ^ 옌스 미카엘리스와 마르쿠스 크라흐트."통사적[dead link] 불변량으로서의 반직선성"컴퓨터 언어학의 논리적 측면. 제1회 국제회의, LACL 1996, 프랑스 낸시, 1996년 9월 23일~25일 컴퓨터 과학 강의 노트 제1328권, 329-345페이지, Selected Papers.스프링거, 1997년
  15. ^ 칼 J. 폴라드"범용어 구조 문법, 머리 문법, 자연어"1984년 스탠퍼드 대학교 박사 학위 논문.
  16. ^ 켈리 로치 "머리 문법의 공식 특성"알렉시스 매너스터-레이머에서, 언어의 수학 편집자, 293-347페이지.존 벤자민스, 1987년
  17. ^ 제럴드 가즈다르"인덱스된 문법의 자연어에 대한 적용성"Uwe Reyle과 Christian Rohrer, 편집자, 자연어 해석과 언어 이론, 69-94페이지.D. 레이델, 1987년
  18. ^ 옌스 미카엘리스."파생적 미니멀리즘은 문맥에 약간 민감하다"컴퓨터 언어학의 논리적 측면, 제3차 국제회의, LACL 1998, 프랑스 그르노블, 1998년 12월 14-16일, Selected Papers, 2014년 컴퓨터 과학 강의 노트, 179-198페이지.스프링거, 1998년
  19. ^ 피에르 불리에."Range Connection Grammars.Harry C에서.편집자인 Bunt, John Carroll 및 Giorgio Satta, Parsing Technology의 New Developments in Parsing Technology, Text, Speech and Language Technology, 269-289페이지.Kluwer Academic Publishers, 2004.
  20. ^ 마이클 J.피셔."매크로라이크 프로덕션이 있는 그래머"제9회 스위칭 및 오토마타 이론에 관한 연례 심포지엄, 131-142페이지, NY, USA, 1968.
  21. ^ 귄터 호츠와 기젤라 피치."커플링-콘텍스트가 없는 언어의 해석에 대하여"이론 컴퓨터 과학, 161(1~2):205~233, 1996.
  22. ^ 오웬 램보우와 조르지오 사타."병렬 개서를 위한 2차원 계층"기술 보고서 IRCS-94-02, 미국 필라델피아 펜실베니아 대학, 1994.