observe_db

보호되어 있는 글입니다.

5/12 5/18 인식기(Recognizer): 입력으로 string을 받아 그 언어의 문장이면 "YES", 아니면 "NO"를 출력하는 프로그램 튜링머신(type0)-A에 선형 종속(type1)-푸시다운 오토마타(type2)-유한 오토마타(type3) 유한 오토마타(Finite Automata. FA) 알파벳Σ에 대한 유한 오토마타 M = (Q,Σ, δ, q0, F) Q: state의 유한 집합 Σ: 입력 알파벳의 유한 집합 δ: 사상함수 q0 ∈Q: 시작 상태 F ⊆Q: 종결 상태의 집합 사상함수 δ: Q * Σ-> 2^Q ex) δ(q, a) = {p1, p2...pn} 결정적 유한 오토마타(DFA) 결정적이다 - δ(q, a)가 한상태 만을 갖는 경우 - δ(q, a) = {p} 대신에 "δ(q, ..

type 3: regular Language 정규 문법과 정규 언어 정규 문법 이론: 컴파일러 어휘 분석 과정에서 모형을 만드는데 사용 Type 3 문법 RLG(Right Linear Grammar): A->tB, A->t LLG(Left Linear Grammar):A->Bt, A->t 여기서 A, B ∈Vn이고, t∈VT* 우선형 형태의 규칙과 좌선형 형태의 규칙이 혼합되어 있으면 정규 문법이 아님. 정의 각 생성규칙이 다음과 같을 때 정규문법이라 한다. A->aB, A->a, 여기서 a∈VT, A,B ∈VN S->ε∈P 이면, S는 오른쪽에 나타나지 않아야 한다. 정규 문법에 의해 생성된 A언어는 정규 언어(rl)이다. L = {a^nb^m|n, M>=1}은 정규언어 S->aS|aA A->bA|b ..

알파벳과 스트링 잘 정의된 언어는 문장으로 구성 알파벳은 문장을 이루는 기본적인 심볼 알파벳: 심벌들의 유한집합 스트링(문장, 단어): 알파벳 T에 속하는 하나 이상의 심벌의 나열 길이: 스트링을 이루는 심벌의 갯수. |ω|로 표시 empty 스트링: 스트링 길이가 0인것. ε또는 λ로 표시 T*: 알파벳 T에 대해서 empty스트링까지 포함한 모든 스트링의 집합 접속(concatenation): 스트링을 연속으로 연결한 것. u●v를 보통 uv로 표기 u=a1a2a3a4...an, v=b1b2b3...bm, u●v=a1a2a3...anb1b2b3...bm uε = u = εu ∀u,v ∈T*, uv∈ T* |uv| = |u| + |v| a^n : n개의 a. 문자 ω의 반전은 문자 ω에 반전표시를 (ω..