KidCat

Consist of CFG Ambiguous Grammar Transform Chonskey Normal Form Consist of CFG Context Free Grammar ( CFG ) CFG 는 4가지로 구성되어 있는데 기호로 G = (Vn, Vt, P, S ) 로 정의한다. Vn : non terminal symbols Vt : terminal symbols P : Production , a -> B S : start symbol Context free language 는 CFG 에 의해 생성되는 문자열이고, Regular Language 와 마찬가지로 , Derivaiton 을 통해 state 를 trainsition 하며 만들어진다. Regular Language 와의 차이는 product..

Lex Yacc What is Lex & Yacc Write Lex Operator character What is Lex & Yacc Lex Lex 는 Lexical Analyzer ( Scanner ) 생성기이다. input 으로 RE로 구성된 source specification 과 Program fragements 를 받아서 Output 으로 Program 이 나온다. 쉽게 말해서 어떤 형식에 따라 RE를 기술해주면, 그것에 맞는 C코드 파일이 Output 으로 나온다. RE 에 대한 것이 Output으로 나오므로, 스캐너를 만들어준다고 생각하면 편하다. Yacc Lex 가 Scanner 를 만들어준다면 Yacc 은 parser 를 만들어준다. Scanner 에 의해서 만들어진..

Lexical analysis Translation process Extension to Regular Expression Optional Ambiguity White Space Lexical analysis Extension to Regular Expression Lexical analysis Scanning - Input 된 소스 코드를 스캔한다. - 토큰 단위로 나눈다. ※ Token (토큰) - 의미를 가진 character (문자) 들의 집합 - Token categories : 예약어 ( Reserved words ) , Special Symbols ( operation ) , Int, double, float, delimiter (구분자) 등.. Lexical analys..

Pumping Lemma FSM ( Finite State Machine ) Pumping Length 임의의 언어 L 이 R.L 임을 어떻게 증명할 것인가 How do we prove that a Language is NOT Regular R.L 은 반드시 가져야 하는 특성 ( property ) 가 존재한다. 이 특성을 만족하지 않는다면, 그 언어는 R.L 이 아니다. 단, 이 특성을 만족한다고 해서 R.L 이 되는 것도 아니다. (필요,충분 조건에 대한 것을 배웠다면 무슨 말 인지 이해할 것이다 ) Pumping lemma 는 " 어떤 언어가 형식 언어의 규칙을 따르지 않을 때 언어가 ' 불완전하다 ' 라는 것을 보여주는 방법 " 이라고 정의 되어있다. 어떤 언어가 형식 언어의 어떤 집..

Finite Automata Accept, Reject, Target , Start state Regular Expression ( RE ) Transition Function DFA, NFA , Minimal DFA Sombrero Construction Finite Automata DFA ( Deterministic finite automata ) NFA ( Non Deterministic finite automata ) Draw DFA, NFA ( NFA -> DFA -> Minimal DFA ) Regular expression to NFA ( RE -> NFA ) Question Finite Automata ( 유한 오토마타 ) Finite automata - 간선이 alph..