동등성(공식 언어)

Equivalence (formal languages)

공식 언어 이론에서 두 문자의 등가성이 약하다는 것은 같은 문자열을 생성한다는 것을 의미한다. 즉, 그들이 생성하는 공식 언어가 같다는 것이다.컴파일러 이론에서 그 개념은 강한(또는 구조적인) 등가성과 구별된다. 이는 추가적으로 두 파스 트리가[clarification needed] 양쪽 모두에 동일한 의미 해석을 할당할 수 있다는 점에서 상당히 유사하다는 것을 의미한다.[1]

Vijay-Shanker와 Weir(1994)는 [2]Linear Indexed Grammars, Combinative Categorial Grammars, Tree-adjection Grammars, Head Grammar가 모두 동일한 문자열 언어를 정의한다는 점에서 약하게 동등한 형식임을 입증한다.[clarification needed]

한편, 두 개의 그래마가 동일한 파생 트리 집합(또는 보다 일반적으로 동일한 추상적 통사적 물체 집합)을 생성하는 경우, 두 그래머는 강하게 동등하다.촘스키(1963년)[3]는 강한 동등성의 개념을 도입하고, 문법 형식주의를 비교할 때 강한 동등성만이 관련이 있다고 주장한다.코르나이와 풀럼(1990년)[4]과 밀러(1994)[5]는 서로 다른 형식에 의해 주어지는 통사적 분석 사이의 이형적 관계를 가능하게 하는 강한 동등성의 정제된 개념을 제공한다.요시나가,[6] 미야오, 츠지이(2002)는 어떤 LTAG 형식주의에도 강하게 동등한 HPSG가 있다는 증거를 제시한다.

문맥이 없는 문법 예제

왼쪽: 첫 번째 문법이 있는 "1+2*3" 문자열의 파스나무 중 하나.맞아, 그 줄에 두 번째 문법이 있는 유일한 파스 트리야.

예를 들어 Backus-Naur 형식으로 제공된 다음과 같은 두 가지 문맥 없는 그래머를 생각해 보십시오.[note 1]

<<expression> ::=<+><+><expression><-"><-"><-"><-"><*><*><*>< ">< ">< ">< ">< ">< ">< ">< ">< ">< ">< ">< ">< "><x><x><x><x><)"><)"><)"><)"><)"><)"><)"><)"?
<<expression> ::=<=><+><+><expression><-"><-">><>>< :><>><*><*> <*><term><term><term><term><term><term><term>< :><=> ::= "y" "1" "1" (expression)"

두 문법 모두 같은 문자열 집합인 viz를 생성한다. "x", "y", "z", "1", "2", "3", 연산자 "+", "-", "*", "/", 괄호 "("와 ")"에서 빌드할 수 있는 모든 산술적 표현 집합이다.그러나 두 번째 문법의 구체적인 구문 트리는 항상 통상적인 운영 순서를 반영하는 반면, 첫 번째 문법에서 나온 트리는 그럴 필요가 없다.

예시 문자열 "1+2*3"의 경우, 그림 오른쪽에는 두 번째 문법이 있는 고유한 파스 트리가 표시된다.[note 2] 이 트리를 수정 후 순서대로 평가하면 적절한 값인 7이 나온다.이와는 대조적으로 왼쪽 그림 부분은 첫 번째 문법과 함께 그 끈에 대한 파스 나무 중 하나를 보여준다; 그것을 수정 후 순서대로 평가하면 9가 나올 것이다.

두 번째 문법은 왼쪽 그림 부분에 해당하는 나무를 생성할 수 없는 반면 첫 번째 문법은 만들 수 있기 때문에 두 문법 모두 강하게 동등하지 않다.

생성능력

언어학에서 문법의 약한 생성능력은 문법에 의해 생성되는 모든 문자열의 집합으로 정의되는 반면,[note 3] 문법의 강력한 생성능력은 문법에 의해 생성되는 "구조적 서술"[note 4]의 집합을 말한다.[7]결과적으로, 두 개의 문법은 약한 생성 용량이 일치하면 약하게 등가물로 간주된다; 강한 등가성과 유사하다.생성능력의 개념은 1963년 노암 촘스키에 의해 도입되었다.[3][7]

메모들

  1. ^ 시작 기호가 "<<<<<>>"로 되어 있다.
  2. ^ <표현>, <용어>, <인자>에 각각 'E', 'T', 'F'라는 약어를 사용한다.
  3. ^ 컨텍스트 없는 문법: 공식 정의는 컨텍스트 없는 문법#컨텍스트 없는 언어를 참조하십시오.
  4. ^ 문맥이 없는 그래머의 경우: 구체적인 구문 트리

참조

  1. ^ Stefano Crespi Reghizzi (2009). Formal Languages and Compilation. Springer. p. 57. ISBN 978-1-84882-049-4.
  2. ^ Vijay-Shanker, K. and Weir, David J. (1994). "The Equivalence of Four Extensions of Context-Free Grammars". Mathematical Systems Theory. 27 (6): 511–546. doi:10.1007/BF01191624. S2CID 12336597.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  3. ^ a b Noam Chomsky (1963). "Formal properties of grammar". In R.D. Luce; R.R. Bush; E. Galanter (eds.). Handbook of Mathematical Psychology. Vol. II. New York: Wiley. pp. 323—418.
  4. ^ Kornai, A.와 Pullum, G. K. 1990.구문 구조의 X-bar 이론.언어, 66:24-50.
  5. ^ 밀러, 필립 H. 1999.강력한 생성 용량.CSLI 간행물.
  6. ^ "Yoshinaga, N., Miyao Y., and Tsujii, J. 2002. A formal proof of strong equivalence for a grammar conversion from LTAG to HPSG-style. In the Proceedings of the TAG+6 Workshop:187-192. Venice, Italy" (PDF). Archived from the original (PDF) on 2011-08-28. Retrieved 2012-02-05.
  7. ^ a b Emmon Bach; Philip Miller (2003). "Generative Capacity" (PDF). In William J. Frawley (ed.). International Encyclopedia of Linguistics (2nd ed.). Oxford University Press. doi:10.1093/acref/9780195139778.001.0001. ISBN 9780195139778.