JJING_LOG

Pushdown automata (PDA) context-free language (CFL)은 Pushdown automata가 허용하는 language이다. Roughly speaking : PDA == [ε-NFA + "a stack"] - FSM 과 pushdown Schematic Finite state machine Pushdown automata Stack이 왜 필요할까? L = {(0^n)(1^n) | n >= 1}이 있다고 가정, CFL language이다. 이 때 몇 번까지 읽었는지 counting을 해주는 것이 stack의 역할이다. Regular Language는 몇 번까지 읽었는지 counting을 할 수 없다. Pushdown automata (PDA) PDA는 7-tuple P ..

Why normal forms? 만약 모든 grammar의 productions이 같은 형식으로 표현된다면 grammar를 사용하는 알고리즘 디자인 용이 증명 및 특성 표시 용이 대표적인 NF 2개 Chomsky Normal Form (CNF) (춈스키 정규 형태) Greibach Normal Form (그레이바하 정규 형태) Chomsky normal form (CNF) context-free grammar G는 production이 아래와 같이 표현되는 경우 Chomsky normal form이다. A -> BC // 2개의 non-terminal로 이루어진 경우 A -> a // 하나의 terminal로 이루어진 경우 S -> ε // start symbol이 ε로 가는 경우 A, B, C ∈ VN..

Context Free Grammar (CFG) context free grammar G = (VN, VT, P, S)로 구성되어있다. V_N : non-terminal symbol의 유한개 집합 V_T : terminal symbol의 유한개 집합 VN ∩ VT = ø VN ∪ VT = V P : productions 유한 집합 a -> v, a ∈ V+, b ∈ V* a ∈ VN, b ∈ V* S : start symbol Context free language (CFL) grammar로부터 생성된 Language context free grammar G=(VN, VT, P, S)가 주어졌을 때, G에 의해 생성된 언어는 집합이다. L(G) = {w | w ∈ VT* and S =*> w} => S에..

Lex Lexical Analyzer(Scanner) Generator 스캐너 프로그램을 만드는 프로그램이다. 문장 입력 stream의 lexical processing을 위해 설계된 프로그램 생성기 Input 문자열 정규표현식에 대한 High-level specification 정규식과 관련된 프로그램 조각 Output 범용 언어로 된 프로그램 입력 스트림의 식을 인식한다. 입력 스트림을 이 식과 일치하는 문자열로 분할한다. 엄밀히 C 코드가 생성된다. An overview of Lex Source에 C 코드 추가 가능 Lex lexical analysis 단계를 수행하기 위해 parser 생성기와 함께 사용한다. Scanner : Lex가 만든다. Parser : yacc이 만든다. lexical l..

Lexical analysis (Scanning) source code를 읽고 token으로 나눈다. token : 집합적 의미를 갖는 문자 sequence token은 컴파일러의 parser에 의해 처리된다. - Token categories Reserved words : IF, THEN 등 Special symbols : +, - 등 Integers, doubles, floats, delimiters 등 - 입력 문자열에서 token을 식별한다. lexeme(string value) : token을 구성하는 실제 문자 시퀀스 token의 실제 text : "137", "int" 등 token : lexeme이 속한 general class - 오류가 거의 감지되지 않는다. 유효한 토큰, 잘못된 토큰 ..

Convert an ε-NFA to a DFA Regular expression을 -> NFA automata로 만들고 -> DFA automata로 변환 ex) - Regular expression : (a + b)*abb - ε-NFA : 1. start symbol의 ε-closure를 구해라 ε-closure(0) = {0, 1, 2, 4, 7, 8} -> A라는 state라고 하겠다. Ds = {A} -> Ds라는 곳에다가(queue라고 생각) A를 추가 아래 처럼 그림 그리기 2. Ds에 있는 element를 pop 한다. -> A 나온다. A는 {0, 1, 2, 3, 7, 8}이라는 state다. {0, 1, 2, 3, 7, 8}에서 a로 갈 수 있는 state를 찾는다. : {0, 1, 2..

Finite automata (유한 오토마타) 유한 오토마타는 edges가 다음과 같은 유한 전이 그래프다. 비공식적 표현 입력 기호의 스트림 또는 sequence에 응답하는 동안, 기계가 취할 수 있는 모든 가능한 state 및 transitions(전환)을 캡처하는 상태 다이어그램 (상태 전의도) A state에서 a 마킹시 B state가 된다. A에서 a 입력시 B로 transition한다. 이러한 state들이 유한개 있다. Recognizer for "Regular Languages" 정규 언어를 인식하는 수학적 모델 어휘 분석기 종류 2개 Deterministic finite automata Non-Deterministic finite automata Deterministic finite a..

Regular expressions (정규표현) 정규 표현은 언어(regular languages)를 설명하는 대수적 방법이다. e가 정규식이면 L(e)가 정의하는 언어다. Definition of regular expressions Basic 1 : a가 기호라면, a는 Regular expression이고, L(a) = {a} a를 regular expression으로 표현시 bold 체로 정의 Basic 2 : ε은 regular expression, L(ε) = {ε} Basic 3 : ø은 regular expression, L(ø) = ø Induction 1 : r, s가 regular expression이라면, r+s도 regular expression L(r+s) = L(r|s) = L(..

Computability, Decidability, Undecidability 모든 입력에 대해 함수가 정의되어 있는지 결정 Automata theory 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학 "장치"는 물리적 하드웨어일 필요가 없다. 컴퓨터 과학의 근본적인 질문은 다양한 모델의 기계가 할 수 있는 것과 없는 것을 알아본다. Motivations ex) 문자열을 입력하고 다음 두 가지 가능한 답변을 반환하는 일종의 black box를 가정 Black box에 input으로 문자열 w를 입력했을 때 YES -> w는 언어에 속한다. NO -> w는 언어에 속하지 않는다. Language로부터 유효한걸 어떻게 기술할 것인가? Automaton : 언어를 ..

컴파일러 (Compiler) 언어 X를 언어 Y로 변환해주는 컴퓨터 프로그램이다. Source Program -> Compiler -> Target Program ex) Source language : high-level language (C / C++) Target language : object code || 어셈블리어 컴파일러가 필요한 이유 1. 폰 노이만 아키텍처 (Von Neumann architecture) 폰 노이만 아키텍처를 따르기 위해선 코드 또는 프로그램이 순차적으로 작성되어야 한다. 2. Machine language (기계어) 기계어로 코드를 작성하는 것은 매우 시간이 많이 걸리고 지루하다. 3. Assembly language (어셈블리어) Assembler : symbolic c..