untitled

Size: px

Start display at page:

Download "untitled"

우림 강
5 years ago
Views:

1 3. Type 3 (N. Chomsky) RLG : A tb, A t LLG : A Bt, A t where, A,B V N nd t V T *. LLG RLG,. ) G : S R S c R Sb L(G) = { n cb n n } is cfl.

2 () A grmmr is regulr if ech rule is i) A B, A, where VT, A, B VN. ii) if S P, then S doesn't pper in RHS. A tb, A t t terminl. (2). ex) L = { n b m n, m } is rl. S S A A ba b [ ] RLG.(RLG => RG) ( ) A tb, where t V T* t = 2...n, i V T., A A A 2 A 2.. A n- -> n B. t =, A B (single production) A (epsilon production).. Right-liner grmmr : A tb or A t, where A,B V N nd t V T *. ) S bca S S, S bs2 S2 ca A bca A ba, A ca A cd A ca', A' d Equivlence. L. 2. L. 3. L. [ ] L = { n b m n,m >= } : rl S S A A ba b

3 (). (2) context-free. (3). (Scnner + Prser). G derivtion L if G = rg, L: re.. () (regulr grmmr) (2) (regulr expression) (3) (finite utomt) rg f re I. : φ,, T. () φ. (2) {}. (3) T {}. II. e e 2 L L2, () (e ) + (e 2 ) L U L2 (union) (2) (e ) (e 2 ) L L2. (conctention) (3) (e) * L * = {} U L U L 2 U... U L n... (closure) Note : precedence : + < < * III..

4 ) (+)* (+)* : α, L(α) α. α β, () L(α + β) = L(α) L(β) (2) L(α β) = L(α) L(β) (3) L(α ) = L(α) exmples : () L( ) = {,,,, } = { n n } (2) L(() (bb) b) = { 2n b 2m+ n,m } (3) L((+b) b(+b) ) = { b, b, bb, b, bb, b, bbb, } :. α = β if L(α) = L(β). Axioms : Α. α + β = β + α Α2. (α + β) + γ = α + (β + γ) Α3. (α β) γ = α (β γ) Α4. α (β + γ) = α β + α γ Α5. (β + γ) α = β α + γ α Α6. α + α = α Α7. α + φ = α Α8. α φ = φ = φ α Α9. α = α = α Α. α = + α α Α. α = ( + α) Α2. (α ) = α Α3. α + α = α Α4. α +α + = α Α5. (α + β) = (α β ) Α8. α φ = φ = φ α (proof) α φ = { xy x L α nd y L φ } Since y L φ is flse, (x L α nd y L φ ) is flse. Thus α φ = φ. : (regulr expression eqution) (coefficient) ex) α, β, X = αx+β., X nonterminl nonterminl.

5 X = X + (solution) X = X + = ( X + ) + = 2 X + + = 2 X + ( + ). = k+ X + ( k ) = ( k +...) = *. X = * X = X + = ( * ) + = * + = ( * + ) = *. A V N, L(A) A., S, L(G)= L(S). :.. A B, A L(A) = {} L(B) U {} A = B +, X γ X = + + γ. 2.. X = X + X = *. ) S S S br S R S L(S) = {}L(S) U {b}l(r) U{} L(R) = {}L(S) ree: S = S + br + R = S S = S + bs + = ( + b)s + = ( + b) * = ( + b) * 2) S A bb b A ba B bs ree: S = A + bb + b A = ba + A = b * = b * B = bs S = b * + bbs + b = bbs + b * + b = (bb) * (b * +b)

6 3) A B A 4) S A bs B A C A S bb C C C B B bb 5) S A B 6) X = X 2 + X + A A S B X 2 = X 3 + X 2 B B X 3 = X + X 3 7) A = (* + ) A + A 2 8) A B ba A 2 = + A + A 3 B B bc A 3 = A + A 2 + C bd B D ba B (recognizer) "yes, "no i i+ i+2... n input Input hed Finite Stte Control Auxiliry Storge Turing Mchine Liner Bounded A PushDown Automt Finite Automt : FA M = (Q,, δ,q,f), Q : finite, non-empty set of sttes. : finite set of input symbols. δ : (mpping function). q Q : strt(or initil) stte. F Q : set of finl sttes. δ : Q x 2 Q., δ(q,) = {p, p 2,..., p n } G = (V N, V T, P, S) re : φ,,, +,, * M = (Q,, δ, q, F) (DFA:deterministic finite utomt) (NFA: non-deterministic finite utomt).

