Formula Sheets: Context Free Grammar, Languages and Push Down Automata

 Page 1


Con text F ree Grammar, Languages & Pushdo wn A utomata
Con t ext-F ree Grammar (CF G)
CF G Definition
• Grammar: G = (V,T,P,S) , where V is v ariables, T is terminals, P is pro ductions, S is start sym b ol.
• Pro d uction: A?a , where A?V , a? (V ?T)
*
.
Language Generated
• Language: L(G) ={w?T
*
|S ?
*
w} , where ?
*
denotes deriv ation.
Am biguit y
• Grammar is am biguous if ?w?L(G) with m ultiple leftmost deriv ations or parse trees.
Simplification of CF G
• Remo v e useless sym b ols: V ariables not deriving terminals or unreac hable from S .
• R emo v e ? -pro ductions: A?? , unless ??L(G) .
• Re mo v e unit pro ductions: A?B , where A,B ?V .
Normal F orms
• Choms ky Normal F orm (CNF): Pro ductions of form A?BC or A?a , where B,C ?V , a?T .
• Greibac h Normal F orm (GNF): Pro ductions of form A?aa , where a?T , a?V
*
.
Con text-F ree Language s (CFL)
CFL Definition
• Language generated b y CF G or accepted b y Pushdo wn A utomata (PD A).
Pumping Lemm a
• F or CFL L , ?p (pumping length) suc h that for w ? L , |w| = p , w = uvwxy , |vwx| = p , |vx| > 0 ,
uv
i
wx
i
y?L for all i= 0 .
Closure P rop erties
• Union: L
1
?L
2
is CFL.
• Concatenation: L
1
·L
2
is CFL.
• Kleene Star: L
*
is CFL.
• Non-closure : In tersection (L
1
nL
2
), Complemen t (S
*
\L ) not ne cessarily CFL.
Pushdo wn A utomata (PD A)
PD A Defini tion
• Definition: M = (Q,S,G,d,q
0
,Z
0
,F) , where Q is states, S is input alphab et, G is stac k alphab et,
d :Q×(S?{?})×G? 2
Q×G
*
, q
0
is start state, Z
0
is initial stac k s ym b ol, F is final states.
• T ransition: (q
'
,?)?d(q,a,X) , where a? S?{?} , X ? G , ? ? G
*
.
A cceptance Mo des
• By Final State: L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?),q?F} .
• By Empt y Stac k: L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?)} .
Deterministic PD A
• A t most one transition p er (q,a,X) and no ? -transitions if input transition exists.
• Language: Subset of C FLs, not all CFLs (e.g., {ww
R
} not DPD A-recognizable).
1
Page 2


Con text F ree Grammar, Languages & Pushdo wn A utomata
Con t ext-F ree Grammar (CF G)
CF G Definition
• Grammar: G = (V,T,P,S) , where V is v ariables, T is terminals, P is pro ductions, S is start sym b ol.
• Pro d uction: A?a , where A?V , a? (V ?T)
*
.
Language Generated
• Language: L(G) ={w?T
*
|S ?
*
w} , where ?
*
denotes deriv ation.
Am biguit y
• Grammar is am biguous if ?w?L(G) with m ultiple leftmost deriv ations or parse trees.
Simplification of CF G
• Remo v e useless sym b ols: V ariables not deriving terminals or unreac hable from S .
• R emo v e ? -pro ductions: A?? , unless ??L(G) .
• Re mo v e unit pro ductions: A?B , where A,B ?V .
Normal F orms
• Choms ky Normal F orm (CNF): Pro ductions of form A?BC or A?a , where B,C ?V , a?T .
• Greibac h Normal F orm (GNF): Pro ductions of form A?aa , where a?T , a?V
*
.
Con text-F ree Language s (CFL)
CFL Definition
• Language generated b y CF G or accepted b y Pushdo wn A utomata (PD A).
Pumping Lemm a
• F or CFL L , ?p (pumping length) suc h that for w ? L , |w| = p , w = uvwxy , |vwx| = p , |vx| > 0 ,
uv
i
wx
i
y?L for all i= 0 .
Closure P rop erties
• Union: L
1
?L
2
is CFL.
• Concatenation: L
1
·L
2
is CFL.
• Kleene Star: L
*
is CFL.
• Non-closure : In tersection (L
1
nL
2
), Complemen t (S
*
\L ) not ne cessarily CFL.
Pushdo wn A utomata (PD A)
PD A Defini tion
• Definition: M = (Q,S,G,d,q
0
,Z
0
,F) , where Q is states, S is input alphab et, G is stac k alphab et,
d :Q×(S?{?})×G? 2
Q×G
*
, q
0
is start state, Z
0
is initial stac k s ym b ol, F is final states.
• T ransition: (q
'
,?)?d(q,a,X) , where a? S?{?} , X ? G , ? ? G
*
.
A cceptance Mo des
• By Final State: L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?),q?F} .
• By Empt y Stac k: L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?)} .
Deterministic PD A
• A t most one transition p er (q,a,X) and no ? -transitions if input transition exists.
• Language: Subset of C FLs, not all CFLs (e.g., {ww
R
} not DPD A-recognizable).
1
Equiv alence of CF G and PD A
CF G to PD A
• Construct PD A sim ulating leftmost deriv ations of CF G.
• Stac k stores v ariables/terminals; p op v ariable, push pro duction righ t-hand side.
• Time Complexit y: O(|w|) for deterministic CFL, O(|w|
3
) for general CFL (CNF parsing).
PD A to CF G
• Construct CF G where v ariables represen t stac k configurations.
• Pro d uctions: F or (p,?,A)? (q,a) , generate A
pq
?aA
rs
··· for transitions.
2