교대(공식언어이론)

Alternation (formal language theory)

형식 언어 이론과 패턴 매칭에서 교대란 두 문자열의 조합 또는 문자열 집합을 설명하는 두 패턴의 논리적 분리를 의미한다.

정규 언어는 교대로 폐쇄되는데, 이는 두 정규 언어의 교체가 다시 정규 언어라는 것을 의미한다.[1] 정규 표현식의 구현에서 대체는 종종 결합이 일치하는 두 언어의 표현식을 연결하는 세로 막대로 표현되는 반면,[2][3] 더 이론적인 연구에서는 이 목적을 위해 더하기 기호를 대신 사용할 수 있다.[1] 유한 오토마타 자체에 의해 정의된 두 개의 정규 언어의 결합을 위한 유한 오토마타를 구성하는 능력은 오토마타에 의해 정의되는 정규 언어와 정규 표현에 의해 정의되는 정규 언어 사이의 동등성에 중심적이다.[4]

교대로 폐쇄되는 다른 종류의 언어에는 문맥 없는 언어와 재귀 언어가 포함된다. 교체를 위한 세로 막대 표기법은 GROPTOL 언어와 일부 다른 언어에서 사용된다. 공식언어이론에서 교번법은 상호보완적이고 연상적이다. 이는 일반적으로 패턴 매칭 언어에 사용되는 대체 언어의 형태에는 해당 언어에서 일치를 수행하는 부작용 때문에 해당되지 않는다.

참조

  1. ^ a b Linz, Peter (2006). "Theorem 4.1". An Introduction to Formal Languages and Automata. Jones & Bartlett Learning. pp. 100–101. ISBN 9780763737986.
  2. ^ Fitzgerald, Michael (2012). "Alternation". Introducing Regular Expressions: Unraveling Regular Expressions, Step-by-Step. O'Reilly Media. pp. 43–45. ISBN 9781449338893.
  3. ^ "Alternation with The Vertical Bar". regular-expressions.info. Retrieved 2021-11-11.
  4. ^ Cooper, Keith; Torczon, Linda (2011). Engineering a Compiler (2nd ed.). Elsevier. p. 41. ISBN 9780080916613.

참고 문헌 목록

  • 존 E. 홉크로프트와 제프리 D. Ulman, Automata 이론 소개, 언어 및 계산, Addison-Wesley 출판, Reading Massachusetts, 1979. ISBN 0-201-02988-X.
Stub icon

이 콤비네이터 관련 기사는 단조롭다. 위키피디아를 확장하여 도울 수 있다.