비결정적 유한 인식기(nfa)

비결정적 유한 인식기(nfa)는 다음과 같이 정의 된다. $$ M=(Q,\Sigma,\delta,q_0,F)$$ Q,∑,q_0,F는 dfa에서와 같이 정의되고, δ는 다음과 같다. $$\delta : Q * (\Sigma \cup \{\lambda\})->2^Q$$ 내부 상태 Q에서 람다를 포함한 심벌들의 전이함수는 Q의 멱집합이 될 수 있다. 무슨 뜻이냐면 내부상태 q_0에서 다음과 같은 전이 함수가 있다 가정했을때, 다음상태를 여러개가 될 수 있다는 뜻이다. $$\delta(q_1,a)=\{q_0,q_2\}$$ 즉 dfa는 방향 그래프에서 현재 상태는 하나의 심벌에 대해 하나의 간선만 진출 간선만 가질수 있지만, nfa에서는 여러개의 진출 간선을 가질수 있다는 것이다. 또한 nfa는 λ(람다)를 허용..

• format_list_bulleted 계산이론
• · 2021. 4. 7.
• textsms

유한 오토마타 -결정적 유한 인식기(dfa)

결정적 유한 인식기, 줄여서 dfa는 유한개의 상태를 가지고 있는 오토마타다. dfa는 다음과 같이 정의 될 수 있다. $$M=(Q,\Sigma,δ,q_0,F)$$ Q는 내부 상태, 즉 그래프로 치면 노드에 해당하고, ∑는 심벌들의 유한집합, 즉 방향 그래프의 간선에 해당한다. 또한 δ는 전이 함수이고, q_0은 처음 시작하는 지점, 즉 입력을 받는 지점을 나타낸다. F는 승인상태들의 집합이다. 승인상태는 이중 원으로 표시한다. 전이함수는 다음과 같이 표기한다. $$\delta(q_0,a)=q_1$$ 상태 q_0에 a가 입렵될 시 q_1상태로 전이 한다는 뜻이다. 이를 가시적으로 표현하기 위해 보통 전이 그래프를 사용해서 표시한다. 확장 전이함수를 사용해 함수를 나타내는 경우도 있다. $$\delta(q..

• format_list_bulleted 계산이론
• · 2021. 4. 5.
• textsms

4)언어, 문법, 오토마타 개념

언어 영어, 한국어, 중국어, 일본어등등 같은것을 자연언어라 한다. 알파벳: 하나 이상의 심벌들의 유한집합, ∑로 표현한다. 문자열: 심벌들의 유한길이의 순서열 ex) 알파벳은 ∑={a,b}라고 하면, aa,aba,abbba,aaaab는 알파벳 ∑에대한 문자열이 된다.특별한 경우를 제외하고, ∑는a,b,c,d...같은 소문자를 사용하고,문자열의 이름은 u,v,w...등을 사용한다.이름이 w인 문자열의 값이 aba는 w=aba라 나타낸다. 접합: 문자열과 문자열을 붙이는 것 ex) w=a_1a_2a_3a_4....a_n, v=b_1b_2b_3b_4...b_m 일때 w와 v의 접합 wv는 a_1a_2a_3a_4....a_nb_1b_2b_3b_4...b_m가 된다. 역문자열 : 문자열의 심벌들은 역순으로 배열..

• format_list_bulleted 계산이론
• · 2021. 3. 28.
• textsms

3) 그래프, 트리

그래프: 정점들의 집합 V(v_1,v_2,v_3...,v_n) 과 간선들의 집합 E={e_1,e_2,e_3....,e_m}으로 이루어진 구조. 간선: 각 간선은 집합 V에 있는 정점들의 쌍 $$e_i = (v_j,v_k)$$ 간선 e_i는 v_j로부터 시작하고 v_k에 도착하는 간선이 된다. v_j를 기준으로 하면 진출간선이라 하고, v_k를 기준으로 하면 진입간선이라 한다. 유향 그래프: 각 간선에 방향을 지정한 그래프 라벨 그래프: 각 정점이나 간선에 라벨을 지정한 그래프. 라벨은 특별한 이름이나 정보일 수 있다. 정점이 {v_1,v_2,v_3}이고 간선들의 집합이 {(v_1,v_3),(v_3,v_1),(v_3,v_2),(v_3,v_3)}인 그래프에서 간선들은 v_i로부터 v_n으로의 "보행" 이라 ..

• format_list_bulleted 계산이론
• · 2021. 3. 19.
• textsms

2) 함수와 관계

함수: 한 집합의 원소를 각각 다른 집합의 단일 원소로 배정하는 규칙 f가 한 함수라 한다면 첫번째 집합을 함수 f의 정의역이라 하며, 두번째 집합을 치역이라 한다. 이러한 함수를 아래와 같이 표기한다. $$f:S_1→S_2$$ 전체 함수, 부분함수: 함수 f의 정의역이 S_1과 같은경우 f를 "전체함수"라 하고, 그렇지 않을경우 "부분함수"라한다. 순위: f(n)과 g(n)을 정의역이 양의 정수들의 부분집합인 함수라 했을때, 충분히 큰 모든 n에 대해 $$f(n)=c|g(n)|$$이 성립하는 상수 c가 존재할 시 f의 순위가 g의 순위보다 낮지 않다고 한다. 이를 아래와 같이 표기한다. $$f(n)=Ω(g(n))$$ 그리고 $$c_1|g(n)|

• format_list_bulleted 계산이론
• · 2021. 3. 19.
• textsms

1) 집합

집합이란? 집합이란 원소들의 모임이다. x가 집합 S의 원소임을 나타내면 "x∈S"로 표기한다. ex) 정수 0,1,2를 포함하는 집합 : S={0,1,2} 집합 표현시에 의미가 명확한 경우에는 생략부호를 사용 할 수 있다.집합 {a,b,c....,z}는 알파벳 소문자들의 집합이고, 집합 {2,4,6,8.....}은 정수중에 짝수의 집합을 의미한다. 필요에 따라서는 짝수들의 집합을 아래와 같이 표현할 수 있다. S={i:i>0, i is even} 이를 읽을때는 "S는 0보다 크고 짝수인 모든 i들의 집합"라 한다. 많이 사용되는 집합연산 합집합: A∪B={x:x∈A or x∈B} 교집합: A∩B={x:x∈A and x∈B} 차집합: A-B={x:x∈A and x∈B} 드모르간 법칙 부분집합: 어떤 집합..

• format_list_bulleted 계산이론
• · 2021. 3. 16.
• textsms