문맥이 없는 언어

Context-free language

형식 언어 이론에서, 문맥 자유 언어(CFL)는 문맥 자유 문법(CFG)에 의해 생성된 언어입니다.

문맥 자유 언어는 프로그래밍 언어에서 많은 응용 프로그램을 가지고 있으며, 특히 대부분의 산술 표현식은 문맥 자유 문법에 의해 생성됩니다.

배경

문맥 자유 문법

문맥이 없는 다른 문법은 동일한 문맥이 없는 언어를 생성할 수 있습니다.언어의 본질적 특성은 언어를 기술하는 여러 문법을 비교함으로써 특정 문법의 외적 특성과 구별될 수 있다.

오토마타

콘텍스트가 없는 모든 언어의 집합은 푸시다운 오토마타에 의해 받아들여지는 언어 집합과 동일하기 때문에 이러한 언어들은 해석에 적합하게 됩니다.또, 소정의 CFG에 대해서, 문법(및 대응하는 언어)을 위해서 푸시다운 오토마톤을 생성하는 직접적인 방법이 있습니다만, 반대로 가는 것(오토마톤이 주어지는 문법을 생성하는 것)은 직접적이지 않습니다.

문맥이 없는 언어의 로는 L { b n : } { L b 1.이 언어는 공백이 아닌 모든 짝수 문자열의 언어이며 첫 번째 절반 전체가 a이고 나머지 절반은 b의 언어입니다.L S S bb {\ S로 생성됩니다.이 언어는 규칙적이지 않다.푸시다운 M= ( { , 1, qf}, { } , { , , ,, z , { q f ) { M ( \ { _ 0 , , 、 { _ { f } \, \ , \ } ) 。

명확한 CFL은 모든 CFL의 적절한 서브셋입니다.본질적으로 애매한 CFL이 존재합니다.{오빠 bmcmd와 n, m>0}{\displaystyle\와 같이{a^{n}b^{m}c^{m}d^{n}n,m&gt의{오빠 b와 cmdmn, m>0}{\displaystyle\와 같이{a^{n}b^{n}c^{m}d^{m}n,m&gt을 가진 본질적으로 모호한 캐나다 풋볼 리그의 예입니다;0\}};0\}}. 이 세트 이후 문맥 자유는 두명의 노동 조합 문맥 자유 la.nguages은항상 컨텍스트가 필요 없습니다.그러나 (컨텍스트가 없는) 서브셋 b c > \ { b c d n>에서 문자열을 명확하게 해석할 수 있는 방법은 없습니다.이것은 이 두 언어의 [1]교집합입니다.

다이크어

올바르게 일치하는 모든 괄호 언어 S ( ) \ S \ SS ~ ( ) ~ \ 에 의해 생성됩니다.

특성.

문맥 없는 해석

이 언어의 문맥이 없는 특성으로 인해 푸시다운 자동화를 사용하여 해석하는 것이 간단해집니다.

멤버십 문제의 예를 특정합니다.즉, w w L서 L L 특정 GG에 의해 생성된 언어인지 여부를 확인합니다.촘스키 정규 형식 문법에 대한 문맥 없는 인식은 Leslie G. Valiant에 의해 부울 행렬 곱셈으로 환원될 수 있다는 것을 보여주었고, 따라서 복잡도 상한인 O(n2.3728639)[2][note 2]를 상속받았다.반대로, Lillian Lee는 O3−ε(n) 부울 행렬 곱셈이 O3−3ε(n) CFG 해석으로 환원될 수 있음을 보여주었고,[3] 따라서 후자에 대한 일종의 하한을 확립했습니다.

문맥이 없는 언어의 실용적인 사용은 또한 문법이 주어진 문자열과 연관된 구조를 나타내는 파생 트리를 생성해야 한다.이 트리를 생성하는 프로세스를 구문 분석이라고 합니다.기존의 파서는 해석되는 문자열의 크기가 세제곱인 시간 복잡도를 가집니다.

형식적으로 모든 컨텍스트프리 언어 세트는 Pushdown Automata(PDA)에 의해 받아들여지는 언어 세트와 동일합니다.문맥이 없는 언어의 파서 알고리즘에는 CYK 알고리즘 얼리 알고리즘이 있습니다.

컨텍스트 프리 언어의 특별한 서브클래스는 결정론적 컨텍스트 프리 언어이며, 결정론적 푸시다운 오토마톤에 의해 받아들여지는 언어 세트로 정의되며 LR([4]k) 파서에 의해 해석될 수 있다.

문법 및 파서의 대체 접근법으로서 표현 문법의 해석도 참조해 주세요.

클로즈

문맥이 없는 언어의 클래스는 다음의 조작으로 닫힙니다.즉, L과 P가 컨텍스트프리 언어인 경우 다음 언어도 컨텍스트프리 언어입니다

  • L[5] P의 결합 L P L \ P
  • L[6] 반전
  • L[5] P의 연결 LP(\ L P
  • L클린[5] 별 L { { * }
  • () \ \ (L ) ism 、 \\}
  • L의 이미지 ( L ) ( \ \ varphi { - ( L ) 1( \ ^ { - )
  • L의 순환 이동({ v L { \ { \ L \[9]} )
  • L의 접두사 폐쇄(L에서 [10]문자열의 모든 접두사 집합)
  • 정규 언어[11] R에 의한 L의 몫 L/R

교차로, 보완 및 차이에 따른 미폐쇄

문맥이 없는 언어는 교차로에서도 닫히지 않습니다.는 언어 A { b , n 0 { A = \ { ^ { } { } {m , \ 0\ } 및 { n c m , b } 0 { } { b } styledisplaystylanguel }를 취함으로써 알 수 있습니다.이들의 교차는 A B { n n 0{ A B=\{ b n 0이다. 이는 맥락을 초월한 언어를 위한 펌핑에 의해 자유로 나타날 수 있다.그 결과 문맥이 없는 언어는 보완 하에 폐쇄될 수 없으며, A와 B언어에서 이들의 교차는 다음과 같이 결합과 보완으로 표현될 수 있다. B A display B { { \ { \ B ={ \ { A }, 문맥이 없는 언어는 차이에 의해 표현될 수 있기 에 차이에 의해 닫힐 수 없습니다

단, L이 컨텍스트프리 언어이고 D가 정규 언어인 경우 L의 D L D L L 모두 컨텍스트프리 [13]언어입니다.

결정 가능성

공식 언어 이론에서는 보통 정규 언어에 대한 질문은 결정될 수 있지만, 문맥이 없는 언어에 대한 질문은 종종 그렇지 않습니다.그러한 언어가 유한한지는 알 수 있지만, 그것이 모든 가능한 문자열을 포함하고 있는지, 규칙적인지, 모호하지 않은지, 또는 다른 문법을 가진 언어와 동등한지는 판단할 수 없다.

다음 문제는 임의로 주어진 컨텍스트프리 문법A 및 B에 대해 결정할 수 없습니다.

  • 등가: () ( { L)=[14]
  • 불협화음: ( )b L ( ) L ( B ) {\display ( \ L ( ) \ L ( B ) = \ }[15] 단, 컨텍스트가 없는 언어와 일반 언어의 교집합은 [16][17]문맥이 없기 때문에, B가 정규 문법이 되는 문제의 변형을 판별할 수 있습니다(「불가능성」을 참조).
  • Containment: ( )L ( ( [18]。B가 정규 문법인 문제의 변종은 판별할 [citation needed]수 있지만 A가 정규 문법은 일반적으로 판별할 [19]수 없습니다.
  • 유니버설리티: ( A ) ( \ L ( A ) = \ { * }[20]
  • 규칙성: L (\(A 정규 [21]입니까?
  • 모호성: L( A) \ L ( )의 모든 문법이 [22]모호합니까?

콘텍스트가 없는 임의의 언어에서는 다음 문제를 해결할 수 있습니다.

  • 공백: 문맥이 없는 문법 A가 주어졌을 때L ( ) { L ( A )= \ }[23]입니까?
  • 정밀도: 문맥이 없는 문법 A가 주어졌을 때L () \ L ( [24]}은 합니까?
  • 멤버십: 문맥이 없는 문법 G와 ww를 지정하면 L ( ) \ w \ L ( ) :멤버십 문제에 대한 효율적인 다항식 시간 알고리즘은 CYK 알고리즘과 얼리 알고리즘입니다.

Hopcroft, Motwani,[25] Ullman(2003)에 따르면, 컨텍스트가 없는 언어의 많은 기본적인 폐쇄성과 (불)결핍성 특성은 1961년 Bar-Hillel, Perles 및 Shamir의[26] 논문에서 나타났다.

문맥이 없는 언어

{ a b > { \ { ^ { } { } { n } d{ n}n 0 \ }은 컨텍스트 의존 언어이지만 이 [27]언어를 생성하는 컨텍스트프리 문법은 존재하지 않습니다.문맥에 구애받지 않는 언어도 있습니다.주어진 언어가 문맥이 없는 것이 아님을 증명하기 위해, 사람들은 맥락을 모르는[26] 언어나 오그덴의 레마파릭의 [28]정리 같은 많은 다른 방법들을 위해 펌핑 레마를 사용할 수 있다.

메모들

  1. ^ \ \displaystyle 의 인수 및 결과: s t t e 1, r e d, pp ) ( 2, h) ( \ \ displaystyle ( \{_ { , { ) = ( \ { } ) } ) 。
  2. ^ Valiant의 논문에서 O(n2.81)는 당시 가장 잘 알려진 상한이었다.그 후의 대폭적인 향상에 대해서는, 매트릭스 곱셈 #계산 복잡도를 참조해 주세요.
  3. ^ 언어 A의 문맥이 없는 문법은 S를 시작 기호로 하여 다음 생산 규칙에 의해 지정됩니다.SSc aTb ε, TaTb ε.B의 문법은 비슷하다.

레퍼런스

  1. ^ 홉크로프트 & 울먼 1979, 100페이지, 정리 4.7.
  2. ^ Valiant, Leslie G. (April 1975). "General context-free recognition in less than cubic time". Journal of Computer and System Sciences. 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8.
  3. ^ Lee, Lillian (January 2002). "Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication" (PDF). J ACM. 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242. S2CID 1243491.
  4. ^ Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
  5. ^ a b c Hopcroft & Ullman 1979, 131, 정리 6.1의 결과.
  6. ^ Hopcroft & Ullman 1979, 페이지 142, 연습 6.4d.
  7. ^ Hopcroft & Ullman 1979, 131-132쪽, 정리 6.2의 결과.
  8. ^ 홉크로프트 & 울먼 1979, 132쪽, 정리 6.3.
  9. ^ Hopcroft & Ullman 1979, 페이지 142-144, 연습 6.4c.
  10. ^ Hopcroft & Ullman 1979, 페이지 142, 연습 6.4b.
  11. ^ Hopcroft & Ullman 1979, 페이지 142, 연습 6.4a.
  12. ^ Stephen Scheinberg (1960). "Note on the Boolean Properties of Context Free Languages" (PDF). Information and Control. 3 (4): 372–375. doi:10.1016/s0019-9958(60)90965-7.
  13. ^ Beigel, Richard; Gasarch, William. "A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's" (PDF). University of Maryland Department of Computer Science. Retrieved June 6, 2020.
  14. ^ Hopcroft & Ullman 1979, 페이지 203, 정리 8.12 (1).
  15. ^ 홉크로프트 & 울먼 1979, 202쪽, 정리 8.10.
  16. ^ 살로마아(1973), 59페이지, 정리 6.7
  17. ^ 홉크로프트 & 울먼 1979, 135페이지, 정리 6.5.
  18. ^ Hopcroft & Ullman 1979, 페이지 203, 정리 8.12(2)
  19. ^ 홉크로프트 & 울먼 1979, 페이지 203, 정리 8.12(4)
  20. ^ 홉크로프트 & 울먼 1979, 페이지 203, 정리 8.11
  21. ^ 홉크로프트 & 울먼 1979, 205쪽, 정리 8.15
  22. ^ 홉크로프트 & 울먼 1979, 206, 정리 8.16
  23. ^ 홉크로프트 & 울먼 1979, 137페이지, 정리 6.6(a)
  24. ^ 홉크로프트 & 울먼 1979, 137페이지, 정리 6.6(b)
  25. ^ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison Wesley. 여기: 7.6장, 304쪽, 9.7장, 411쪽
  26. ^ a b Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). "On Formal Properties of Simple Phrase-Structure Grammars". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung. 14 (2): 143–172.
  27. ^ 홉크로프트 & 울먼 1979년
  28. ^ "How to prove that a language is not context-free?".

인용된 작품

추가 정보