7 Deterministic Finite Automt(DFA) δ(q,) (deterministic). δ(q,) = {p} δ(q,) = p. (q,) M (completely specified). δ : Q x Q x * δ(q, ) = q δ(q,x) = δ(δ(q,x),), x *. DFA M L(M): L(M) = { x δ(q,x) F } ) M = ( {p, q, r}, {, }, δ, p, {r} ) δ : δ(p,) = q δ(p,) = p δ(q,) = r δ(q,) = p δ(r,) = r (r,) = r L(M)? δ(p,) = δ(p,) = δ(q,) = δ(r,) = r F L(M). L(M)? δ(p,) = δ(p,) = δ(q,) = δ(p,) = q F. L(M). δ : mtrix (trnsition tble) ) input symbols δ p q p q r p r r r, δ(q,) = p q p., strt., strt p q r (+)*(+)* Identifier : letter, digit strt S letter A

8 Algorithm : ssume M = (Q,, δ, q, F); begin currentstte := q ; (* strt stte *) get(nextsymbol); while input not eof do begin currentstte := δ(currentstte, nextsymbol); get(nextsymbol) end; if currentstte in F then write( input recognized ) else write( input not recognized ); end. Non-deterministic Finite Automt(NFA) δ(q,) = {p, p 2,..., p n },., q, p, p 2,..., p n. ) NFA M = ( {q,q,q 2,q 3,q f }, {,}, δ, q, {q f } ) q {q, q 2} {q, q 3} q {q, q 2} {q, q 3} q 2 {q f} φ q 3 φ {q f } q 4 {q f } {q f } δ(q,) = φ, δ(q,). δ (i) δ : Q x * 2 Q δ( q, ) = { q } δ( q, x ) = U δ(p,), V T x V T*. p δ( q, x ) (ii) δ : 2 Q x * 2 Q k δ({p, p 2,..., p k }, x) = δ(p i, x), i= δ ) L(M)? δ({q }, ) = δ({q,q 3 }. ) = δ({q,q 2 },) = δ({q,q 3 },) = {q,q 3,q f } L(M) ( {q,q 3,q f } {q f } φ) ) L(M)?

9 (q, ) (q, ) (q 3, ) (q,) δ(q 2,) φ (q,) (q 3,) φ q q 3 q f NFA :. DFA :. NFA DFA. NFA : δ(q,, 2... n ) = δ({q,q 2,,q i }, n ) = δ({p,p 2,,p j }, i... n ) = {r,r 2,...,r k } δ δ () Q' = 2 Q, {q, q 2,..., q i } Q', where q i Q. Q' [q, q 2,..., q i ]. (2) q ' = {q } = [q ] (3) F' = {q Q' q F } (4) δ ' : δ '([q, q 2,...,q i ], ) = [p, p 2,..., p j ] if δ({q, q 2,..., q j }, ) = {p, p 2,..., p j }. L(M) = L(M')., δ '(q ',x) F' δ(q, x) F φ.

10 ) NFA M = ({q,q }, {,}, δ, q, {q }), δ q {q, q } {q } q φ {q, q } DFA M' = (Q',, δ ', q ', F'), Q' = 2 Q = {[q ], [q ], [q,q ]} q ' = [q ] F' = {[q ], [q,q ]} ' : '([q ],) = ({q },) = {q,q } = [q,q ] '([q ],) = {q } = [q ] '([q ],) = (q,) = φ '([q ],) = (q,) = {q,q } = [q,q ] '([q,q ],) = ({q,q },) = {q,q } = [q,q ] '([q,q ],) = ({q,q },) = {q,q } = [q,q ] : [q ] = A, [q ] = B, [q,q ] = C. δ A C A B φ C C C C B strt A C, B (inccessible stte) strt A C, : (q, ω) * (p, ), p (ccessible stte). 2) NFA DFA NFA : δ q {q,q 2 } {q,q 3 } q {q,q 2 } {q,q 3 } q 2 {q f } φ q 3 φ {q f } q f {q f } {q f } DFA : δ ' [q ] [q q 2 ] [q q 3 ] [q q 2 ] [q q 2 q f ] [q q 3 ] [q q 3 ] [q q 2 ] [q q 3 q f ] [q q 2 q f ] [q q 2 q f ] [q q 3 q f ] [q q 3 q f ] [q q 2 q f ] [q q 3 q f ]

11 - NFA: M = (Q,, δ, q, F) -. δ : Q ( {} ) 2 Q : -CLOSURE : s - CLOSURE(s) = {s} {q (p, )=q, p -CLOSURE(s)} T - CLOSURE(T) = -CLOSURE(q) q T ) -NFA CLOSURE strt b A B C D - CLOSURE (A) = {A, B, D} - CLOSURE({A,C}) = -CLOSURE(A) - CLOSURE(C) = {A, B, C, D} ) -NFA DFA strt c 2 3 b 4 strt A c c B C b D δ CLOSURE() = {,3,4} CLOSURE(2) = {2} [,3,4] [2] b φ c CLOSURE(3) = {3,4} [3,4] [2] φ [3,4] [4] A = [,3,4], B = [2], C = [3,4], D = [4] φ CLOSURE(4) = {4} [4] φ φ CLOSURE(3) = {3,4} [3,4] φ φ φ (stte merge) : * distinguishes q from q 2 if δ(q, ) = q 3, δ(q 2, ) = q 4 nd exctly one of q 3, q 4 is in F. : δ δ δ

