이산수학 8. 형식언어와 오토마타, 셈 - swkim0128/PARA GitHub Wiki
영상: https://www.youtube.com/playlist?list=PLD8rdlfZeJk7aDHa1VxqnX5TyQ4FmgavH
-
오토마타
계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 분야
형식 언어를 정의하는 관점에서 컴파일러에서 구분 분석을 하면서 추상 구문 트리를 생성할 때계산 능력을 가진 추상 기계를 논하는 관점에서 계산 이론적으로 P-NP문제와도 연관성 있음
-
S: 기호들의 집합
-
S*: S로부터 만들어지는 모든 유한 문자열들
-
언어의 세가지 구성요소
- 알파벳: 기호들의 집합 S가 반드시 존재한다.
- Syntax(문법): S로부터 몬장들의 집합 S*를 형성하는 규칙이 반드시 존재한다
- Semantics(의미론): 규칙에 합당하게 만들어진 문장들이 어떤 의미를 갖는지를 결정할 수 있어야 한다
- 문법: 문장의 적합한 구성에 대한 규정 / 나는 가고있다 빠른 사람 (문법에 맞지않음)
- 의미론: 문장의 적합한 의미에 대한 규정 / 소리가 걸어간다 (의미론적으로 맞지않음)
- 특정한 법칙들에 따라 적절하게 구성된 문자열들의 집합
- 심벌(symbol): 기호
- 알파벳(alphabet): 기호들의 유한 집합
- 문자열(String): 알파벳에 포함된 기호들이 나열된 것
- 공 문자열(empty String): 길이가 0인 문자열, λ로 표시 (공집합과는 다르다.)
- G = (V,T,S,P)
- V: 기호의 집합 = (단말기호(T), 비단말기호(N)로 이루어짐, V=T∪N)
- T: 단말 기호(terminal symbol) = 최종적으로 문자열로 나타내어지는 것
- S: 시작기호(start symbol, seed) = 여기서부터 문자열이 생성 됨
- P: 생성규칙(production rule) (⇒로 표시)
ex1)
⇒ (비단말기호들로 이루어짐, 이런형태가 생성규칙임)
⇒ Jill
⇒ Jill drives frequently (단말 기호 생성완료)
-
유도트리를 이용해 생성과정 표현
ex2)
G = (V,T,S,P)
N = {S},
T = {a, b}, V = T∪N
P = {S ⇒ aSb, S ⇒ ab}
a^3b^3은 이 문법에서 만들어지는가?
S⇒ aSb ⇒ aaSbb ⇒ aaabbb
생성 가능함
- L(G): 문법 G의 언어
- 문법 G를 사용하여 만들어질 수 있는 문장들의 집합
예)
G = (V,T,S,P)
N = {S, A},
T = {a, b}, V = T∪N
P = {S ⇒ aA, S ⇒ b, A⇒aa}
S ⇒ aA ⇒ aaa
S ⇒ b
2가지 경우가 존재
따라서 문법 G로부터 유도되는 언어는
L(G) = {aaa, b}
이다
- 문법의 종류
- 유형0 문법 (비제한 문법)
- 생성에 아무 제약이 없다
- 왼쪽편에 여러개의 비단말 기호가 나올 수 있음
- 유형1 문법 (문맥 의존 문법: context sensitive grammar)
- αAβ ⇒ αγβ
- α, β ∈ (N∪T), A∈N, γ∈(N∪T) - {λ}
- 왼쪽편에 여러개의 비단말 기호가 나올 수 있음
- 왼쪽꺼가 오른쪽과 연관되어 대체됨(그래서 문맥의존 이라함)
- 유형2 문법 (문맥 자유 문법: context free grammar)
- A⇒α, A∈N (비단말 기호), α∈(N∪T)*
- 왼쪽편에 한개의 비단말 기호만 가능
- 오른쪽 편에 아무거나 나와도 가능
- 유형3 문법(정규 문법: reqular grammar)
- A⇒aB 혹은 A⇒a 혹은 A⇒λ, A, B∈N, a∈T
- 왼쪽편에 한개의 비단말 기호만 가능
- 오른쪽 편에 정해진 형태만 가능
- 유형0> 유형1> 유형2> 유형3
- 프로그래밍 언어의 경우 유형 2, 유형 3로 전부 표현됨
- 유형0 문법 (비제한 문법)
-
BNF(Backus-Naur Form) 형식
-
문법 다이어그램(syntax diagram)
-
유도 트리(derivation tree)
-
BNF형식
-
비단말 기호는 로 표시한다
-
생성 ⇒ 은 ::=로 표시한다
-
하나의 비단말 기호로부터 생성되는 여러 개의 문자열은 | 으로 구분한다
예시) ::= a ::= bb|c
-
-
문법 다이어그램
- 비단말 기호는 사각형으로, 단말 기호는 원으로 그린다.
- 생성 과정은 화살표로서 표시한다.
- 하나의 비단말 기호로부터 생성되는 여러 개의 문자열은 병롤로 놓고 화살표로 표시한다
- I : 기호(symbol)들의 집합(알파벳)
- I* : 집합 I의 기호들을 결합하여 만들어지는 유한 크기를 갖는 모든 문자열의 집합
- λ : 공 문자열(empty string)
- αβ : 문자열 α와 문자열 β의 연결 (concatenation)
- α+β : 두 문자열 α, β의 합집합 (+는 ∪로도 표시한다)
- (α)* : 문자열 α가 유한 개수만큼 반복되어 만들어지는 문자열 λ ∈(α), (α) ≡ α*
- I : 기호들의 집합(알파벳)
- I 에서 정의되는 정규식은 다음과 같이 재귀적으로 정의된다
- 공문자열 λ는 정규식이다
- α∈I 라면 α는 정규식이다
- α과 β가 각각 정규식이면 αβ도 정규식이다
- α과 β가 각각 정규식이면 α+β도 정규식이다
- α가 정규식이면 α*도 정규식이다
-
I* 으로 표현
-
정규식으로부터 만들어지는 모든 문자열들을 정규 집합이라고 함
예시) I={a, b, c} 일때, 다음의 정규식으로 만들어지는 정규집합 I를 구하여라 a → I* = {λ, a, aa, aaa, aaaa, ...} a(b+c) → I* = {ab, ac} ab(bc)* → I* = {ab, abbc, abcbcbc, ...}
-
정규 문법: 정규 문법은 정규식으로 표현될 수 있으며 정규 문법에 의해서 생성되는 언어는 정규식에 의해서 만들어지는 정규 집합과 동일하다
이산수학: 형식언어와 오토마타3- 유한상태기계(finite state machine)
-
플립플롭이 대표적인 예시임
-
유한 상태 기계 (S, I, F)
플립플롭을 이용한 예시 S = {0, 1} I = {0,1} f(현재상태, 입력값) = 결과상태 f(0, 0)=0, f(1, 0)=1, f(0, 1)=1, f(1, 1)=0
-
유한 상태 기계의 유형
- 출력이 있는 유한 상태 기계
- 출력이 상태의 추이함수에 의해 결정
- 출력이 상태에 의해 결정
- 출력이 없는 유한 상태 기계
- 출력이 있는 유한 상태 기계
-
출력이 있는 유한 상태 기계
S: 상태의 집합 (a set of states) I: 입렵값의 집합 (a set of inputs) f: 상태 추이 함수(state transition function) g: 출력함수 s0: 초기상태
-
유한 상태 오토마타(finite state automata)라고도 함
-
출력은 없지만 최종 상태의 집합이 존재한다
-
언어를 인식하는 기계를 모델링할 때 사용된다
M = (S, I, f, s0, F) S: 상태의 집합 (a set of states) I: 입렵값의 집합 (a set of inputs) f: 상태 추이 함수(state transition function) s0: 초기상태(starting states) F: 최종상태(acceptance states)의 집합
유한 상태 오토마타 예시
문제: 5L의 물통, 3L의 물통으로 4L의 물을 만들자
x: 5L 통에 물을 채운다
x': 5L 통에 물을 비운다
y: 3L 통에 물을 채운다
y': 3L 통에 물을 비운다
xy: 5L통 → 3L통
yx: 3L통 → 5L통
(0,0)-x→(5,0)-xy→(2,3)-y'→(2,0)-xy→(0,2)-x→(5,2)-xy→(4,3)
x, xy, y', xy, x, xy 라는 입력값을 통해 (4,3)이라는 최종 상태에 도달한 형태