수실잡
공부는 저희 친구들이 잘해요
수실잡
전체 방문자
오늘
어제

블로그 메뉴

  • 🏠블로그 홈
  • 💭태그 클라우드
  • 📬방명록
  • 🛠️블로그 관리
  • 📝글 쓰러 가기
  • 분류 전체보기 (127)
    • 교양(학문의 기초) (22)
      • 미적분학 (1)
      • 물리 (1)
      • 화학 (1)
      • 생물 (0)
      • 통계 (0)
      • 공학수학 (19)
    • 프로그래밍 언어 (2)
      • C (0)
      • C++ (0)
      • Java (0)
      • Python (2)
      • MATLAB (0)
      • R (0)
      • Julia (0)
    • 수학 (35)
      • 집합론 (Set Theory) (19)
      • 해석개론 (9)
      • 해석개론의 정수 (1)
      • 선형대수학 (1)
      • 미분방정식 (0)
      • 실해석학 (0)
      • 복소해석학 (0)
      • 대수학 (0)
      • 위상수학 (0)
      • 미분기하학 (0)
      • 응용수학 (0)
      • 확률론 (5)
    • 물리학 (32)
      • 물리수학 (3)
      • 역학 (9)
      • 전자기학 (13)
      • 양자물리 (0)
      • 열역학과 통계물리 (5)
      • 전자기파와 광학 (0)
      • 응집물질물리학 (2)
      • 논문 리뷰 (0)
    • 화학 (16)
      • 물리화학 (11)
      • 분석화학 (1)
      • 유기화학 (1)
      • 무기화학 (0)
      • 생화학 (3)
      • 고분자화학 (0)
      • 화학실험 (0)
      • 논문 리뷰 (0)
    • 재료공학 (1)
      • 재료공학원리 (0)
      • 재료열역학 (0)
      • 결정학개론 (0)
      • 재료상변태 (0)
      • 재료의 기계적 거동 (0)
      • 재료의 전자기적 성질 (1)
      • 재료역학 (0)
      • 기타 (0)
    • 컴퓨터공학 (9)
      • 자료구조 및 알고리즘 (0)
      • 인공지능 (0)
      • 양자컴퓨터 (1)
      • 컴퓨터구조 (5)
      • 논리설계 (0)
      • 컴파일러 (0)
      • 운영체제 및 시스템프로그래밍 (1)
      • 논문 리뷰 (1)
      • 계산이론 (1)
    • 전기전자공학 (0)
      • 전기전자회로 (0)
      • 소자 (0)
      • 집적회로 (0)
      • 신호처리, 제어공학 (0)
      • 전파공학 (0)
      • 전력전자공학 (0)
    • 기계공학 (2)
      • 고체역학 (2)
      • 열역학 (0)
      • 동역학 (0)
      • 유체역학 (0)
    • 언어학 (2)
      • 음성학 (0)
      • 음운론 (0)
      • 형태론 (0)
      • 통사론 (2)
    • 기타 등등 (6)
      • 학회리뷰 (3)
      • 꿀팁 (0)
      • 역대 교양수학 성적 통계량 정리 (1)
      • 기타 등등 (2)

공지사항

인기 글

최근 글

최근 댓글

태그

  • 벡터
  • ZFC Set Theory
  • 선형변환
  • ZFC 집합론
  • 레닌저 생화학
  • 행렬식
  • 차원
  • 확산
  • 열 및 통계물리
  • 벡터공간
  • 물리화학
  • 앳킨스 물리화학
  • 확률론
  • 백응생
  • Athreya
  • Atkins' Physical Chemistry
  • 선형대수
  • Thermal and statistical physics
  • 레닌저생화학
  • Random walk
  • Physical Chemistry
  • 가역
  • 공학수학
  • 랭크
  • 텐서
  • 일차독립
  • 컴퓨터구조
  • 행렬
  • Diffusion
  • 기본행렬

티스토리

