Automata and Theory of Computation 20160318정리

한양대학교 ocw Automata and Theory of Computation 20160318 강의를 정리 Regular expression $$ 1. \pi, \lambda, a \ni \sum : primitives\\ 2. r_1+r_2, r_1 \cdot r_2 , r_1^*,(r_1)$$ $$(a+b \cdot c)^* \cdot(c+\pi)$$

더 보기

Automata and Theory of Computation 20160316정리

한양대학교 ocw Automata and Theory of Computation 20160316 강의를 정리 Indistinguishable Distinguishable ( by a string w) 두 state 에서 모든 string w에 대하여 transition을 했을시에 모두 final , 혹은 모두 final로 안가는 경우 두개의 state가 Indistinguishable |w|=n+1인 를 통하여 distinguish하는 string w가 있으면 반드시 |w`|=n으로 distinguish하는 string존재

더 보기

Automata and Theory of Computation 20160309정리

한양대학교 ocw Automata and Theory of Computation 20160309 강의를 정리 Regular Language A Language L is regular some DFA M, L=L(M) $$L=\{awa: w \in \{a,b\}^*\}$$ $$ L^2=\{aw_1aaw_2a: w_1,w_2 \in \{a,b\}^*\}$$ 2.2 NFA $$M=(Q,\sum,\delta,g_0,F) \\ DFA: \delta : Q \times \sum \rightarrow Q \\NFA: \delta : Q \times ( \sum \cup \{\lambda \}) \rightarrow 2^Q $$…

더 보기

Automata and Theory of Computation 20160304정리

한양대학교 ocw Automata and Theory of Computation 20160304 강의를 정리 Finte Automata DFA(Deterministic Finite Acceptor) $$M=(Q,\sum,\delta,q_0,F)\\Q:set of states\\ \sum: input \ alphabet \\ \delta :Q \times \sum \rightarrow Q: transition \ function \\ q_0 \in Q : initital \ state \\ F \subset Q : final states \\ $$ example $$M=(\{g_0,g_1,g_2\},\{0,1\},\delta,q_0,\{q_1\})\\ \delta(g_0,0)=g_0 \\ \delta(g_0,1)=g_1 \\…

더 보기

Automata and Theory of Computation 20160302정리

한양대학교 ocw Automata and Theory of Computation 20160302 강의를 정리 alphabet $$\sum=\{a,b\}$$ 어떤 language에서 a,b 2개의 symbol만 사용 string $$w=abab,aaabbba $$ alphabet 에 들어있는 symbol을 0개 이상 사용하는것 string concatenation $$w=a_1,a_2,….,a_n $$ $$v=b_1,b_2,….,b_m $$ $$wv=a_1,a_2,….,a_n b_1,b_2,….,b_m $$ string reverse $$W^R= a_n,a_{n-1},….,a_1$$ string length $$|w|=n$$ null string $$\lambda :|\lambda|=0$$ substring 부분문자열 w=abba prefix substring => 앞에서…

더 보기