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 $$

Q : states sigma: input alphabet delta: transition function(edge) q_0 : start state F: final state

DFA와 NFA는 위 처럼 transition function만 차이남

Example

$$delta(q_0,\lambda)=\{q_0,q_2\} accept$$

하나의 state라도 accept하면 accept

Accept

$$ lambda,1010,101010,10$$

~Accept

$$ 110,\ 10100$$

$$delta^*(q_1,a)=\{q_0,q_1,q_2\} $$

$$delta^*(g_2,\lambda)=\{g_0,g_2\} $$

$$delta^*(g_2,aa)=\{g_0,g_1,g_2\} $$

댓글을 남겨주세요~