hELLO · Designed By 정상우.
수실잡

공부는 저희 친구들이 잘해요

컴퓨터공학/계산이론

0. Basic Concepts - Language

By 성적표보여줘
2022. 8. 1. 19:59
Language

이 글은 언어로 작성되어 있습니다.
익숙하신 언어를 선택하십시오.

This post is written in Language.
Select the language you prefer.

この文は言語で作成されています。
使用する言語を選択してください。


Introduction

'학문'이란 어떤 '문제'를 푸는 과정으로 일축할 수 있다. 예를 들어, 건축공학은 집을 잘 짓는데 필요한 '문제'를 해결해 나가는 학문이고, 물리학이란 여러 가지 자연 현상들을 설명하고 예측하는 '문제'를 해결해 나가는 학문이다.

 

그렇다면 컴퓨터 과학(Computer Science)는 어떤 학문일까? 여러가지 정의가 있겠지만, 필자는 '문제를 푸는 방법', 그 자체에 대한 학문이라고 생각한다. 그 문제를 풀기 위해 우리는 컴퓨터라는 계산 기계를 이용하기 때문에 우리는 이 학문을 컴퓨터 과학이라고 부른다.

앞으로 연재해 나갈 포스트들은 컴퓨터로 어떠한 문제를 풀 수 있는지(Computability), 그러한 문제들이 얼마나 풀기 어려운지(Intractability)에 대해 다룰 것이다.

Language

먼저 알파벳과 스트링에 대한 것들을 정의하자.

정의 0.1

  • 알파벳(alphabet)이란 글자들의 유한 집합을 의미한다. 주로 $\Sigma$로 표현한다. 예를 들어, $\{a, b, c\}$, $\{0, 1\}$ 등은 모두 알파벳이다. 별 다른 설명이 없다면 알파벳은 0과 1을 사용한다.
  • 스트링(string)이란 유한 개의 알파벳을 나열한 것이다. 주로 $w$로 표현한다. 예를 들어, 010, abaab 등은 스트링이다.
  • 스트링의 길이(length)는 스트링 내의 알파벳의 개수를 의미하고 주로 $\vert w \vert$로 나타낸다. 예를 들어, 010은 길이가 3인 스트링이다. 길이가 0인 스트링은 $\epsilon$으로 표기한다.
  • $\epsilon$을 포함하여 알파벳 $\Sigma$ 상의 모든 스트링의 집합을 $\Sigma^*$로 표현한다. 예를 들어 $\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, \cdots\}$을 의미한다. 
  • 두 스트링의 접합(concatenation) $xy$는 $x$ 뒤에 $y$를 붙인 것이다. 예를 들어, $x = 0, y= 11$이면 $xy = 011$이다. 
  • 스트링의 역(Reverse) $w^R$는 알파벳을 역순으로 나열한 것이다. 예를 들어,  $w = 011$이면 $w^R = 110$이다. 

우리는 $\Sigma^*$의 부분집합을 언어(language)라고 하자. 주로 $L$로 표기한다. 언어의 연산은 다음과 같은 것들이 있다.

  • 언어 $L_1, L_2$의 접합(concatenation)은 다음과 같다. $$\{uv \;\vert\; u \in L_1, v \in L_2 \}$$ 또한 $L^k = L^{k-1} L (k>1)$로 정의된다. 
  • $L^*$는 다음과 같이 정의된다. $$L^* = L^0 \cup L^1 \cup L^2 \cup \cdots $$

우리가 앞으로 다룰 문제(problem)는 어떤 스트링 $w$가 어떤 언어 $L$에 속하는지 아닌지를 알고 싶은 것이다.

예제 0.1

스트링 $w = 101$이 $L = \{ w \;\vert\; w = w^R \}$에 속하는지 결정하라.

예제 0.2

언어의 개수는 몇 개인가? 자연수 집합의 크기인가 실수 집합의 크기인가?

티스토리툴바