형식 언어 (1) - 문자열

형식 언어 (1) 문자열

형식 언어(formal language)는 규칙적인 구조와 규칙에 따라 생성된 문자열의 집합입니다.
이러한 규칙은 문법(grammar)이라고도 하며, 형식 언어는 이러한 문법에 따라 생성된 문자열들의 집합으로 구성됩니다.
형식 언어는 컴퓨터 과학에서 중요한 개념으로, 프로그래밍 언어, 데이터베이스 쿼리 언어, 통신 프로토콜 등 다양한 분야에서 사용됩니다.

형식 언어는 종류에 따라 위의 4가지로 분류가 됩니다

형식 언어 정의

1. 알파벳 : 언어의 문장을 이루는 기본적인 기호

알파벳이란 공집합이 아닌 기호들의 유한 집합으로 시그마로 표시한다.

• 알파벳의 의미는 일반적인 프로그래밍 언어에서 사용하는 문자,기호의 집합이다

2. 문자열 : 알파벳에 대한 문자열은 알파벳에서 정의 된 기호들을 나열한 유한 수열

문자열은 언어 이론에서는 문장 또는 단어와 동의어로 사용 된다

문자열은 해당 언어에서 지원하는 알파벳(기호)로 이루어져 있다.

3. 문자열의 길이 : 문자열을 이루는 기호의 개수

• |w| : 어떤 문자열 w의 길이, w의 cardinality이라고 한다
  

4. 문자열의 접속 : 두 개의 문자열을 연결하여 새로운 문자열을 만드는 연산

• u·v는 문자열의 접속을 의미한다.
  

5. 공문자열(Empty String) : 문자열의 길이가 0인 문자열

• 엡실론으로 표기한다
• 어떤 문자열 u, v에 대하여 다음과 같은 속성을 가진다
  • 
    

6. 접두사(Prefix) : 문자열 w = uv일 때 u는 문자열 w의 접두사

• 진접두사(Proper prefix) : u가 공문자열(엡실론)이 아닌 접두사
• 접미사 : 문자열 w=uv에서 v를 문자열 w의 접미사
• 진 접미사(Proper Suffix) : v가 공문자열(엡실론)이 아닌 접미사
• 
  • 접두사와 접미사에 공문자열이 포함 된 것을 확인하라
  • 접두사는 앞에서부터 점점 늘어나고, 접미사는 앞에서부터 하나씩 줄어든다

7. Σ* (reflexive transitive closure, Kleene closure)

• 공문자열을 포함하는 알파벳 Σ에 대한 접속 연산에 의해 만들어질 수 있는 모든 문자열의 집합
  • 조합에서 만들어 질 수 있는 모든 경우의 수
• Σ+ (transitive closure, positive closure)
  • Σ*에서 공문자열을 제외한 모든 문자
  • Σ-대거라고 읽고, Σ+ = Σ* - {ε}이다.
    

8. 언어 L : 알파벳 Σ에 대해서 Σ*의 부분 집합

• 유한 언어(finite language) : 언어에 속하는 문자열의 수가 유한 개일 경우
• 무한 언어(infinite language) : 언어에 속하는 문자열의 수가 무한 개일 경우
  

형식 언어에서 유한 언어와 무한 언어를 구분하는 방법 : 해당 언어에 속하는 문자열의 수

유한 언어는 유한 개의 문자열로 구성되어 있으며, 무한 언어는 무한 개의 문자열로 구성되어 있습니다.

언어에 속하는 문자열의 수로 구분하는 것이 정확한 방법입니다.
예를 들어, {0, 1} 알파벳으로 구성된 문자열의 집합에서 {ε, 0, 1, 00, 01, 10, 11, 000, …}는 무한 언어이고, {ε, 0, 1, 00, 01, 10}는 유한 언어입니다.