언어와 문법 (languages, grammar) 과거의 문법: 법률처럼 조직되어 해서 안될일들의 망라 Syntactic structure, grammar 언어의 역사, 진화연구 (과학적 접근) Saussure, Boas, Bloomfield Chomsky의 생성문법 http://www.personal.kent.edu/~pbohanbr/Webpage/New/newintro.html 정규 문법 <-> finite state automaton (computer 의 일종) Context free grammar <-> pushdown automaton
생성(영)문법 <sentence> -> <subject><predicate> <subject> -> <noun phrase> <noun phrase> -> <noun> <noun phrase> -> <noun><conjunction><noun> <conjunction> -> and <noun>-> Jack <noun> -> Jill
<predicate> -> <verb><prepositional phrase> <propositional phrase> -> <proposition><article><noun> <preposition> -> up <article> -> the <noun> -> hill Jack and Jill ran up the hill
S(sentence) -> DNP(noun phrase) VP (verb phrase) VP -> V(verb) DNP VP-> V PP PP (prepositional phrase) -> P(preposition) DNP DNP -> DET NP DNP -> DNP PP NP -> A(adjective) NP NP -> N The woman runs to the big car (II pp. 151-154 많은 예를 만들수 있음)
Formal grammar G=(N,T,P,S) N finite set of nonterminal symbols T terminal symbols (N, T disjoint) P productions 생성자 S sentence symbol 문장기호 P의 원소 aAb -> awb (A = S or nonterminal symbol, w ∊ (N∪T)*
언어(language) L(G) = {w∈T*: S =>* w} G N={A}, T={a,b} S -> A, A -> aAb, A-> ab S => A => aAb => aaAbb => aaabbb L(G) = {akbk: 모든 k ≧1} G1 N={A, B, C}, T={a, b,c} P: S -> A, A -> aABC, A-> abC, CB -> BC, bB-> bb, bC -> bc, cC->cc L(G1) = {akbkck: 모든 k ≧1}
Finite State Automata 만약 여러분이 암산을 하고 있다면 다음 과정을 반복하고 있다. 5 + 1 + 6 – 7 = ? 5를 읽는다. +를 읽는다. 더할 준비를 한다. (변화) 1을 읽는다. 5+1을 계산하여 기역한다. (변화) -> + 을 읽는다….. 문장을 읽는 것도 마찬가지이다.
예(자동문) 앞발판 뒷발판 앞뒤양 뒤 양 무 앞 열린상태 닫힌상태 무 input state 무 앞 뒤 양쪽 닫힌 닫 열 열린
State diagram States {q1, q2, ..,q n}, transitions, accept, reject states M1 Input {1101} q1 -> q2 -> q2 -> q3 ->q2, accept 1 1 q1 q2 q3 0,1
Finite Automaton (Q, S, d, q0, F) Q states, S alphabet, d: QxS -> Q transition function q0 start state F ⊂ Q accept states 지난예 Q={q1, q2,q3}, S={0,1}, q1 start, F={q2} d 1 q1 q2 q3
언어 M: FSA, A:알파벹으로 이루어진 문자열 언어 L(M) ={ A : M이 받아들이는 문자열 A} 지난예 L(M1)= {w: w는 최소한 한 개의 1을 가지고 짝수개의 0이 최후의 1이후 부터 있다. }
정규언어 정규언어란 어떤 FSA가 받아들이는 언어이다. (0 ∪ 1)0* 컴퓨터 search 정규언어를 만드는 방법 1.a∊ S, 2. , 3. {}, 4. (R1∪R2), 5. (R1R2), 6. (R1)* 0*10*, (SS)*, 0S*0∪1S*1∪0∪1 정규언어 <-> FSA {0n1n}, {akbkck}는 정규아니다.
Context free grammar 인간의 언어의 모델, 컴퓨터 프로그램 언어 인간의 언어의 모델, 컴퓨터 프로그램 언어 예: A-> 0A1, A->B, B-> # 정의: (V, T, R, S) 1. V variables, 2. T terminals, 3. R rules, 4. S start variables 예 G3={{S}, {a,b}, R, S} S -> aSb | SS | abab, aaabbb, aababb,…. a=(, b=)라 두면 재대로된 괄호의 모음
Pushdown Automata Stack FSA Pushdown A a b .. a b x y state state
Pushdown Automaton의 정의 (Q, S, G, d, q0, F) 1. Q set of states 2. S input alphabets 3. G stack alphabets 4. D: QxSxG -> P(QxG) Context free 언어 <-> 받아들이는 PA가 있다. 예: 여러분 계산기 (최대한 활용하면)