12 ) b A F b D b b C b B E b : {A,F}, {B, C, D, E} :,. : {A,F}, {B,E}, {C,D} : {B, C, D, E} : {A,F}, {B,E}, {C,D}. δ b [AF] [AF] [BE] [BE] [BE] [CD] [CD] [CD] [AF] <step > ; <step 2> ; <step 3> DFA M' = (Q',, δ ', q ', F'), () Q' : (b) δ '([p],) = [q] if δ(p,) = q. (c) q ' is [q ]. (d) F' = {[q] q F}. : (reduced) () (ccessible). (2). ) M = ({A,B,C,D,E,F}, {,}, δ, A, {E,F}) FA δ A B C B E F C A A D F E E D F F D E : {A, B, C, D}, {E, F} : {A, C}, {B, D}, {E, F} δ [A,C] = p q p [B,D] = q r r [E,F] = r q r

13 Progrmming < 3.2> NFA NFA_to_DFA DFA Minimiztion _of_dfa Reduced DFA Input Design Dt Structure [ ] L,L 2 finite utomton lnguges (FAL), (i) L U L 2 (ii) L L 2 (iii) L * FAL. ( ) M = (Q,, δ, q, F ) M 2 = (Q 2,, δ 2, q 2, F 2 ), Q Q 2 = φ ( renming) (i) M = (Q U Q 2 U {q },, δ, q, F) where, () q is new stte. (2) F = F U F 2 if L U L 2. F U F 2 U {q } if L U L 2. (3) () δ(q,) = δ(q,) U δ(q 2,) for ll. (b) δ(q,) = δ (q,) for ll q Q,. (c) δ(q,) = δ 2 (q,) for ll q Q 2,. f f.. (ii) M = (Q U Q 2,, δ, q, F) () F = F 2 if q 2 F 2 F U F 2 if q 2 F 2 (2) () δ(q,) = δ (q,) for ll q Q -F. (b) δ(q,) = δ (q,) U δ 2 (q 2,) for ll q F. (c) δ(q,) = δ 2 (q,) for ll q Q 2. M M 2. M. M : strt A B => * M 2 : strt X Y => * M M 2 : strt A B Y => **

