Formula Sheets: Regular & Context Free Languages, Pumping Lemma

 Page 1


Regular & Con text F ree Languages, Pumping Lemma
Regular Languages
Definition
• Language L?S
*
accepted b y DF A, NF A, or defined b y regular expression.
Closure Prop erties
• Union: L
1
?L
2
.
• In tersection: L
1
nL
2
.
• Complemen t: S
*
\L .
• Concatenation: L
1
·L
2
.
• Kleene Star: L
*
.
• Rev ersal: L
R
={w
R
|w ?L} .
Pumping Lemma
• F or regular languageL ,?p (pumping length) suc h that forw ?L ,|w|=p ,w =xyz ,|xy|=p ,|y|>0 ,
xy
i
z ?L for all i=0 .
Con text-F ree Languages
Definition
• Language generated b y Con text-F ree Grammar (CF G) or accepted b y Pushdo wn A utomata (PD A).
Closure Prop erties
• Union: L
1
?L
2
.
• Concatenation: L
1
·L
2
.
• Kleene Star: L
*
.
• Non-Closure:
– In tersection: L
1
nL
2
not alw a ys CFL.
– Complemen t: S
*
\L not alw a ys CFL.
• In tersection with Regular: LnR is CFL, where R is regular.
Pumping Lemma
• 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 .
Grammar and Language Relationship
Regular Grammar
• Righ t-Linear: A?a or A?aB , where A,B ?V , a?T .
• Left-Linear: A?a or A?Ba .
• Language: Regular languages.
Con text-F ree Grammar
• Pro ductions: A?a , where A?V , a?(V ?T)
*
.
• Language: Con text-F ree languages.
1
Page 2


Regular & Con text F ree Languages, Pumping Lemma
Regular Languages
Definition
• Language L?S
*
accepted b y DF A, NF A, or defined b y regular expression.
Closure Prop erties
• Union: L
1
?L
2
.
• In tersection: L
1
nL
2
.
• Complemen t: S
*
\L .
• Concatenation: L
1
·L
2
.
• Kleene Star: L
*
.
• Rev ersal: L
R
={w
R
|w ?L} .
Pumping Lemma
• F or regular languageL ,?p (pumping length) suc h that forw ?L ,|w|=p ,w =xyz ,|xy|=p ,|y|>0 ,
xy
i
z ?L for all i=0 .
Con text-F ree Languages
Definition
• Language generated b y Con text-F ree Grammar (CF G) or accepted b y Pushdo wn A utomata (PD A).
Closure Prop erties
• Union: L
1
?L
2
.
• Concatenation: L
1
·L
2
.
• Kleene Star: L
*
.
• Non-Closure:
– In tersection: L
1
nL
2
not alw a ys CFL.
– Complemen t: S
*
\L not alw a ys CFL.
• In tersection with Regular: LnR is CFL, where R is regular.
Pumping Lemma
• 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 .
Grammar and Language Relationship
Regular Grammar
• Righ t-Linear: A?a or A?aB , where A,B ?V , a?T .
• Left-Linear: A?a or A?Ba .
• Language: Regular languages.
Con text-F ree Grammar
• Pro ductions: A?a , where A?V , a?(V ?T)
*
.
• Language: Con text-F ree languages.
1
DF A to Regular Expression
Con v ersion
• State Elimination: F or DF A M = (Q,S,d,q
0
,F) , remo v e states, com bine transitions as regular
expressions.
• Arde n’s Lemma: Solv e R=Q+R·P as R=QP
*
.
• T ime Complexit y: O(|Q|
3
) .
2