Properties
of
Context-Free languages
Prof. Busch - LSU
1
Union
Context-free languages
are closed under:
Union
L1 is context free
L1  L 2
L 2 is context free
is context-free
Prof. Busch - LSU
2
Example
Language
Grammar
n n
L1  { a b }
L 2  { ww
R
S1  aS 1b | 
S 2  aS 2 a | bS 2 b | 
}
Union
n n
L  { a b }  { ww
R
}
Prof. Busch - LSU
S  S1 | S 2
3
In general:
For context-free languages L1 , L 2
with context-free grammars G1 , G 2
and start variables
S1 , S 2
The grammar of the union L1  L 2
S
has new start variable
and additional production S  S1 | S 2
Prof. Busch - LSU
4
Concatenation
Context-free languages
Concatenation
are closed under:
L1 is context free
L1 L 2
L 2 is context free
is context-free
Prof. Busch - LSU
5
Example
Language
Grammar
n n
L1  { a b }
L 2  { ww
R
S1  aS 1b | 
S 2  aS 2 a | bS 2 b | 
}
Concatenation
n n
L  { a b }{ ww
R
}
Prof. Busch - LSU
S  S1 S 2
6
In general:
For context-free languages L1 , L 2
with context-free grammars G1 , G 2
and start variables
S1 , S 2
The grammar of the concatenation L1 L 2
S
has new start variable
and additional production S  S1 S 2
Prof. Busch - LSU
7
Star Operation
Context-free languages
Star-operation
are closed under:
L is context free
*
L
Prof. Busch - LSU
is context-free
8
Example
Language
Grammar
n n
S  aSb | 
L  {a b }
Star Operation
n n
S1  SS 1 | 
L  {a b } *
Prof. Busch - LSU
9
In general:
For context-free language
with context-free grammar
and start variable
L
G
S
The grammar of the star operation L *
S1
has new start variable
and additional production S1  SS 1 | 
Prof. Busch - LSU
10
Negative Properties
of
Context-Free Languages
Prof. Busch - LSU
11
Intersection
Context-free languages
intersection
are not closed under:
L1 is context free
L1  L 2
L 2 is context free
not necessarily
context-free
Prof. Busch - LSU
12
Example
n n m
n m m
L1  { a b c }
L2  {a b c }
Context-free:
Context-free:
S  AC
S  AB
A  aAb | 
A  aA | 
C  cC | 
B  bBc | 
Intersection
L1  L 2  { a b c } NOT context-free
n n n
Prof. Busch - LSU
13
Complement
Context-free languages
complement
are not closed under:
L
is context free
L
Prof. Busch - LSU
not necessarily
context-free
14
Example
n n m
n m m
L1  { a b c }
L2  {a b c }
Context-free:
Context-free:
S  AC
S  AB
A  aAb | 
A  aA | 
C  cC | 
B  bBc | 
Complement
n n n
L1  L 2  L1  L 2  { a b c }
NOT context-free
Prof. Busch - LSU
15
Intersection
of
Context-free languages
and
Regular Languages
Prof. Busch - LSU
16
The intersection of
a context-free language and
a regular language
is a context-free language
L1 context free
L1  L 2
L 2 regular
context-free
Prof. Busch - LSU
17
Machine M 1
Machine M 2
NPDA for L1
DFA for L 2
context-free
regular
Construct a new NPDA machine M
that accepts L1  L 2
M
simulates in parallel M 1 and M 2
Prof. Busch - LSU
18
NPDA M 1
q1
a, b  c
DFA M 2
q2
a
p1
transition
p2
transition
NPDA M
q1 , p1 a , b  c q , p
2
2
transition
Prof. Busch - LSU
19
NPDA M 1
q1
, b  c
DFA M 2
q2
p1
transition
NPDA M
q1 , p1
, b  c
q 2 , p1
transition
Prof. Busch - LSU
20
NPDA M 1
DFA M 2
q0
p0
initial state
initial state
NPDA M
q0 , p0
Initial state
Prof. Busch - LSU
21
NPDA M 1
DFA M 2
p1
q1
final state
p2
final states
NPDA M
q1 , p1
q1 , p 2
final states
Prof. Busch - LSU
22
Example:
context-free
*
*
L1  { w1 w 2 : | w1 | | w 2 |, w1  { a , b } , w 2  { c , d } }
NPDA M 1
a,  1
b,   1
c ,1  
d ,1  
q 0  ,    q1  ,    q 2  ,    q 3
Prof. Busch - LSU
23
regular
*
L 2  { a , c}
DFA M 2
a, c
p0
Prof. Busch - LSU
24
context-free
Automaton for: L1  L 2  { a n c n : n  0}
NPDA M
a,  1
q0 , p0
,  
q1 , p 0
c ,1  
,  
Prof. Busch - LSU
q2 , p0
,  
q3 , p0
25
In General:
M
simulates in parallel M 1 and M 2
M accepts string w
if and only if
M 1 accepts string w
and
M 2 accepts string w
L(M )  L(M 1)  L(M 2 )
Prof. Busch - LSU
26
Therefore:
M is NPDA
L ( M 1 )  L ( M 2 ) is context-free
L1  L 2 is context-free
Prof. Busch - LSU
27
Applications
of
Regular Closure
Prof. Busch - LSU
28
The intersection of
a context-free language and
a regular language
is a context-free language
Regular Closure
L1 context free
L1  L 2
L 2 regular
context-free
Prof. Busch - LSU
29
An Application of Regular Closure
Prove that:
n n
L  { a b : n  100 , n  0}
is context-free
Prof. Busch - LSU
30
We know:
n n
{ a b : n  0}
is context-free
Prof. Busch - LSU
31
We also know:
L1  { a
100 100
b
*
is regular
}
L1  {( a  b ) }  { a
100 100
b
Prof. Busch - LSU
}
is regular
32
n n
{a b }
context-free
*
L1  {( a  b ) }  { a
regular
n n
(regular closure) { a b }  L1
n n
100 100
b
context-free
n n
{ a b }  L1  { a b : n  100 , n  0}  L
is context-free
Prof. Busch - LSU
33
}
Another Application of Regular Closure
Prove that:
L  { w : n a  nb  n c }
is not context-free
Prof. Busch - LSU
34
If L  { w : n a  n b  n c } is context-free
(regular closure)
Then
n n n
L  { a * b * c *}  { a b c }
context-free
regular
context-free
Impossible!!!
Therefore, L is not context free
Prof. Busch - LSU
35
Descargar

Languages and Finite Automata