Formal Language, Grammar and Automata

Theory of Computation

계산 이론

• Computability, Decidabillity, Undecidability
  • 계산 가능한 함수인가?
  • 함수가 종료 가능한가?
  • 증명이 무엇인가?
• Languages and Automata
  • 언어란 무엇인가?
  • 언어를 어떻게 정의하는가?
  • 언어 안의 단어를 어떻게 인식할 것인가?
• Complexity
  • 공간과 시간을 너무 많이 사용하면 안 됨
  • P (polynomial time)= NP(non-deterministic polynomial time)

계산 가능성, 결정 가능성, 결정불가능성

• 함수가 모든 입력에 대해 정의되는지 결정하는 것은 어려움
• 3n + 1문제

오토마타 이론(Automata theory)

• 계산 능력이 있는 추상기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구
• Automaton(단수 표현) : 계산 능력이 있는 추상 기계
  • 물리적인 하드웨어 필요 없음
  • Automata(복수 표현)
• 컴퓨터 과학에서의 근본적인 문제
  • 서로 다 유한

동기

• 인식의 관점
  • 문자열 w가 언어 L에 속하면 인식
  • 문자열 w가 언어 L에 속하지 않으면 인식 안됨
• 생성의 관점
  • 합법적인 문자열을 생성하는 문법 정의
  • 언어를 어떻게 기술하면 표현 가능한지
• 오토마타는 언어를 인식한다.
• 문법은 언어를 생성한다.

Formal Language(형식 언어)

알파벳(Alphabet)

• 알파벳 $\Sigma$
  • 유한한, 비어있지 않은 기호들의 집합

문자열(Strings)

• 문자열(String or word) w
  • $\Sigma$로부터 얻어지는 유한한 기호들의 순서
  • 빈 문자열 $\epsilon$ (문자열의 길이 = 0)
• |w| : 문자열의 길이
• 연결
  • x = abcd, y = efgh → xy = abcdefgh
• $a^n = a...a\space(a의 개수 = n)$

알파벳의 거듭제곱$(\Sigma^*, \Sigma^+)$

• $\Sigma^k$ : 길이가 k인 문자열 집합
• $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...$s제
• $\Sigma^+ = \Sigma^* - { \epsilon } = \Sigma^1 \cup \Sigma^2 \cup ...$

언어(Language)

• 언어 L
  • $\Sigma^$의 부분집합, $L \subseteq \Sigma^$

멤버쉽 문제(Membership (recognition) problem)

• 주어진 문자열 w가 언어 L에 포함되는가 $(w \in L)$

Grammar

문법(Grammar)

• 합법적인 문자열을 생성하는 법칙으로 언어를 기술
• 문법 $G = (V_N, V_T, P, S)$
  • $V_N$ : 유한개의 non-terminal symbols 집합
  • $V_T$ : 유한개의 terminal symbols 집합
    • $V_N \cap V_T = \varnothing, V_N \cup V_T = V$
  • $P$ : 유한한 문자열 쌍의 집합, productions
    • $\alpha \rightarrow \beta, \alpha \in V^+, \beta \in V^*$
    • $\alpha$ : 왼쪽에 있는 것 (lhs)
    • $\beta$ : 오른쪽에 있는 것(rhs)
    • → : 왼쪽 기호를 오른쪽 기호로 대체한다.
  • $S$ : 시작 기호(non-terminal symbol)

추가적인 문법 표기법

• Non-terminal symbols : 대문자
• Terminal symbols : 소문자
• Start symbol : S
• lhs가 같을 때 | 로 연결해서 rhs 표현
  • S → A | a ( S → A, S → a)

Derivation(⇒)

• 한 문자열에서 생성 규칙을 한 번 적용해서 다른 문자열로 바꾸는 것
• $\overset{*}\Rightarrow$ : 0번 이상 derivation
• $\overset{+}\Rightarrow$ : 1번 이상 derivation
• $\overset{n}\Rightarrow$ : $a_1 \overset{n}\Rightarrow a_n \space
  iff\space a_1, a_2, a_3, ..., a_n \in V^*\space and\space a_1 \Rightarrow a_2 \Rightarrow a_3 \Rightarrow ... \Rightarrow a_n$
  • iff : if and only if, 필요충분조건

문법 G로 생성된 언어 L

• $G = (V_N, V_T, P,S)$에 의해 생성된 언어 $L(G)$
• $L(G) = {w|w \in V_T^\space and\space S \overset{}\Rightarrow w}$

촘스키 계층 구조(The Chomsky Hierarchy)

Type	Grammar	Production Rules
0	Unrestricted	$\alpha \rightarrow \beta$	제약 없음
1	Context-Sensitive	$\alpha \rightarrow \beta$   $|\alpha| \leqq |\beta|, \alpha \in V^+, \beta \in V^*$	$\alpha$의 길이가 $\beta$보다 짧아야 함
2	Context-Free	$\alpha \rightarrow \beta$   $\alpha \in V_N, \beta \in V^*$	$\alpha$는 non-terminal symbol 하나만 올 수 있음
3	Regular	$\alpha \rightarrow t\beta\space |\space t$ (right linear)   $\alpha \rightarrow \beta t\space |\space t$   (left linear)   $\alpha,\beta \in V_N, t \in V^*_T$	right linear : 맨 왼쪽은 terminal symbol이어야 함 left linear : 맨 오른쪽은 terminal symbol이어야 함

언어와 인식기의 계층구조(Hierarchy of Languages and recognizer)

Grammar	Language	Example of Language	Recognizer
Unrestricted	Recursively enumerable set		Turing machine
Context-Sensitive	Context-sensitive language	$\{a^nb^nc^n | n\ge 0\}$ (중복매칭언어)	Linear bounded automata
Context-Free	Context-free language	$\{a^nb^n | n\ge 0\}$ (단순매칭언어)	Pushdown automata
Regular	Regular language	$\{a^mb^n | m,n\ge 0\}$	Finite automata