형식 언어 (2) - 언어

형식 언어 (2) - 언어

형식 언어(formal language)는 규칙적인 구조와 규칙에 따라 생성된 문자열의 집합입니다.
이러한 규칙은 문법(grammar)이라고도 하며, 형식 언어는 이러한 문법에 따라 생성된 문자열들의 집합으로 구성됩니다.

오늘 설명할 언어는 의미(Semantic)의 개념은 포함하지 않습니다
L은 언어를 뜻합니다

두 언어의 합집합

두 언어의 접속

L의 거듭 제곱

• 즉 거듭 제곱한 만큼 뽑는 경우의 수 문제입니다

클리니 클로저, 포지티브 클로저

유도

• 정의된 문법으로부터 어떤 언어가 생성되는지, 언어가 문법에 맞는지를 알기 위해 유도를 설명한다
  
• α, β 등 그리스어 소문자는 문법 기호로 구성된 문자열을 나타냅니다.
  
• 한 번 이상의 유도는 *가 아니라 +로 위에 것을 바꿔야 합니다
  
• 유도라는 표현은 주체적인 표협입니다
  

실습 : 예제 3-4에서 0, 0000, 001100 등이 허용

되는지 유도하라

실습 : id + (id * id)가 [예제 3-5]의 문법에 의해 생성되는 문자열인지 확인