Definition: A phrase structure grammar is a 4-Tuple



Definition: A phrase structure grammar is a 4-Tuple

G(V,(,P,S) Where

V=Total Vocabulary

(=Terminal Alphabet (finite)

S =Start Symbol ( V-(=N set of non-terminal symbols

P=finite set of Production rules of the form

(((, Where ( ( V(NV(

( ( V(

Notation: Upper Case: Nonterminals

Lower Case: Terminals

(.X. (={a,b}, N= {A,S}

S( ab, S(aASb, A(bSb

AS(bSb, A(e, aASAb(aa.

Definition: “ Directly Generates” relation(()

(1((1, where (, ( ( V*

iff (1=a1(a2, (1= a1(a2

and ((( ( P

(.X.

S(ab

S(aASb( abSbSb, Notation S(abSbsb

Definition (* called the reflexive transitive closure

Sentential forms of G, S(G)={( ( V(/S(((}

The language generated by grammar:

L(G)=S(G)(((={w ( ((/S((w}

(.X. S(ABC E0(0E then L(G)={xx / x ( {0,1}(}

AB(0AD E1(1E

AB(1AE AB(e

DC(B0C C(e

EC(B1C 0B(BQ

D0(0D 0B(B0

D1(1D

Definition: Right linear Grammar

Rules of Form: A((B

A((, ( ( ((

A,B ( N

(.X.

G:S(aS/a, L(G)=a+

(.X FSA(Grammar

a

b L(A)=a(ba(.

Q2

a

G: Q1(aQ1

Q1(bQ2

Q2(aQ2/e since Q2=final state

Algorithm:

If A=(Q,(,((q1,F) F.S.A.

Then corresponding Grammar G=(V,(, P( q1)

The alphabet (= is the set of terminal symbols, the states Q= is the non terminal symbols

P={q(a((q,a)/(q,a)( Qx(} ( {q(e/q ( F}

Grammar( N.F.S.A(DFSA

G: q1(abq1 L(G)=(ab)( baa(

q1(bq2

q2(bq2

q2(a

ab

q

b a

b

Algorithm:

If G=(V,(,P,S) right linear grammar

Then C=(Q,(, (,{S},F) the corresponding FSA

Where Q=(V-() ( {q}, q (V

F={q}, (=(qi,u,qj) / qi(uqj.( P} ( {(qi,u,q) / qi (u ( P}

Note: not every linear grammar is regular

[Regular=left linear or right linear]

For example ,

S(A

A(aB/e

B(Ab cannot be converted to right linear grammar (language = {anbn}

Redundancies in Context free Grammar ( N0 Proofs)

(CFG: every rule in form: A((, A in N, ( ( V*)

(.X useless symbols

Definition: T ( N useless iff ¬( ( ( ( (: T(((

E(E+E/T/F ( E ( E+E/F

F(F(E/(T)/( F( F*E/a

T(E-T ( T Useless if use T(E-T never can get rid of T)

How to get rid of useless symbols

G=(V,(,P,S) ( G1=(V1,(,P1,S) with no useless symbols

Algorithm (to find useful symbols)

W1={ A ( N= V-Σ / A( x is in P for some x ( (( }

Wk+1= Wk ( { A ( N / A(( is in P for some ( ( ( ( ( Wk)( }

Stop when Wk+1= Wk

For previous example:

W1= { F ( ( }

W2= E ( F

Useless=N-{usefull}

Once useless are found, eliminate any rules that contain a useless symbol.

Unreachable Symbols

Definition G=(V,(,P,S ) Context free,

A ( N=V- Σ, B ( V

Then B is reachable from A iff A (( (B(, (,( ( V(

S( aBa

B(Sb/bCC

C(abb

D((C (D is unreachable)

Algorithm to Eliminate Unreachable symbols

1. Find reachable symbols.

W1(A)= {A}

Wk+1 (A)=Wk(A) ( { c ( V / ( (,( ( V(, B ( WK(A) : B( (C( in P}

(.X. for previous example: W1={S}, W2={S,B,a}, W3(S)={(,S,B,b,C}, W4=W3

Lemma 3.3.1

ti n

( ( (, (=a1….an and (i ( (i, then ( ti=( and ti ( (, (i

i=1

(.X. E ( E+T/T

T ( T(F/F E + T ( E+( + T((

a1 a2 a3 b1 b2 b3

F ( (/(E)

a1 ( b1, a2 ( b2, a3 ( b3

Theorem:

If L is a CFL (Context free Languages) then LT is CFL

Proof:

G=(V,(,P,S), L=L(G), GT=(V,(,PT,S)

Where PT ={ A((T / Where A ( ( in P}

1 1

If A ( ( ( A ( (T

G GT

2 2 1 1

A ( (2 iff A ( (2T ( if A ((1=u1 A1u2 (u1B1u2, A1 ( N, u1,u2 ( (( )

G GT G GT

1 1

A ((1T=u2T A1 u1T ( u2T B1T u1T= (2T

GT GT

Therefore i( for I+1

Class

( (

A ((.,( ( V( iff A ( (T

G GT

(

A ( b

G

1

If A ( (=u1A1u2A2……unAn, ui ( ((,Ai ( N

G

1

A( (T=un+1TAnunTAn-1….u2Ta1u1T

GT

( ti ti

( ( (=u1(1u2(2….un(1un+1, Ai ( (i , ti ( r ( Ai ((iT

G GT

So A( Un+1T An UnT…. A1U1T ( Un+1T (nT….(1TU1T=bT

Chomsky Normal Form

The productions of any context free grammar G with e( L (G)

Can be written in the form :

A(BC, A,B,C ( N

A((, ( ( (

To convert to CNF:

1) Eliminate ( rules and Chain rules

(-rules : A ( v

(.X G:E(TE1

E1(+TE1/( same as E ( E+T /T

Algorithm to Eliminate e-Rules (if ( ( L(G) it will not work)

W1={ A / A((}

Wk+1=Wk( { A/A(( is in P for same ( ( WK( }

Stop when Wk+1=Wk

If A(Wn( A((( @ ( ( L(G) iff S( Wn

Construction of the Productions:

P1= { A( (1(2….(n if A( A1A2…An is in P,

where (i=Ai or ( if Ai ( Wn }

(.X. E(TE1

E1(+TE1 /(

W1={E1}, W2={E1}

P1={ E(TE1/T

E1(+TE1/+T }

(.X. A(A1A2A3

A2((/(

A3(b/( W1={A2,A3}

A1(C A(A1A2A3

A(A1A3

A(A1A2

A(A1

A2((

A3(b

Definition: Chain Rule: is rule of form A(B, A,B ( N

Eliminate Chain Rules:

(.X E(E+T/T

T(T(F/F

F((E)/(

P1: E(E+T/T(F/(E)/(

T(T(F/(E)/(

F((E)/( eliminate ( rules, chain rules

2nd Whenever a right hand side more than 1 terminal or nonterminal

S(TbT ---------( convert to non terminals

T(T(T/C(

as: S(TBT S(TT1

T1(BT

B(b

T(TAT T(TT2

T2(AT

A( (

T(CA

C(c

Greibach Normal Form

A( a(, a ( (, ( ( N(

(.X. A((BCD (1) ( no left recursion –good GNF,

(2) used in operators precedence (compilers)

Grammar ( Chomsky ( Greibach

Lemma 4.6.1 A((1 B (2 Then can replace by A((1b1(2/../(1b1(2

B(b1/b2/…./bn

Lemma 4.6.2 A(A(1/../A(n Then can replace by non-left recurs set of productions

A(b1/../bs

A(b1z/../bsZ/b1/b2/..bs

Z((1Z/../(1Z/(1’../(s

(.X. A(A(1/b1 } same as A(b1z/b1

Z((1Z/(1

W ( (* IF LG(w)=n takes n steps to device w G.N.F

A1(A2A3 A1(A2A3

A2(A1A2/1 A2(A1A2/1(A2(A2A3A2/1

A3(A1A3/0

Not in order ,change it

So now A1(A2A3

A2(1Z1/1

Z1(A3A2Z1/A3A2

A3(A1A3 ( A3( A2A3A3/0 ( A3(1Z1A3A3/1A3A3/0

So now

A1(A2A3 ( A1(1Z1A3/1A3

A2(1Z1/1 G.N.F

Z1(A3A2Z1/ A3A2

A3( 1Z1A3A3/ 1A3A3/ 0 . G.N.F

Z1( 1Z1A3A2A2Z1/ 1A3A2Z1/ 0A2Z1

/1Z1A3A3A2/1A3A3A2/0A2

Greibach Normal form also called m Standard form iff ( A(a(, lg(()( m

av

Given m standard form , m( 3 then we convert ( CFG in m-standard form into (m-1) standard form in 2 standard form have rules of form : Operator precedence Grammar

(.X.: A((

A((B

A((BC

Algorithm to convert m-standard into (m-1) standard

i) A(( will be in P1 if it is also in P and lg(() ( m.

(since (=(BCD.. # of non-terminals is m-1)

(ii) A((B1B2…….Bn-1Bm let B1n-1 Bn @1 add the rule

if : Bn-1( (

add : Bn-1((Bm, now if lg(() ( m-1 ( ( m- ( Nonterminals is ( so adding Bm

lg(()=m ( ( m- 1 Nonterminals: then

B1m-1((B1B2….(Bm-1Bm)

Lg(()=m+1( Bm-1Bm((B1B2….(,)(,) group two

of these

(.X: 3-form

A1(aA1(A2A3)

A1(aA1A2A3 (A2A3)(bA1(A4A3)

A2(bA1A4 ( (A4A3)(d(A4A3)

A3(cA4 A3(cA4

A4(dA4 A4(dA4

A1(aA1(A2A3)

A1(aA1(A2A3) (A2A3)(bA1(A4A3)

(A2A3)(bA1A4A3 A2(bA1A4

A2(bA1A4 A3(cA4

A3(cA4 (A4A3)(d(A4A3)

A4(dA4 A4(dA4

A4(dA4

Operator Grammar (Context free grammar) with productions having right hand side with no two adjacent non-terminals.

(.X A((BcD Valid

A((BCD not valid

A(abCd Valid

2-Standard into Operator

1) Replace each productions of the form A(aBC by A(a[BC] where [BC}is the one Non-terminal

2) After replacing all productions of the form A(aBC as above , first we generate productions for [BC] as follows:

If B((, C(( ( [BC] (((

2-form

A(a[BC] Now B is unreachable so

(.X A(aBC B(b[CD] erace C,D

B(bCD (Step1

C(c

C(c D(d

D(d

Step 2 : [BC](b[CD]c ( L(G1)= abcdc

[CD](cd so L(G) = L(G1)

_____________________________________________________________________

Push Down Automata

(N.P.D.A accepts C.F language but D.P.D.A not accept all C.F languages

P.D.A is a 7 Tuple

A=(Q,(,(,(,q0,z0,F)

Q=Final set of states

(=finite non-empty input symbols

(=finite non-empty push down symbols

q0 ( Q initial state

zo ( ( the initial symbols on stack

F ( Q set of final states

(: Q ( (( ( () ( ( ( Q ( ((

Transitions:

((q,(,z)=(q1,b) means

if in state q and read “a” from input tape , replace z by b on top of stack. Enter state q1

(.X. ((q, a, b)=(q1,e) is a transition which pops b.

((q, a, e)=(q1,b) is a transition which pushes b.

Definition:

The P.D.A M accepts string w(on input tape)

Iff ( derivation (s,w,e) |--….|-- (p,e,e) , where P ( F = final state

Start symbol, initial state

Theorem: Any FSA is equivalent to a PDA

EXAMPLES:

1) Design PDA for { wcwT/ w ( {a,b}(}

states k={S,F} (={a,b,c}, F={f}, (={a,b}

( : { (s,a,e)( (s,a)

(s,b,e) ( (s,b)

(s,c,e)( (f,e)

(f,a,a)( (f,e)

(f,b,b)( (f,e) }

(.X feed it with “abbacabba”

2) { wwT/w ( {a,b}( }

(s,a,e)( (s,a)

(s,b,e) ( (s,b)

(s,c,e)( (f1,e)

(f,a,a)( (f,e)

(f,b,b)( (f,e)

(.X try “abba”

Theorem: G=C.F grammar , W ( (( then S (* W iff S (*L W using left derivations

Definition: Context free grammar (Type 2 in Chomsky Hierachy)

A((, A (N, ( ( V(

{an bn} ( regular but is context free: grammar S(e/aSb)

Theorem: C.F language ( its accepted by a PDA

ALGORITHM: C.F grammar ( P.D.A

let M= ( {p,q},(,V,p,{q})

where (: (p,e,e)( (q,s)

(p,e,A)((q,x) ( rule A(x

(q,a,a)((q,e) ( a ((

(.X Given: V=(S,(,),[,])

(=( (,),[,] )

R:= S(e/SS/[S]/

Construct a PDA???

(.X L={an bm an / n,m ( 1}( {an bm cn / n,m ( 1}

PDA:

A=(Q,(,(,(,qo,c,{q2})

Q={qo,q1,q2}

(=(={a,b,c}

((q0,a,c)((q0,ac) ((q0,a,b)=(q1,e)

((q0,a,a)(( q0,aa) ((q1,e,b)=(q1,e)

((q0,b,a)((q0,ba) ((q1,a,a)=(q1,e)

(q0,(b,b)(( q0,bb) ((q1,e,c)=(q2,e)

((q0,c,b)=(q2,e)

((q2,c,b)=(q2,e)

((q2,e,a)=(q2,e)

((q2,e,c)=(q2,e)

(.X

1) give a grammar for { am bn / m(n}

S(aS/aSb/e

PDA (p,e,e)((q,S) (q,a,a)((q,e)

(q,e,S)((q,a,S) (q,b,b)(\(q,e)

(q,e,S)((q,aSb)

(q,e,s)((q,e)

2) { am bn cp dq / m+n=p+q }

S(aSd/M/N/e

M(aMC/T/e

N(bNd/T/e

T(bTC/e

3) G: S(aSa/bSb/C, L(G)={ WCWR}

P.D.A ?

M={( {p,q},(,V,(,p,{q} ) with

( = { ((p,e,e),(q,S) )

((q,e,S),(q,aSa))

((q,e,S),(q,bSb))

((q,e,S),(q,c))

((q,a,a), (q,e))

((q,b,b),(q,e))

((q,c,c),(q,e)) }

DEFINITION:

M=PDA is simple iff

(q,u,b), (p,r) ( ( ( | b | ( 1

And

((Q,U,E),(,R) ( ( ( (( q,u,A), (p,r,A) ( (, ( A ( ( ( start symbol

Theorem: if M is PDA then there is a simple PDA which accepts same language

Proof:

1) if ( Transitions ((q,u,b),(p,r) ( ( with | b | ( 1

replace it by a sequence of transitions which sequentially pop the symbols of b

i.e, replace ((q,u,b),(p,r) by : if b=B1…Bn

(q,e,B1),(t1,e)

(t1,e,B2),(t2,e)

((tn-2,e,Bn-1)(tn-1,e))

((tn-1,u,Bn),(p,r))

2) Add to (

The transitions

(q,u,A)(P,rA) whenever (q,u,e)(p,r) ( ( ( A ( (

Simple PDA ( Grammar let A=(Q,(,(,(,q0,Zo,F)

G=(V,(,P,S)

where F={f}

Where V=( ( (Q(((Q)

S=(q0,zo,f) where F={f}

P:

1) ( u ( 1, ( ( ( ( {e}, Z,Z1……,Zk ( (

and ( q,p,q1,……..qk ( Q

if

((q,a,z)=(p,z1…,zk)

then

(q,Z,qk)( ( (p,Z1,q1)(q1,Z2,q2)….(qk-2,Zk-1,qk-1)(qk-1,Zk,qk)

2) if

((q,a,Z)=(p,e)

then

(q,Z,p)( (

L={an bn) S={qo ,e , q1 )

PDA: (qo,a,e)=(q0,a)

(q0,e,e)=(q1,e,e) ( simple (={a}

(q1,b,a)=(q1,e)

simple

(q0,e,q0)(a(q0,a,q0)

((q0,a,e)=(q0,a)( (q0,e,q1)(a(q0,a,q1)

(q0,a,q0)(a(q0,a,q0)(q0,a,q0) (q0,a,q0)(a(q0,a,q1)(q1,a,q0)

((q0,a,a)=(q0,aa) ( (q0,a,q1)(a(q0,a,q0)(q0,a,q1)

(q0,a,q1)(a(q0,a,q1)(q1,a,q1)

((q0,e,e)=(q1,e) (q0,a,q1)(e

((q0,e,a)=(q1a) (q0,a,q0)(e(q1,a,q0)

((q0,b,a )=(q1,e) (q0,a,q1)(e(q1,a,q1)

S(aA/e

B(aC

C(D/aaCA/aAE

E(b

Pumping lemma for C.F.Languages

Let G= C.F Grammar

Then ( K: each String W ( L(G) with length(w) can be written as:

W=uvxyz in such a way that either u or y ( (

And u vn x yn z ( L(G) ( n(0

(.X Prove { an bn cn : n(0 } ( C.F

G.C.F @1 H.C.F ( G ( H C.F ?

G compliment C.F ?

NO:

(.X G={ anbncm / m,n ( 0 } C.F

H={ ambncn / m,n ( 0 }

But G(H ( C.F

If G.C.F ( (*-G C.F ?

(*- ( (*-G ) ( ( (*-H) = G ( H

if C.F ( G ( H contracdiction.

PDA:

1) S(aSa/bSb/C

L(G)={ WCWT / W ( {a,b}(}

q0( start state

z0(start symbol of stack

((q0,d,z0)((q1,z0,d)

((q1,d,A)((q1,A,d)

((q2,d,d)((q2,A)

((q2, (,Z0)((q3,z0) q3:final state

2) S(aSa/bSb/( L(G)= { WWt/ W ({a,b}(}

CA ( {a,b}

((q0,c,z0)={(q0,z0,c} ((q0,C,A)=(q0,AC)

((q0,(,z0)=(q1,() ((q0,c,c)={(q0,c,c),(q1,()}

((q1,c,c)=(q1,(), ((q1,(), ((q1,(,z0)=(q1,()

Accepted Language

1) T(A) = { w ( (( / (q0,w,z0) (( (q1,(,(), for some q(F, ( ( ((}

2) N(A)={ w ( (( / (q0,w,z0) (( (q1,(,( ), for some q(Q

3) L(A)= {w ( (( / (q0,w,z0) (( (q1,(,(), for some q(F, q(F}

Deterministic PDA

1) ((q,(,z) ( 1

2) if ((q,(,z)( (( ((q,a,z)= (, ( a ( (

Algorithm to Construct PDA from grammar

i) ((q,(,Z)= { (q,(t)/Z(( is in P}

ii) ( ( ( (, ((q,(,()={(q,()}

(.X S(aSb/(

if top Stack Nonterminals replace it by

Corresponding rule remain same state

( State always contain sentential form

S

S a if next input symbol a ( b

S

((q0,(,S)={(q0,bSa),(q0,()}

((q0,(,()={(q0,()}

((q0,b,b)={(q0,()}

if grammar is in G.N.F then Algorithm reduces to : (q,(,Z)({(q,(,(t)}

where Z(a( in P

Given PDA construct grammar

Basic Idea

(q1,z1,q2) is a nonterminal in grammar

iff{(q1,(,z1) |--( (q2,() ( {(q1,Z1,q2) ( ( (, (((( } S = (q0,Z0,f)

((q,a,Z) = (P,ZkZk-1) then (q,z,qk)(((p,z1,q1)(q1,z2,q2)….

….(pk-2,zk-1,qk-1)(pk-1,zk,qk)

(.X

1) A: ((q0,1,z0)={(q,()}, L(A)={1}

(q0,z0,q1)(1

2) ((q0,1,z0)={(q0,z0,z1)} (1)

((q0,1,Z1)={(q0,()} (2)

((q0,0,Z0)={(q0,()} (3)( D (L

(q0,Z0,q0)(0

(q0,Z1,q0)(1

(Q0,Z0,Q0)(1(Q0,z1,Q0)(Q0,z0,Q0)

CLOSURE of CFL

1) Union: S(S1/S2, Si start symbol for Gi

2) Concatenation S(S1S2

3) Kleene , S(S1S/(

4) Not closed under ( (.x {aibici/i(1} not CF

{aibicj/j(, I (1} CF

{cibjcj/ i(1,j(1} CF

5) not closed under complementation

__ __ __ __

L2(L1 = L1(L2, L1(L1 = L1(L2

If L= (deterministic)(unambiguous)CFL @1 R is regular

then L(R is CFL (deterministic)(unambiguous)

Proof:

P=PDA, A=FSA ~P1=L(P)(L(A)

P1 simulates moves of P on ( without changing state of FSA (q,q1) state in P1 where q (P, q1 (A

((q,a,Z)=(q1,a) for P

(A(q1,a)=q1 for A

P1 accepts when both P,A accept

Theorem: L is CFL, R regular ( L-R is C.F.L

_

Proof: L-R=L(R= CFL

TURING MACHINES

Definition: A Turing machine T

T=(Q , ( , Q0 , ( )

(= transform function.

(: (Q-{H} * ( ( Q * ( * {L,R,S}

(.X ((Q,X)=(Q1,X1,L) means replace X ( ( by X1 @ move reader to head to left.

a # b c #

Machine Stops if :

1) reaches the halting state H (machine halts)

2) ( says move to ptr to left @’ it’s already on the leftmost cell or there exits cancel instruction to move the machine at that input (machine hangs).

Notation:

1) a

2) ((Q,X)=(Q1,X1,L)

X/(X1,lRs)

(.X Def Let L be a language of alphabet ( @1 #, $ ( (

L is Turing recognizable ( ( Turing machine T:

1) the tape alphabet of T contains ( ( { $,#}

2) if ( ( ((

@1 on tape [Q0,$ (]

then

if σ(L the machine will halt at [H,$,Y]

if σ ( L, T will halt at [ H,$N]

(.X Built T to recognize {1n/n=1,3,5…}

Tape Symbol

| |1 |$ |# |Y |N |

|Q0 | |(Q1,$,R) | | | |

|Q1 |(Q2,1,R) | |(Q3,#,L) | | |

|Q2 |(Q1,1,R) | |(Q4,#,L) | | |

|Q3 |(Q3,#,L) |(Q5,$,R) |(Q4,#,L | | |

|Q4 |(Q4,#,L) |(Q6,$,R) |(Q4,#,L | | |

|Q5 | | |(H,N,L) | | |

|Q6 | | |(H,Y,L) | | |

|Q7 | | | | | |

1 / (1,R) x( $ / (#,L)

$ / ($,R)

1 / (1,R) # / (#, L) $ / ($ , R)

# / (#, L) # / (Y, L)

# / (N, L)

$ / ($, R)

{anbncn/ n=0,1,2,3,…}≠ context free [ does not exist PDA] but there exists Turing Machine

Exercise: $/($,R) a/(a,R)

a) What does this do ?

#/(#,S)

Move all the way to the right

B/(b,R)

b) Given x/(X,R)

$/($,R) x/(X,R)

# / (#,R)

Input tape

What is the final Configuration?

Go all the way to right @1 stop at 2 blanks in a row $ X X # #……

Notation:

(M1(M2 where Mi=Turing Machine

When M1 halts, q0 to M2

(M1(M2 if M1 halts @’ header is at X, Start M2

x

M2

(M1

M3

Notation:

X,y,z w if Current Input =x,y or Z machine should proceed

With W=↓ to what is present

X,y W

(.X (M1 M2

Means is after M2 executes and Current Symbol =equal as when M2 was reduced , go @’ repeat M1.

Useful Machines: x/(x,R) x/({x,L)

R: L: y/(y,L)

Y/(y,R)

#/(#,L)

#/(#,R)

x/(x,S) y

Rx: R

Y/(y,S)

X: #

#/(#,S)

y

x

R┐x: ( R Lx: -( L

#

x

L┐x:(L

X,y w x,y σ

SR: # L L RσL

R R#R#W

#xyyxx# #yxy##xxy# xy#yx## Erase y if # on left of y

##xyyx# # #yxy#xxy# xy##x##

x,y w x,y σ

SL: # R R L LσR

#

L L#L#W

(.X Transform #W# to #W#W#

W({x,y}(

X,y w

R#R#L#L# R #R#R#WR#L#L#W

Machine for {xnynzn}

L#

X y z # # $

# R SL SL SL L Rs

y,z #,z R R

x,# #

Z,# x,#

R

Grammar for {XnYnZn} Non CF

S(xyNSZ

S(e

yNx(xyN

yNz(yz

yNy(yyN

Turing Machine

A b a a

Turing Machine: (K,(,(,S)

Where

K=finite set of States( h does not belong to K)

(=alphabet ( # ( ( )

s ( k= Initial state

(: K * ( ( (K ( {h}) * ((({L,R})

((q,a)=((p,b) means: if in state q @’ scanning ‘a’ in input tape

( go to state p @1 if b ( ( rewrite a as b

if does not belong to (, b=L move head left, b=R move head right

(.X Erases a’s on Tape

|Q |σ |((q, σ) |

|Q0 |a |(q1,#) |

|Q0 |# |(h,#) |

|Q1 |a |(q0,a) |

|Q1 |# |(q0,a) |

a) M=(K,(,(,S)

K={q0,q1}

(={a,#}

s=qo

Trace:

(q0,aaa)((q1,#aa)((q0,#aa………….

Notation:

Configuration:

a a b a # #

Assume:

Input surrounded by blanks #:

# a b a b # # #

When start : Tape head positioned on blank following Input

M halts on Input w iff

(S,#w#)((h,anything)

(otherwise hangs)

Definition: Let f:((((1(: f(w)=u.

A Turing Machine M=(K,(,(,S) computes f iff (0,(1 is a subset of ( @’ if f(w)=u then (S,#w#)((h,#u#)

[ f is called Turing Comutable]

(.X f:{a,b}(({a,b}(:w(w=replace a’s with b’s @’ b’s with a’s

M=(K,(,(,S)

K={q0,q1,q2}

(={a,b,#}

S=q0

|q |σ |((q,σ) |

|Q0 |a |(q1,L) |

|Q0 |b |(q1,L) |

|Q0 |# |(q1,L) |

|Q1 |a |(q0,b) |

|Q1 |b |(q0,a) |

|Q1 |# |(q2,R) |

|Q2 |a |(q2,R) |

|Q2 |b |(q2,R) |

|Q2 |# |(h,#) |

(:

Trace: (q0,#aab#)(..((h,#bba#) to compute fuctions: f:N(N\ represent n(N as a string of n 1’s 5:11111 etc

(.X. f(n)=n+1

M=(K,(,(,S)

K={q0}

(=(I,#}

S=q0

(:

|q |σ |((q,σ) |

|Q0 |I |(h,R) |

|Q0 |# |(q0,I) |

(.X (q0,#II#)(…((h,#II#)

f(n)=2n (q0,$)((q0,L)

(q0,#)((q0,L)

(q0,1)((q1,$)

(q1,$)((q1,R)

(q1,#)((q0,$)

Def: Let y,N does not belongs to (0

L is a subset of (0( is Turing Computable iff

XL:((({Y,N} is turing computable ( w ( (0(

Xl(ww)= Y, if w ( L

N, if w does not belongs to L

(.X (0={a}, L={W((0(/|W|=even}

M=(K,(,(,S) , K={q0,……,q6} , (={a, y , N,#}

(:

|Q |σ |((q,σ) |

|Q0 |# |(q1,L) |

|Q1 |( |(q2,#) |

|Q1 |# |(q4,R) |

|Q2 |# |(q3,L) |

|Q3 |( |(q0,#) |

|Q3 |# |(q6,R) |

|Q4 |# |(q5,Y) |

|Q5 |Y |(h,R) |

|Q5 |N |(h,R) |

|Q6 |# |Q5,N) |

Definition:

a) Turing Machine M Accepts string w((( iff M halts on input W

b) Turing Machine M accepts a language L is a Subset (0( iff L={w((0( /M accepts W}

c) language L is Turing Computable iff there exists Turing Machine M which accepts It

Theorem: Turing Decidable ( Turing acceptable

(.X L={w({a,b}( / w has at least one a }

L accepted by M L also decidable by M

(:

|q |σ |((q,σ) |

|Q0 |a |(h,a) |

|Q0 |b |(q0,I) |

|Q0 |# |(q0,L) |

|q |σ |((q,σ) |

|Q0 |a |(h,Y) |

|Q0 |b |(q0,L) |

|Q0 |# |(q0,L) |

Combining Turing Machines

Basic Machines

1) there exists symbol writing machine for each symbol in ( for a((:W( = (K,(,(,S), K={q}, S=q, ((q,b)=(h,a), ( b((

2)VL=L head moving mahines

VR=R

K={q},S=q, (L (q,a)=(h,L), (a ( (

Start with input in tape , apply machine M1.

When M1 halts , apply M2 to whatever is left on tape , if current tape symbol is a.

If Current tape symbol is b, apply machine M3

a

b Machine starts on tape square, moves to right until it

> c finds A blank;”#”,@’halts

c

a, b, #

> R R Move right, if see a or b # move right again

.

> R R Move right, two squares

Unlabelled arc≡all ( assumed as labels or RR

> R # means > R σ≠#

What does this do?

σ≠#

. > R L σ Scans right till it finds a non-blank, goes left, copies nonblank to its

square .

# Lσ≡L(σ

R#: >R # Find 1st blank to right of current space.

L#: >L #

R#: >R # find first nonblank to the right of current

square

L#: >L #

(Copying machine)

(. X. Built machine e # W# #W#W#

((#

>L# R R#R#(L#L#(

#

R# (halts here)

Try #abc#

Left shifting machine.

#W#(W# (assume W has no blanks)

σ≠#

SL: : >L# R LσR

#

L#

-------------------------------------------------------------------------------------------------------------

SR: Right shifting machine

#W#(##W# (assume W contains no blanks)

--------------------------------------------------------------------------------------------------------------

Prove f:(0*((0*: f (w)=ww is computed by C SL (copy followed by shift left)

C SL

#W# #W#W# #W#W#

Machine to compute:

f:(0*((0*: f (W)=WWR

.

>L σ≠#

#R#σL#σ

#

R#

-------------------------------------------------------------------------------------------------------------

L={W({a, b}*: W=WR}

#W# a#W erase symbols from left, right of W as long as match. If

empty left replace a by Y else by N

>SRLaRR σ≠# #R#L σ

#L#

# # Z≠σ, #

__

#L #

L##R Y R #

L##R N R

(0={a, b, c}

L={W((o*/W has equal #’s of a’s, b’s, c’s}

Go through left to right 3 times, 1st searching for a

2nd searching for b

3rd searching for c

If it finds them, it then replaces them with 3 d’s.

If no more a’s, b’s, c’s halt. (all d’s).

a

d b, c,d a a,c,d b a,b,d c

>L b,c L dR#L dR#L dR#

$ $ # #

halt RNR

RYR

Turing machines with K-tapes or with ∞ tapes on both ends are equivalent to standard Turing machines.

F: N+(N+ is Turing compatible

Iff Э Turing machine T:

[θ0, $ 11…11] * [11, $ 111…. 11]

n 1’s f (n) 1’s

(. X f (n)=2n

b/(b, R) 1/(1,R)

a/(a, R) b/(b, R) X≠$/(X, L)

$/($, R) 1/(a, R)

> Q0 Q1 Q2 #/(b,c) Q3

#/(#, L)

$/($, R)

$/($, S)

Q4 H

X≠$/(1,L)

Algorithm ≡ Turing machine

Church-Turing thesis (not proved)

Turing Machine for {Xn Yn Zn}

L# ≠ #

X y z #

R SL SL SL L

x y y z

x y

R

y, z R

≠ #

#, z #,z #,x #,x

R

A non-context free grammar for {Xn Yn Zn}

S(xyNSZ/e

yNX(xyN

yNZ(yZ

YNy(yyN

f(n)=2n is Turing Compatible.

b/(b, R) 1/(1,R)

a/(a, R) b/(b, R) x≠$/(x,L)

$/($, R) 1/((, R) #/(b, L)

>

$/($, R)

#, (#, L)

$/($, S)

halt

X≠$/(1,L)

Pascal, C, etc are context free

(. X If C1 then C2 else C3.

Grammar 1:

(IF then /

IF then else / (

IF C=0 then IF 0=1 then A=3 else A=4 can have 2 derivation trees.(2 ways to parse it)

IF C=0 then

IF D=1 then A=3 else A=4

(OR)

IF C=0 then else A=4

IF D=1 then A=3

Therefore two different meanings

1) Given grammar G, Э’ algorithm to decide if its ambiguous or not.

2) Halting problem is undecidable.

Note: Its possible that G ambiguous, G’ unambiguous but L (G)=L (G’)

(. X. for if. …then …else:

(S1/S2//

S1(IF then S1/

IF then S2 else S1/

S2(IF then S2 else S3/

Only 1 way to parse

IF C=0 then S1

IF D=1 then S2 else S1

A=3 A=4

Parsing

Construct derivation tree for a sentence in language, or say cant be parsed

Question: a sequence of productions uniquely defines the tree?

(. X 1) 2 distinct productions can give same tree.

1 E(E+T 1, 2,4,6,4,6(a+a

2 E(T E((

3 T(TxF 1,4,6,2,4,6(a+a ≠ but same tree

4 T(F E(

5 F((E)

6 F(a

2) Same sequence of productions gives different trees.

1 2 2 3 3 3

S(A S(A(AOA(AOAOA(10AOA(1010A(10101

1 2 2 3 3 3

A(AOA S(A(AOA(AOAOA(AOAO1(AO10(110101

A(1

But trees different.

If both derivations are left most then no problem with 2.

Definition: A left parse of a string σ is a left most derivation of σ.

Parsing

Top down parsing Bottom up parsing

…….

1 AN

Definition: top-down parsers using left derivations ≡LL parsers

(. X

S(aAS/b parse σ = abbab

A(bSA/a

S

????

a b b a b

Assume ( string σ ends with a $ sign.

Let G=((, N, S, P) grammar.

A top-down parser for G is a non-deterministic PDA.

M with only one state Q, and an output tape.

Tape input for M=(, $

(=stack alphabet =(, N, #

a1 a2 ------- ai ai+1 ------- an $ ----------

rj

.

.

r1

n1 na ------ nk

#

Stack output tape

Notation: [ aiai+1,…. An$, rjrj-1….r2r1# ,n1n2…nk ]

Tape stack output

Initial configuration of parse is [ a1a2…an$, $#, e ]

The parser works as follows:

1.If X(N is on top of stack (1 on input tape. Replace X by (1---(t where X((1---(t(P ((1 on top of stack) at same time parse writes on output tape the # of the production.

Input header pointer doesn’t move.

2.If X(( on top of stack, a≡ current input symbol. Then if X=a, pop X from stack, move header to right, if X≠a, while Reject on output tape, halt. (σέ=,Yj((UNU{e}

Then ( two cases:

Apply it for: same grammar as above:

(.X. S(BA B(DC DcSc D(d

A(aBA A(e C(bDC C(e

FOLLOW (X): ( X(N

1) Let Nonterminals be S,A1,A2, ---,An.

Define sets M (Ai): M (S)=M (A1)=$

M (A2)=------=M (An)= ø

2) Go through rules in arbitrary but fixed order @’ for each rule perform following changes on sets M:

a) If the rule has only terminals or e on right side do nothing.

b) If rule has nonterminal on right side, then ( X(N express the rule as Ai((Xb @’ do following:

i) Add all terminals of FIRST (b) to M (X) (do not add e)

ii) If e(First (b)(add all symbols of M (Ai) to M (X).

iii) If any of M sets changes in step 2,repeat 2.else set Follow (Ai)=M (Ai), ( I=1,2—n.

(*) ( a smallest index 1< j Assume m>2 ( 2 possibilities. (otherwise ( = e (m-2) or ( ( ( N ( ( @’ we know values of FIRST(()

1) ( smallest index 1 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download