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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
Related searches
- make a phrase with these letters
- make a phrase out of these letters
- create a phrase from letters
- what is a phrase in grammar
- what is a definition essay
- a phrase with two meanings
- sentence structure grammar exercises
- definition of organizational structure pdf
- what is a tuple in python
- is negative 4 a rational number
- great zimbabwe is a structure that uses
- what is a grammar clause