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 => 앞에서 부터 포함된 부분문자열(ex a,ab,abb..)

suffix substring => 뒤에서 부터 포함된 부분문자열(ex a,ba,bba…)

string power

$$W^0=\lambda$$

$$W^1=w$$

$$W^2=ww$$

$${\sum}^{*}=\{\lambda,a,b,aa,ab,ba,bb….\} $$

$${\sum}^{+}={\sum}^{*} -\lambda$$

language => 알파벳을 이용해서 임의의 한 string의 집합 위 집합의 subset

{a,aa,aab}는 alphabet={a,b}를 이용해 만든 유한한 language의 예

아래는 alphabet={a,b}를 이용해 만든 무한한 language의 예

$$L=\{a^nb^n:n>=0\}$$

sentence

language에 속한 원소를 지칭하는 말 {a,aa,aab} 에서 a language를 sentence의 집합으로 봄

language 의 기타 정의

$$\overline{L}={\sum}^{*}-L$$

$$L^R=\{w^R:w \in L\}$$

$$L_1L_2=\{ab,abb,aab,aabb\} \\ then \ L_1={a,aa},L_2={b,bb}$$

$$L^0=\{\lambda\}\ne\{\}$$

$$L^*=L^0\cup L^1\cup L^2 \dots$$

$$L^+=L^1\cup L^2 \dots$$

example

$$L=\{a^nb^n:n>=0\}$$

$$L^2 \ne \{a^n b^n a^n b^n :n>=0\}$$

$$L^2 = \{a^n b^n a^m b^m :n>=0,m>=0\}$$

$$L^R=\{b^n a^n:n>=0\}$$

grammar

$$G(V,T,S,P)$$

V: variable
T: terminal symbols
S: start variable
P: productions

example

$$G=(\{S\},\{a,b\}),S,P\\S->aSb\\ s->\lambda$$

S에서 시작 production rule을 반복적으로 적용 -> variable이 없어 질때 까지 (string을 만드는것이 목적 string은 variable이 없고 teriminal 만 존재)

S=> aSb =>ab

S=> aSb=>aaSbb(sentential form 중간과정)=>aabb(sentanence 최종)

아래 language를 만드는 grammar임을 알 수 있음

$$L=\{a^nb^n:n>=0\}$$

$$L(G)=\{w\in T^*:S \overset{*}{\Rightarrow} w\}$$

위 수식의 의미는 start symbol에서 부터 만들수있는 모든 sentence의 집합(sentential form은 제외)

$$L=\{a^nb^{n+1}:n>=0\} \\ S \rightarrow Ab \\ A \rightarrow aAb \\ A \rightarrow \lambda$$


$$S\rightarrow SS\\S\rightarrow \lambda\\S\rightarrow aSb\\S\rightarrow bSa\\n_a(w)=n_b(w)$$

위 문법에 의해 생성되는 string은 a의개수와 b의 개수가 같음

댓글을 남겨주세요~