14 (iii) L : FAL => L * : FAL. Construct M' = (Q U {q '},, δ ', q ', FU{q '}), δ ' : () δ '(q,) = δ(q,) if q Q - F nd. (2) δ '(q,) = δ(q,) U δ(q,) if q F,. (3) δ '(q ',) = δ(q,) for ll.., rc., M : A B δ '(B,) = δ(b,) U δ(a,) = {B,A} δ '(B,) = δ(b,) U δ(a,) = {B} δ '(q ',) = δ(a,) = {A} δ '(q ',) = δ(a,) = {B}. M ' : q ' A B, regulr grmmr (rg) finite utomt (f) regulr expression (re) re => f : scnner genertor. RG & FA 2. FA & RE. (RG) (FA),. RG FA Given G = (V N, V T, P, S), construct M = (Q,, δ, q, F). () Q : V N U {f}, f. (2) : V T. (3) q : S. (4) F: if L(G) then {f} else {S, f} (5) δ : if A B P then δ(a,) B. if A P then δ(a,) f.

15 ) FA. G = ({S, B}, {, }, P, S) P: S S S B S B S B M = (Q,, δ, q, F), Q : V N {f} = {S, B, f} : V T = {, } Q : S F : {f} δ S {S} {B, f} B {S} {f} f Ø Ø FA RG RE Given M = (Q,, δ, q, F), construct G = (V N, V T, P, S). () V N = Q (2) V T = (3) S = q (4) P : if δ(q,) = r then q r. if p F then p. ex) strt p q r, p p q q p r r r r L(P) = (+)*(+)* RE FA ( scnner genertor) For ech component, we construct f inductively :. : i f Σ : i f 2. () N + N 2 N i f N 2

16 (2) N N 2 i N N 2 f (3) N* i N f [ 3] (+b)* (Simplifiction) -rc rc. A B A RE -NFA ( ) DFA [ 33].. L is generted by some regulr grmmr. 2. L is recognized by some finite utomt. 3. L is described by some regulr expression. (Closure Properties of Regulr Lnguge) [ ] If L nd L 2 re regulr lnguges, then so re (i) L U L 2, (ii) L L 2, nd (iii) L *. ( ) (ii) Since L nd L 2 re RL, RG G = (V N, V T, P, S ) nd RG G 2 = (V N2,V T2, P 2, S 2 ), such tht L(G ) = L nd L(G 2 ) = L 2. Construct G=(V N U V N2,V T U V T2,P,S ) in which P is defined s follows : () If A B P, A B P. (2) If A P, A S 2 P. (3) All productions in P 2 re in P. We must prove tht L(G) = L(G ). L(G 2 ). Since G is RG, L(G) is RL. Therefore L(G ).L(G 2 ) is RL. ) P : S S ba A A P 2 : X X Y Y Y P : S S ba A A X X X Y Y Y

17 (iii) L : RL, RG G = (V N, V T, P, S) such tht L(G) = L. Let G' = (V N U {S'}, V T, P', S') P' : () If A B P, then A B P'. (2) If A P, then A, A S' P'. (3) S' S P'. We must prove tht L(G') = (L(G))*. ω L(G), S =>* ω. S' => S =>* ωs' =>* ω * S' => ω *. (L(G))* = L(G'). ex) P : S S, S b P' : S S, S b, S bs', S' S, S'. note P : S = S + b = *b P' : S = S + b + bs' = *(b+bs') = *b + *bs' S' = S + = *bs' + *b + = (*b)*(*b + ) = (*b)*(*b) + (*b)* = (*b)*. [ ] L, m, xyz y., i xy i z L. (proof)m = (Q,, δ, q, F) n FA L(M) = L m = n. n M. M. δ(q,xyz) = δ(q,yz) = δ (q,z) = q f F y x z q q q f y n y, i. δ(q,xy i z) = δ(q,y i z) = δ(q,y i- z) =... = δ(q,z) = q f F. Since w = xyz L, xy i z L for ll i. ex) L = { n n n } is not type 3. (Proof) Suppose tht L is regulr. Then for sufficiently lrge n, n n cn be written s xyz such tht y ω nd xy i z L for ll i. If y + or y +, then xz = xy z L. If y + +, then xyyz L. We hve contrdiction, so L cn not be regulr. n cb n not rl n cb m rl

untitled

untitled 5. hamks@dongguk.ac.kr (regular expression): (recognizer) : F(, scanner) CFG(context-free grammar): : PD(, parser) CFG 1 CFG form : N. Chomsky type 2 α, where V N and α V *. recursive construction ) E