정규 언어

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
촘스키 위계 클래스의 정규 언어

정규 언어(regular language), 합리적 언어(rational language)[1][2]이론 전산학, 형식 언어 이론에서 정규 표현식을 이용하여 표현할 수 있는 형식 언어이다.

정규 언어는 유한 오토마톤이 인지하는 언어로 정의할 수도 있다. 정규 표현식과 무한 오토마타의 등가성은 클레이니의 정리로 알려져 있다.[3] 촘스키 위계에서 정규 언어는 3형 문법(정규 문법)에 의해 생성되는 언어로 정의된다.

정규 언어는 입력 구문 분석(파싱)과 프로그래밍 언어 설계에 매우 유용하다.

기본 요소 정의[편집]

  • Φ은 공집합을 나타낸다.
  • ε은 집합을 나타낸다.
  • 각각의 a ∈ Σ (a는 Σ에 속함)에서 a (∈VT)는 집합 {a}를 나타낸다.

같이 보기[편집]

각주[편집]

  1. Ruslan Mitkov (2003). 《The Oxford Handbook of Computational Linguistics》. Oxford University Press. 754쪽. ISBN 978-0-19-927634-9. 
  2. Mark V. Lawson (2003). 《Finite Automata》. CRC Press. 98–103쪽. ISBN 978-1-58488-255-8. 
  3. Sheng Yu (1997). 〈Regular languages〉. Grzegorz Rozenberg and Arto Salomaa. 《Handbook of Formal Languages: Volume 1. Word, Language, Grammar》. Springer. 41쪽. ISBN 978-3-540-60420-4. 

외부 링크[편집]