형식 언어

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

형식 언어는 유한한 종류의 문자로 이루어진 유한한 길이의 문자열의 집합을 말한다.

형식 언어는 수학, 논리학, 언어학, 정보 이론 등에서 사용하고 있으며, 또한 계산가능성 이론과 밀접하게 관련되어 있다.

정의[편집]

각 형식 언어에는 그 언어에서 사용하는 문자의 집합이 있으며, 그 집합은 무한할 수도 있다. 그 형식 언어에 속하는 문자열은 문자들로 이루어진 유한한 길이의 수열로 정의된다. 문자 집합을 \Sigma라고 정의했을 때, 그 문자들로 이루어진 모든 문자열의 집합은 \Sigma^*가 된다. 여기에서 별표는 클레이니 스타 연산자이다.

이 때, \Sigma 위에 존재하는 형식 언어 L\Sigma^*부분집합으로 정의된다.

형식 언어의 기술 방식[편집]

형식 언어는 특정한 문자열의 집합이기 때문에, 다음과 같은 방식을 이용해 형식 언어를 만들 수도 있다.

형식 언어의 연산[편집]

기존의 형식 언어를 결합하여 새로운 언어를 만들어 낼 수 있다. 두 형식 언어 L1L2가 있다고 하면, 다음과 같은 연산을 할 수 있다.

  • L1L2연쇄L1 의 문자열 vL2 의 문자열 w 를 연쇄시켜 만든 단어들의 집합이다. 표기: L_1\cdot L_2 또는 L_1 L_2.
  • L1L2교집합L1L2 에 동시에 속해 있는 문자열들의 집합이다. 표기 : L_1 \cap L_2\,.
  • L1L2합집합L1에 속하거나 L2 에 속하는 문자열들의 집합이다. 표기 : L_1 \cup L_2\, 또는 L_1 + L_2.
  • L1여집합L1 에 속하지 않는 문자열들의 집합이다.
  • 우상(右商: 오른쪽 몫)은 L2의 문자열 w 에 대하여 vwL1 에 속하도록 하는 문자열 v 의 집합이다. 표기 : L_1 / L_2.