결정론적 문맥 자유 언어

Deterministic context-free language

형식 언어 이론에서 결정론적 문맥 자유 언어(DCFL)는 문맥 자유 언어의 적절한 부분 집합이다.이들은 결정론적 푸시다운 오토마톤에 의해 받아들여질 수 있는 문맥이 없는 언어입니다.DCFL은 항상 모호하지 않습니다.즉, 모호하지 않은 문법을 인정합니다.확정적이지 않은 CFL이 존재하기 때문에 DCFL은 명확하지 않은 CFL의 적절한 서브셋을 형성합니다.

DCFL은 선형 시간에 구문 분석할 수 있기 때문에 매우 실용적이며, 다양한 제한된 형태의 DCFG는 단순한 실용적인 파서를 허용합니다.따라서 컴퓨터 과학 전반에 걸쳐 널리 사용되고 있습니다.

묘사

DCFL의 개념은 결정론적 푸시다운 오토마톤(DPDA)과 밀접하게 관련되어 있습니다.푸쉬다운 오토매톤의 언어 파워가 우리가 결정론적으로 만드는 경우로 감소한다. 푸쉬다운 오토매톤은 다른 상태 전이 대안들 사이에서 선택할 수 없게 되고 그 결과 모든 문맥이 [1]없는 언어를 인식할 수 없게 된다.명확한 문법이 반드시 DCFL을 생성하는 것은 아닙니다.예를 들어, 알파벳 0과 1의 짝수 길이 회문 언어는 명확한 문맥이 없는 문법 S → 0S0 1S1 µ을 가지고 있다. 이 언어의 임의의 문자열은 모든 문자를 먼저 읽지 않고 구문 분석할 수 없으며, 이는 푸시다운 자동화가 다른 가능성을 수용하기 위해 대체 상태 전환을 시도해야 한다는 것을 의미한다.반파싱 [2]문자열의 ible 길이입니다.

특성.

결정론적 문맥이 없는 언어는 다항식 시간과 O(log2 n) 공간에서 결정론적 튜링 기계에 의해 인식될 수 있다. 결과적으로 DCFL은 복잡도 클래스 [3]SC의 서브셋이다.

결정론적 컨텍스트프리 언어 세트는 다음 조작으로 [4]닫힙니다.

  • 보충하다
  • 역동형사상
  • 정규 언어의 오른쪽 지수
  • pre: pre ( \ L)는L \ L에 적절한 프레픽스를 가진 모든 문자열의 서브셋입니다.
  • min: min ( \ L)는 L\ L l in in in프리픽스가없는모든스트링의서브셋입니다.
  • max: max ( \ L)는 L\ L \ l in in의 긴 문자열 프리픽스가 아닌 모든 문자열의 서브셋입니다.

결정론적 문맥 자유 언어 집합은 다음 [4]작업에서는 닫히지 않습니다.

중요성

이 클래스의 언어는 비결정론적 문맥이 없는 언어보다 훨씬 효율적으로 구문 분석할 수 있기 때문에 컴퓨터 과학에서 실질적으로 매우 중요합니다.결정론적 푸시다운 오토마톤의 프로그램 복잡성과 실행 시간은 비결정론적 오토마톤보다 훨씬 적다.단순 구현에서는 비결정적 단계가 발생할 때마다 후자가 스택의 복사본을 만들어야 합니다.컨텍스트 프리 언어로 멤버십을 테스트하는 가장 잘 알려진 알고리즘은 Valiant의 알고리즘으로 O를 취합니다.n2.378) 시간, 장소n는 문자열의 길이입니다.한편, 결정론적 문맥이 없는 언어는 O로 받아들여질 수 있다.nLR()k[5] 파서에 의한 시각.많은 컴퓨터 언어가 이 클래스의 언어에 속하기 때문에 이것은 컴퓨터 언어 번역에 매우 중요합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 233.
  2. ^ Hopcroft, John; Rajeev Motwani; Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253.
  3. ^ Cook, Stephen A. (April 30 – May 2, 1979). "Deterministic CFL's are accepted simultaneously in polynomial time and log squared space". Proceedings of the eleventh annual ACM Symposium on Theory of Computing - STOC '79. Atlanta. pp. 338–345. doi:10.1145/800135.804426.
  4. ^ a b Hoogeboom, Hendrik; Engelfriet, Joost (2004). Formal Languages and Applications. Springer-Verlag Berlin Heidelberg. p. 128. ISBN 978-3-642-53554-3.
  5. ^ 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.